Back
 OJDM  Vol.2 No.3 , July 2012
An Entertaining Example of Using the Concepts of Context-Free Grammar and Pushdown Automation
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