Językiem bezkontekstowym nazywany jest język, który zdefiniowany jest za pomocą zbioru produkcji bezkontekstowych. Produkcja bezkontekstowa jest wtedy i tylko wtedy, gdy:
A ::= ξ (A ∈ N, ξ ∈(N ∪ T)*)
Lewa strona produkcji bezkontekstowej składa się z pojedynczego symbolu pomocniczego i może być zastąpiona przez ξ niezależnie od kontekstu, w jakim pojawia się A. Jeśli produkcja jest postaci:
αAβ:: = αξβ
to nazywana jest produkcją kontekstową, ponieważ zastąpienie A przez ξ może nastąpić tylko w kontekście α i β.
Przykład 1:
Przykład ten zawiera gramatykę, w której za pomocą rekursji można wyprowadzić nieskończenie wiele zadań za pomocą skończonego zbioru produkcji.
S ::= xA
A ::= z|yA
Zbiór zadań jakie mogą być wyprowadzone z symbolu początkowego S:
xz
xyz xyyz xyyyz ...
Title
Description