An Entertaining Example of Using the Concepts of Context-Free Grammar and Pushdown Automation


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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[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.

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.