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 𝛂 ,β ∈ (V u T) and |𝛂| ≤ | β |
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.
Fig 1: context sensitive grammar
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 :
● Union, intersection and concatenation of two context-sensitive languages is
Context-sensitive.
● Complement of a context-sensitive language is context-sensitive.
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 {an bn cn | n≥1}.
Key takeaway:
- The language that can be defined by context - sensitive grammar is called CSL.
- Context-sensitive grammars are more powerful than context-free grammars
- A Context-sensitive grammar is an Unrestricted grammar
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 −
● Q is a finite set of states
● X is the tape alphabet
● ∑ is the input alphabet
● q0 is the initial state
● ML is the left end marker
● MR is the right end marker where MR ≠ ML
● δ is a transition function which maps each pair (state, tape symbol) to (state,
Tape symbol, Constant ‘c’) where c can be 0 or +1 or -1
● F is the set of final states
Fig 2: linear bounded automata
A deterministic linear bounded automaton is always context-sensitive and the linear bounded automaton with empty language is undecidable..
Equivalence with CSG
A language is accepted by a CSG created by an LBA iff.Like CFG and PDA equivalence,
Given an x ∈ CSG G, you can see intuitively that LBA can start with S and choose all derivations from S non-deterministically and see if they are equal to the x input string. Since CSL's are non-contracting, only derivations of length |x| need to be generated by the LBA. This is because it is never able to shrink to the size of |x| if it produces a derivation longer than |x|.
Key takeaway -
● The measurement is limited to the region bounded by constants.
● A linear bounded automaton is a multi-track non-deterministic Turing machine with a tape of some limited finite length.
Reference:
- 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. John Martin, Introduction to Languages and the Theory of Computation, Tata McGraw Hill.
