Unit - 3
Context-sensitive languages
Q1) What is the context - sensitive grammar?
A2)
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.
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
Q2) Write short notes on context - sensitive language ?
A2)
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.
Q3) Define linear bounded automata ?
A3)
Linear bounded automata
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
A deterministic linear bounded automaton is always context-sensitive and the linear bounded automaton with empty language is undecidable.
Q4) Write any example of CSG ?
A4)
Example of CSG
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}.
Q5) Write closure properties of context sensitive language ?
A5)
They are closed under -
● Union
If λ ∉ L1 ∪ L2, then let
G = (N1 ∪ N2 ∪ {S}, T, S, P1 ∪ P2 ∪ {S → S1, S → S2}),
Where S ∉ N1 ∪ N2, a new symbol.
It can be seen that G generates the language L1 ∪ L2
● Concatenation
If λ ∉ L1 and λ ∉ L2, then let
G = (N1 ∪ N2 ∪ {S}, T, S, P1 ∪ P2 ∪ {S → S1S2}),
Where S ∉ N1 ∪ N2 a new symbol.
It can be easily seen that G generates the language L1L2.
Q6) What of the following is the most general phase - structured grammar ?
A) regular
B) Context - sensitive
C) Context - free
D) None of the above
A6)
Correct answer is “ B “.
