A context sensitive grammar (CSG) is a grammar where all productions are of the form αAβ → αγβ where γ ≠ ε.
During derivation non-terminal A will be changed to γ only when it is present in the context of α and β.
*Note the constraint that the replacement string γ ≠ ε ; as a consequence we have α ⇒ β implies |α| ≤ |β|
CSG is a Noncontracting grammar.
Formal Definition of Context Sensitive Grammar
A context sensitive grammar G = ( N, Σ, P, S), where
- N is a set of non-terminal symbols
- Σ is a set of terminal symbols
- S is the start symbol, and
- P is a set of production rules, of the form αAβ → αγβ , where A in N, α, β ∈ (N ∪ Σ) and γ ∈ (N ∪ Σ)+
The production S → ε is also allowed if S is the start symbol and it does not appear on the right side of any production.
Linear Bounded Automata
Linear Bounded Automata (LBA) is a single tape Turing Machine with two special tape symbols call them left marker < and the right marker >.
The transitions should satisfy these conditions:
- It should not replace the marker symbols by any other symbol.
- It should not write on cells beyond the marker symbols.
Thus the initial configuration will be : < q0a1a2a3a4a5…..an >
Real Also Definition of Pushdown Automata
Formal Definition
Formally Linear Bounded Automata is a non-deterministic Turing Machine , M = ( Q, Σ, Γ, δ, ε, q0, <, >, t, r)
- Q is set of all states
- Σ is set of all terminals
- Γ is set of all tape symbols, Σ ⊂ Γ
- δ is set of transitions
- ε is blank symbols or null
- < is left marker and > is right marker
- t is accept state
- r is reject state