Context-Sensitive Grammars and Linear-Bounded Automata
Автор: Prem Nath
Журнал: International Journal of Computer Network and Information Security(IJCNIS) @ijcnis
Статья в выпуске: 1 vol.8, 2016 года.
Бесплатный доступ
Linear-bounded automata (LBA) accept context-sensitive languages (CSLs) and CSLs are generated by context-sensitive grammars (CSGs). So, for every CSG/CSL there is a LBA. A CSG is converted into normal form like Kuroda normal form (KNF) and then corresponding LBA is designed. There is no algorithm or theorem for designing a linear-bounded automaton (LBA) for a context-sensitive grammar without converting the grammar into some kind of normal form like Kuroda normal form (KNF). I have proposed an algorithm for this purpose which does not require any modification or normalization of a CSG.
Context-sensitive Grammars (CSGs), Context-sensitive Languages (CSLs), Linear-Bounded Automata (LBA), Replaceable Sentence (RS)
Короткий адрес: https://sciup.org/15011493
IDR: 15011493
Список литературы Context-Sensitive Grammars and Linear-Bounded Automata
- N. Chomsky, "On Certain Formal Properties of Grammars", Information and Control (1959), Vol. 2, pp. 137-167.
- J. Myhill, "Linear Bounded Automata", Wright Air Development Division, Tech. Note No. 60-165 (1960), Cincinnati, Ohio.
- Peter S. Landweber, "Three Theorem on Phrase Structure Grammar of Type 1", Information and Control, (1963), Vol. 6, Pp 131-136.
- S. Y. Kuroda, "Classes of Languages and Linear-Bounded Automata", Information and Control (1964), Vol. 7, Pp. 207-223.
- John E. Hoffcroft, Jeffrey D. Ullman, "Introduction to Automata Theory, Languages, and Computation" 2001 Edition, Narosha Publishing House, New Delhi.
- A. Salomaa, "Computations and Automata" 1985 Edition, Encyclopedia of Mathematics and its Applications, Cambridge University Press.
- Harry R. Lewis and Christos H. Papadimitriou "Elements of the Theory of Computation", 2001 Edition, Printice-Hall Publication of India.
- John C. Martin "Introduction to Language and the Theory of Computation", Second Edition, Tata McGraw-Hill Publication, India.
- Peter Linz, "An Introduction to Formal Languages and Automata", Third Edition, Narosha Publication House, New Delhi (India).
- R. B. Patel and Prem Nath, "Automata Theory and Formal Languages", Second Edition, Umesh Publication, Delhi (India).
- A. Salomaa, I. N. Sneddon, "Theory of Automata" 2013 Edition, Pergamon Press, ISBN 0080133762.
