Research ArticleOpen AccessGoogle Scholar indexed
An Entertaining Example of Using the Concepts of Context-Free Grammar and Pushdown Automation
Faculty of Mathematics and Natural Sciences, South-West University, Blagoevgrad, Bulgaria
- 1 Faculty of Mathematics and Natural Sciences, South-West University, Blagoevgrad, Bulgaria
Open Journal of Discrete Mathematics·Volume 02 (2012)·Pages 105–108·Published 18 July 2012·DOI10.4236/ojdm.2012.23020
Copy link · social · email
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.
KeywordsContext-Free GrammarContext-Free LanguagePushdown AutomationHanoi towersDiscrete Mathematics Learning
- J. Arsac, “Jeux et Casse—Tête a Programmer,” BORDAS, Paris, 1985.
- A. V. Anisimov, “Recursive Information Transducers,” Vishcha Shkola, Kiev, 1987.
- A. V. Anisimov, “Informatics, Creativity, Recursion,” Naukova Dumka, Kiev, 1988.
- N. Wirth, “Algorithms + Data Structures = Programs,” Prentice Hall, Boston, 1976.
- I. Chiswell, “A Course in Formal Languages, Automata and Groups.” Springer-Verlag, London, 2009. doi:10.1007/978-1-84800-940-0
- J. Denev, R. Pavlov and I. Demetrovich, “Discrete Mathematics,” Science and Art, Soa, 1984.
- J. Denev and S. Shtrakov, “Discrete Mathematics,” SouthWest University “N. Rilski”, Blagoevgrad, 1995.
- J. E. Hopcroft, R. Motwani and J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation,” Addison-Wesley, Boston, 2001.
- K. Manev, “Introduction in Discrete Mathematics,” KLMN, Soa, 2003.
- J.-P. Allouche and F. Dress. Tours de Hano? et automates. Informatique théorique et applications, 24(1):1{15, 1990. (in French).
- J.-P. Allouche and J. Shallit, “Automatic Sequences: Theory, Applications, Generalizations,” University Press, Cambridge, 2003. doi:10.1017/CBO9780511546563
- S. Shtrakov, K. Yordzhev and M. Todorova, “Guide for Solving of Tasks in Discrete Mathematics,” South-West University “N. Rilski”, Blagoevgrad, 2004.
- S. Ginsburg, “The Mathematical Theory of Context-Free Languages,” McGraw-Hill, Boston, 1966.
- G. Lallemant, “Semigroups and Combinatorial Applications,” John Wiley & Sons, Hoboken, 1979.
- A. V. Aho and J. D. Ullman, “The Theory of Parsing, Translation and Computing,” Prentice-Hall, Upper Saddle River, 1972.