A Note on Automata

Volume 15, Issue 1, pp 88-96 http://dx.doi.org/10.22436/jmcs.015.01.08

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 2707 Downloads
• 3958 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

Keywords

• Formal language
• Automata
• Length product

MSC

•  18B20
•  68Q45

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.
  • View Article
  • Google Scholar


• [2] N. Chomsky, Three Models for the Description of Languages, IRE Transactions on Information Theory, 2 (3) (1956), 113–124.
  • View Article
  • Google Scholar


• [3] N. Chomsky, On Certain Formal Properties of Grammars, Information and Control, 2 (2) , 137–167. (1959)
  • View Article
  • MathSciNet
  • Google Scholar


• [4] D. Grune, C. H. Jacobs, Parsing Techniques – A Practical Guide, Ellis Horwood, England (1990)
  • Google Scholar


• [5] J. E. Hopcroft, J. D. Ullman, Formal Languages and Their Relations to Automata, Addison-Wesley Publishing , (1969)
  • MathSciNet
  • Google Scholar


• [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.
  • Google Scholar


• [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)
  • View Article
  • Google Scholar


• [8] T. Jiang, B. Ravikumar, M. Li, K. W. Regan, Formal Grammars and Languages, Lecture Notes, (2010), 1 – 40.
  • Google Scholar


• [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)
  • Google Scholar


• [10] A. K. Joshi, K. V. Shanker, D. Weir, The Convergence of Mildly Context-Sensitive Grammar Formalisms, Technical Reports (CIS), 539 (1990), 1–65.
  • Google Scholar


• [11] J. Kari, Automata and Formal Languages, University of Turku, Finland, (2013), 1– 150.
  • Google Scholar


• [12] P. M. Postal, D. T. Langendoen, English and the Class of Context-Free Languages, Computational Linguistics, 10 (3 – 4) (1984), 177–181.
  • Google Scholar


• [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.
  • Google Scholar