Context-Sensitive Grammars and Linear-Bounded Automata

Full Text (PDF, 385KB), PP.61-66

Views: 0 Downloads: 0


Prem Nath 1,*

1. The Patent Office, CP-2, Sector-5, Salt Lake, Kolkata-700091, India

* Corresponding author.


Received: 11 May 2015 / Revised: 6 Aug. 2015 / Accepted: 1 Sep. 2015 / Published: 8 Jan. 2016

Index Terms

Context-sensitive Grammars (CSGs), Context-sensitive Languages (CSLs), Linear-Bounded Automata (LBA), Replaceable Sentence (RS)


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


[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.