OJDM  Vol.2 No.3 , July 2012
An Entertaining Example of Using the Concepts of Context-Free Grammar and Pushdown Automation
Author(s) Krasimir Yordzhev*
ABSTRACT
A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-free grammar which generates an algorithm for solving this task is described. A deterministic pushdown automation which in its work imitates the work of monks in solving the task of the Hanoi towers is built.

Cite this paper
K. Yordzhev, "An Entertaining Example of Using the Concepts of Context-Free Grammar and Pushdown Automation," Open Journal of Discrete Mathematics, Vol. 2 No. 3, 2012, pp. 105-108. doi: 10.4236/ojdm.2012.23020.
References
[1]   J. Arsac, “Jeux et Casse—Tête a Programmer,” BORDAS, Paris, 1985.

[2]   A. V. Anisimov, “Recursive Information Transducers,” Vishcha Shkola, Kiev, 1987.

[3]   A. V. Anisimov, “Informatics, Creativity, Recursion,” Naukova Dumka, Kiev, 1988.

[4]   N. Wirth, “Algorithms + Data Structures = Programs,” Prentice Hall, Boston, 1976.

[5]   I. Chiswell, “A Course in Formal Languages, Automata and Groups.” Springer-Verlag, London, 2009. doi:10.1007/978-1-84800-940-0

[6]   J. Denev, R. Pavlov and I. Demetrovich, “Discrete Mathematics,” Science and Art, Soa, 1984.

[7]   J. Denev and S. Shtrakov, “Discrete Mathematics,” SouthWest University “N. Rilski”, Blagoevgrad, 1995.

[8]   J. E. Hopcroft, R. Motwani and J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation,” Addison-Wesley, Boston, 2001.

[9]   K. Manev, “Introduction in Discrete Mathematics,” KLMN, Soa, 2003.

[10]   J.-P. Allouche and F. Dress. Tours de Hano? et automates. Informatique théorique et applications, 24(1):1{15, 1990. (in French).

[11]   J.-P. Allouche and J. Shallit, “Automatic Sequences: Theory, Applications, Generalizations,” University Press, Cambridge, 2003. doi:10.1017/CBO9780511546563

[12]   S. Shtrakov, K. Yordzhev and M. Todorova, “Guide for Solving of Tasks in Discrete Mathematics,” South-West University “N. Rilski”, Blagoevgrad, 2004.

[13]   S. Ginsburg, “The Mathematical Theory of Context-Free Languages,” McGraw-Hill, Boston, 1966.

[14]   G. Lallemant, “Semigroups and Combinatorial Applications,” John Wiley & Sons, Hoboken, 1979.

[15]   A. V. Aho and J. D. Ullman, “The Theory of Parsing, Translation and Computing,” Prentice-Hall, Upper Saddle River, 1972.

 
 
Top