An Entertaining Example of Using the Concepts of Context-Free Grammar and Pushdown Automation
Author(s)
Krasimir Yordzhev*
Affiliation(s)
Faculty of Mathematics and Natural Sciences, South-West University, Blagoevgrad, Bulgaria.
Faculty of Mathematics and Natural Sciences, South-West University, Blagoevgrad, Bulgaria.
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.
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.
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.
[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.