International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 8, No. 1, 8 Jan. 2016
Cover page and Table of Contents: PDF (size: 385KB)
Context-Sensitive Grammars and Linear-Bounded Automata
Full Text (PDF, 385KB), PP.61-66
Views: 0 Downloads: 0
Author(s)
Prem Nath
1,*
Index Terms
Context-sensitive Grammars (CSGs), Context-sensitive Languages (CSLs), Linear-Bounded Automata (LBA), Replaceable Sentence (RS)
Abstract
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.
Cite This Paper
Prem Nath, "Context-Sensitive Grammars and Linear-Bounded Automata", International Journal of Computer Network and Information Security(IJCNIS), Vol.8, No.1,pp.61-66, 2016. DOI:10.5815/ijcnis.2016.01.08
Reference
[1]N. Chomsky, “On Certain Formal Properties of Grammars”, Information and Control (1959), Vol. 2, pp. 137-167.
[2]J. Myhill, “Linear Bounded Automata”, Wright Air Development Division, Tech. Note No. 60-165 (1960), Cincinnati, Ohio.
[3]Peter S. Landweber, “Three Theorem on Phrase Structure Grammar of Type 1”, Information and Control, (1963), Vol. 6, Pp 131-136.
[4]S. Y. Kuroda, “Classes of Languages and Linear-Bounded Automata”, Information and Control (1964), Vol. 7, Pp. 207-223.
[5]John E. Hoffcroft, Jeffrey D. Ullman, “Introduction to Automata Theory, Languages, and Computation” 2001 Edition, Narosha Publishing House, New Delhi.
[6]A. Salomaa, “Computations and Automata” 1985 Edition, Encyclopedia of Mathematics and its Applications, Cambridge University Press.
[7]Harry R. Lewis and Christos H. Papadimitriou “Elements of the Theory of Computation”, 2001 Edition, Printice-Hall Publication of India.
[8]John C. Martin “Introduction to Language and the Theory of Computation”, Second Edition, Tata McGraw-Hill Publication, India.
[9]Peter Linz, “An Introduction to Formal Languages and Automata”, Third Edition, Narosha Publication House, New Delhi (India).
[10]R. B. Patel and Prem Nath, “Automata Theory and Formal Languages”, Second Edition, Umesh Publication, Delhi (India) .
[11]A. Salomaa, I. N. Sneddon, “Theory of Automata” 2013 Edition, Pergamon Press, ISBN 0080133762.