Levezetések és egy kis Chomsky
Közvetlen levezetés
- Legyen \(G=(N,T,P,S)\) egy adott grammatika
- Legyen \(u,v\in(N\cup T)^*\)
\(v\) mondatformából akkor vezethető le közvetlenül az \(u\) mondatformából, ha \(\exists u_1,u_2\in (N\cup T)^*\) és TODO
Közvetlen evezetés - Példa
\(u=ab\red{Bca}aAcb\) \(v=ab\red{caBA}aAcb\)
- \(Bca\to caBA\in P\)
az 1. szabály miatt levezethető közvetlen
Közvetett levezetés
- Legyen \(G=(N,T,P,S)\) egy adott grammatika
- Legyen \(u,v\in(N\cup T)^*\)
- Akkor vezethető le, ha \(\exists k\ge 0\in\N:\;x_0,\ldots,x_k\in(N\cup T)\) TODO
Grammatika által generált nyelv
\[
L(G):=\{u\in T^*\;|\;S\underset{G}{\Rightarrow}^* u\}
\]
Ekvivalencia
A \(G_1\) és \(G_2\) nyelvtanok ekvivalensek, ha TODO
Chomsky-féle grammatikák
KES - Korlátozott \(\varepsilon\) szabály
Amikor \(S\to \varepsilon\) engedett, de \(S\) nem jelenhet meg jobboldalt
0. Típus
- Nincs megkötés
- \(p\to q\)
- \((p\in N^+,\;q\in(N\cup T)^*)\)
1. Típus - Környezetfüggő grammatika
- \(u_1Au_2\to u_1vu_2\)
- \(u_1,u_2,v\in(N\cup T)^*,\;A\in N,\;v\ne\varepsilon\)
- \(p\to q\)
- \(\ell(p)\le\ell(q)\)
- KES
- \(\ell(p)\le\ell(q)\)
- Kuroda normál forma
- \(A\to a\;\lor\; A\to B\;\lor\;A\to BC\;\lor\;AB\to BC\) alakúak a szabályok
- \(a\in T;\;A,B,C,D\in N\)
- KES
- \(A\to a\;\lor\; A\to B\;\lor\;A\to BC\;\lor\;AB\to BC\) alakúak a szabályok
2. Típus - Környezetfüggetlen grammatika
- \(A\to v\)
- \(v\in (N\cup T)^*,\;A\in N\)
- \(v\ne\varepsilon\)
- KES
- Chomsky normál forma
- \(A\to a\;\lor\;A\to BC\)
- \(a\in T;\;A,B,C \in N\)
- KES
3. Típus - Reguláris grammatika
- \(A\to uB\;\lor\;A\to u\)
- \(u\in T^*;\;A,B\in N\)
- KES
- 3-as normál forma
- \(A\to aB\;\lor\;A\to\varepsilon\)
- \(a\in T;\;A,B\in N\)
Chomsky nyelvcsalád jelölése: \(\mathcal{L}_i\)
Chomsky-Hierarchia
\[ \mathcal{L}_3\subset\mathcal{L}_2\subset\mathcal{L}_1\subset\mathcal{L}_0 \]
- Hasonlóan a grammatikákra (\(\mathcal{G}_i\))
- Nyilván akkor mondhatunk egy \(L\) nyelvet \(i\in\{0,1,2,3\}\) típusúna, ha megadható egy olyan grammatika, ami kigenerálja az \(L\) nyelvet