Gramatyka bezkontekstowa
Gramatyka bezkontekstowa – gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:
- A→Γ,{displaystyle Ato Gamma ,}
- A→Γ,{displaystyle Ato Gamma ,}
gdzie:
A{displaystyle A}– dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje;
Γ{displaystyle Gamma }– dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.
Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.
Formalna definicja |
Gramatyką bezkontekstową nazywa się czwórkę uporządkowaną (T,N,P,S),{displaystyle (T,N,P,S),}
T{displaystyle T}jest skończonym zbiorem symboli terminalnych,
N{displaystyle N}jest skończonym zbiorem symboli nieterminalnych,
P{displaystyle P}jest skończonym zbiorem reguł typu L→R,{displaystyle Lto R,}
gdzie L∈N{displaystyle Lin N}
oraz R∈(T∪N)∗,{displaystyle Rin (Tcup N)^{*},}
S∈N{displaystyle Sin N}jest wyróżnionym elementem początkowym.
Przykłady |
- Przykład 1
- Gramatyka ({a,b},{S},{S→aSb|ϵ},S){displaystyle ({a,b},{S},{Sto aSb|epsilon },S)}
generuje język {anbn:n∈N}.{displaystyle {a^{n}b^{n}:nin mathbb {N} }.}
Ten język nie jest regularny.
- Przykład 2
- Język {w:w∈{a,b}∗∧w=wR},{displaystyle {w:win {a,b}^{*}wedge w=w^{R}},}
który jest językiem wszystkich palindromów nad alfabetem {a,b},{displaystyle {a,b},}
może być wygenerowany przez następującą gramatykę:
- ({a,b},{S},{S→aSa|bSb|a|b|ϵ},S).{displaystyle ({a,b},{S},{Sto aSa|bSb|a|b|epsilon },S).}
Postaci normalne |
Każdy język bezkontekstowy nie zawierający słowa pustego może być wyrażony za pomocą gramatyki w postaci normalnej Greibach oraz postaci normalnej Chomskiego.
| ||||||||||||||||||||||||||||||||||||
