UNIT 3
Context-sensitive languages
Context-Sensitive Grammar –
A Context-sensitive grammar is an Unrestricted grammar in which all the productions are of form –
Where α and β are strings of non-terminals and terminals.
Context-sensitive grammars are more powerful than context-free grammars because there are some languages that can be described by CSG but not by context-free grammars and CSL are less powerful than Unrestricted grammar. That’s why context-sensitive grammars are positioned between context-free and unrestricted grammars in the Chomsky hierarchy.
Context-sensitive grammar has 4-tuples. G = {N, Σ, P, S}, Where
N = Set of non-terminal symbols
Σ = Set of terminal symbols
S = Start symbol of the production
P = Finite set of productions
All rules in P are of the form α1 A α2 –> α1 β α2
Context-sensitive Language: The language that can be defined by context-sensitive grammar is called CSL. Properties of CSL are :
Example –
Consider the following CSG.
S → abc/aAbc
Ab → bA
Ac → Bbcc
bB → Bb
aB → aa/aaA
What is the language generated by this grammar?
Solution:
S → aAbc
→ abAc
→ abBbcc
→ aBbbcc
→ aaAbbcc
→ aabAbcc
→ aabbAcc
→ aabbBbccc
→ aabBbbccc
→ aaBbbbccc
→ aaabbbccc
The language generated by this grammar is {anbncn | n≥1}.
A linear bounded automaton is a multi-track non-deterministic Turing machine with a tape of some bounded finite length.
Length = function (Length of the initial input string, constant c)
Here,
Memory information ≤ c × Input information
The calculation is confined to the steady limited territory. The information letters in order contains two uncommon images which fill in as left end markers and right end markers which mean the advances neither one of the moves to one side of the left end marker nor to one side of the correct end marker of the tape.
A linear bounded automaton can be defined as an 8-tuple (Q, X, ∑, q0, ML, MR, δ, F) where −
A deterministic linear bounded automaton is always context-sensitive and the linear bounded automaton with empty language is undecidable..
Books
John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education Asia.
Reference books
1. Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson EducationAsia.
2. Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer.
3. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.
4. John Martin, Introduction to Languages and the Theory of Computation, Tata McGraw Hill.
