A Note on Automata
-
3191
Downloads
-
4681
Views
Authors
Dasharath Singh
- (Former Professor, Indian Institute of Technology, Bombay) Professor, Mathematics Department, Ahmadu Bello University, Zaria, Nigeria
Ahmed Ibrahim Isah
- Mathematics Department, Ahmadu Bello University, Zaria, Nigeria
Abstract
In this paper, a brief description of finite automata and the class of problems that can be solved by such devices is presented. The main objective is to introduce the concept of length product, illustrate its application to finite automata, and prove some related results.
Share and Cite
ISRP Style
Dasharath Singh, Ahmed Ibrahim Isah, A Note on Automata, Journal of Mathematics and Computer Science, 15 (2015), no. 1, 88-96
AMA Style
Singh Dasharath, Isah Ahmed Ibrahim, A Note on Automata. J Math Comput SCI-JM. (2015); 15(1):88-96
Chicago/Turabian Style
Singh, Dasharath, Isah, Ahmed Ibrahim. "A Note on Automata." Journal of Mathematics and Computer Science, 15, no. 1 (2015): 88-96
Keywords
- Formal language
- Automata
- Length product
MSC
References
-
[1]
T. Becker, A. Joshi, O. Rambow, Long-distance scrambling and tree adjoining grammars, In Proceedings of the fifth conference on European Chapter of the Association for Computational Linguistics, Association for Computational Linguistics, (1991), 21–26.
-
[2]
N. Chomsky, Three Models for the Description of Languages, IRE Transactions on Information Theory, 2 (3) (1956), 113–124.
-
[3]
N. Chomsky, On Certain Formal Properties of Grammars, Information and Control, 2 (2) , 137–167. (1959)
-
[4]
D. Grune, C. H. Jacobs, Parsing Techniques – A Practical Guide, Ellis Horwood, England (1990)
-
[5]
J. E. Hopcroft, J. D. Ullman, Formal Languages and Their Relations to Automata, Addison-Wesley Publishing , (1969)
-
[6]
R. Huybregts, The weak inadequacy of context-free phrase structure grammars, In Ger Jan de Haan, Mieke Trommelen, and Wim Zonneveld, editors, Van periferie naar kern, Foris, Dordrecht, (1984), 81–99.
-
[7]
G. Jäger, J. Rogers, Formal Language Theory: Refining the Chomsky Hierarchy, Philosophical Transactions of Royal Society of London, Series B, Biological Sciences, 1–29. (2012)
-
[8]
T. Jiang, B. Ravikumar, M. Li, K. W. Regan, Formal Grammars and Languages, Lecture Notes, (2010), 1 – 40.
-
[9]
A. Joshi, How much context-sensitivity is necessary for characterizing structural descriptions — tree adjoining grammars, In David Dowty, Lauri Karttunen, and Arnold Zwicky, editors, Natural Language Processing, Theoretical, Computational and Psychological Perspectives, Cambridge University Press, Cambridge, UK (1985)
-
[10]
A. K. Joshi, K. V. Shanker, D. Weir, The Convergence of Mildly Context-Sensitive Grammar Formalisms, Technical Reports (CIS), 539 (1990), 1–65.
-
[11]
J. Kari, Automata and Formal Languages, University of Turku, Finland, (2013), 1– 150.
-
[12]
P. M. Postal, D. T. Langendoen, English and the Class of Context-Free Languages, Computational Linguistics, 10 (3 – 4) (1984), 177–181.
-
[13]
J. Rogers, G. Pullum, Aural pattern recognition experiments and the subregular hierarchy, In Marcus Kracht, editor, Proceedings of 10th Mathematics of Language Conference, University of California, Los Angeles , (2007), 1–7.
-
[14]
K. Ruohonen, Formal Languages, Lecture Notes, (2009), 1–94.
-
[15]
S. Shieber, Evidence against the context-freeness of natural language, Linguistics and Philosophy, 8 (1985), 333–343.
-
[16]
D. Singh, A. I. Isah, Some Algebraic Structures of Languages, the Journal of Mathematics and Computer Science, 14 (2015), 250–257.