Kihagyás

Grammatikák

Gramatika - Alakja

\[ G=(N,T,P,S) \]
  • S - kezdő karakter
  • T - terminálisok halmaza
  • N - Nem ternimálisok halmaza
  • P - szabályok

Grammatika - Tulajdonságok

  • \(u \in T^*\)
  • \(L(G)\subseteq T^*\)
  • \(N\cap T = \emptyset\)
  • \(p\to q \in P\)
  • \(p\in \{T\cup N\}^*N\{T\cup N\}^*\)
    • Legalább egy nem terminális legyen benne
  • \(q\in \{T\cup N\}^*\)
    • Nincs extra megkötés, a \(q\) oldalon szerepelhet \(\varepsilon\) is
  • Szabály tüzelőképessége
    • \(w_1\,p\,w_2\mapsto w_1\,q\,w_2\)
  • \(S\in N\)
    • start szimbólum

Nyelv Definíció - Grammatika és Terminális

\[ L(G):=\{u\in T^*\,|\,S\underset{G}{\Rightarrow}^*u\} \]

Szabályok - Példa

\[ \begin{array}{ccl} P_1: & 1. & \;S\to A \\ & 2. & S\to A+S \\ & 3.& A \to B \\ & 4.& A\to B*A \\& 5. & B \to i \\ & 6.& B \to (S) \end{array} \]

\(S\overset{?}{\Rightarrow}A+S\)

\(\overset{1.}{\Rightarrow}A+A\)

\(\overset{3.}{\Rightarrow}B+A\)

\(\overset{3.}{\Rightarrow}B+B\)

\(\overset{5.}{\Rightarrow}B+i\)

\(\overset{5.}{\Rightarrow}i+i\)

\[ i+i\overset{\checkmark}{\in} L(G) \]
  • \(A\) helyébe 2, \(S\) helyébe is 2 helyettesítés valid
    • 4 szabály tüzelőképes (alkalmazható)

Megkötés

\(i\)-vel vagy nyitó zárójellel kezdőthet egy terminális

\[ i+i\overset{\checkmark}{\in} L(G) \]
\[ \left(\;i\left(\right.\right.\not\in L(G) \]

Levezetés - Példa - Visszafelé

Visszafelé legtöbbször ugyanolyan helyes, csak akadhatnak zsákutcák, amiknél vissza kell lépni

\[\begin{array}{cl} & u = i + i * i \\ 1.& \overset{3.}{\Leftarrow}i+i*B \\ 2.& \overset{3.}{\Leftarrow}i+B*B \\ 3.& \overset{3.}{\Leftarrow}B+B*B \\ 4.& \overset{4.}{\Leftarrow}B+B*A \\ 5.& \overset{4.}{\Leftarrow}B+A \\ 6.& \overset{3.}{\Leftarrow}A+A \\ 7.& \overset{1.}{\Leftarrow}A+S \\ 8.& \overset{2.}{\Leftarrow}S\end{array}\]

Példa - 2

\[ \begin{array}{ccl} P_2: & 1. & \;S\to AB \\ & 2. & A\to aA \\ & 3.& A \to \varepsilon \\ & 4.&B\to bB \\& 5. & B \to \varepsilon \end{array} \]
  • \(L(G)=\{a\}^*\{b\}^*\)
    • Regulárisan kifejezhető a nyelv
  • \(L(G)\) előállytható a szabályok algoritmikus alkalmazásával
  • Ez nem hármas típusú
    • balról jobbra történik a terminálisok előállítása
    • Mert több mint egy nem terminális van

Hármas típus előállítása

\[ A\to vB\qquad (A\in N,\; v\in T^*,\; B\in N) \]
\[ \begin{array}{ccl} P_3: & 1. & \;S\to \varepsilon\,|\,aS\,|\,B \\ & 2. & B\to \varepsilon\,|\,bB \end{array} \]

A \(\varepsilon\) előállítása rendundás, azonban teljesül a hármas típusnak megfeleltetés

\[ G_2\equiv G_3\quad \implies\quad L(G_2) = L(G_3) \]

Példa - 3

\[ \begin{array}{clrl} P_4: & 1. & \;S&\to YSB \\ & 2. & S&\to V \\ & 3. & YV &\to Vaa \\ & 4. & YV &\to aa\end{array} \]

\(S\overset{*}{\underset{1. n\text{-szer}}{\Rightarrow}}Y^nSb^n\underset{2.}{\Rightarrow}Y^nVb^n\underset{3.}{\Rightarrow}Y^{n-1}Vaab^n\underset{3.}{\Rightarrow}Y^{n-2}Vaaaab^n\ldots\underset{3.}{\Rightarrow}YV(aa)^{n-1}b^n\underset{4.}{\Rightarrow}(aa)^nb^n\)

\[ L=\{a^{2n}b^n\,|\,n\ge 1\}=\{aab,\ldots\} \]

Random előrehaladás

\[ L_0\subset L_1 \subset L_2 \subset \ldots \]

A grammatikák szintjei valódi tartalmazási kapcsolatban állnak

Példa 3 - kettes típusú megfelelője

\[ \begin{array}{clrl} P_5: & 1. & \;S&\to aaSb \\ & 2. & S&\to aab \end{array} \]
\[ L(G4) = L(G_5) \]

Helyes zárójelezés nyelve

\[ \begin{array}{clrl} P_6: & \;S&\to (S)\,|\,SS\,|\,\varepsilon \end{array} \]

\(S\overset{2.}{\Rightarrow}SS\overset{1.}{\Rightarrow}(S)S\overset{3.}{\Rightarrow}()S\overset{1.}{\Rightarrow}()((S))\overset{3.}{\Rightarrow}()(())\)

\[ \begin{array}{clrl} P_6: & \;S&\to aSb\,|\,SS\,|\,\varepsilon \end{array} \]

\(L_1=\{u\in\{ab\}^*\,|\,u=u_1u_2\;\land\;\ell_a(u_1)\ge\ell_b(u_1)\;\land\;\ell_a(u)=\ell_b(u)\}\)

\(L(G_6)\subseteq L_1\)

\(L(G_6)\overset{?}{\supseteq} L_1\)

\(L_1=\{\varepsilon,\,ab,\\ \,aabb,\,abab, \\ \,a^3b^3,a^2bab^2,a^2b^2ab,aba^2b^2,(ab)^3,\\\ldots\}\)

  • \(n=2k\quad (k\ge 0)\)
  • \(k=0\checkmark\)
  • \(k=1\checkmark\)
  • \(k=2\checkmark\)
  • \(2(k+1)\overset?=2k+2\)
    • \(u = a\,v_1\,b\,v_2\)
    • \(v_2=\varepsilon:\)
      • \(S\overset{1.}{\Rightarrow}aSb\overset{*}{\underset {t.i}\Rightarrow}a\,v_1\,b\)
    • \(v_2\ne\varepsilon:\)
      • \(S\overset{2.}{\Rightarrow}SS\overset{*}{\underset {t.i}\Rightarrow}S\,v_2\;\overset{1.}{\Rightarrow}aSb\,v_2\;\overset{*}{\underset {t.i}\Rightarrow}\;a\,v_1\,b\,v_2\)