Átvezetés szintaktikai elemzéshez

Verem-Automata

Never forget $\mathcal{L}_2$

Bar Hiller Lemma

$\forall L\in\mathcal{L}_2:\exist\,p,q\in\N:$

$\forall u \in T^*: \ell(u)>p:$ $$ \exists u =v\,x\,w\,y\,z \;\land\;\ell(x\,w\,y)\le q \;\land\;xy\ne \varepsilon,\; $$

\[ \forall i\ge0: v\,x^i\,w\,y^i\,z\in L \]

Példa bizonyítás

\[ L=\{a^nb^nc^n\;|\;n>0\} \ne \mathcal L \]

(so that language is bs...)

↯ $\exists q,p,\;u=a^kb^kc^k = v\,x\,w\,y\,z$

$\ell(x\,w\,y)\le q < k,\;xy\ne\varepsilon$

$a^{k+j}b^kc^k\not\in L$

$a^{k+j}b^{k+j}c^k\not\in L$

${\char"21af} \implies L\not\in\mathcal L_2$

Veremautomata

$A=(Z,Q,T,\delta,z_0,q_0,F)$
$Z$ a verem szimbólumok ábácéje
$Q$ az állapotok nem üres véges halmaza
$T$ az input szimbólumok ábécéje
$\delta:Z\times Q\times(T\cup\{\varepsilon\})\to \mathcal{P}(Z^*\times Q)$
$z_0\in Z$ kezdő veremszimbólum
$q_0\in Q$ a kezdőállapot
$F\subseteq Q$ elfogadó állapotok halmaza

Alapesetben nem-determinisztikus (pl.: szimmetrikus szavak)

Akkor determinisztikus, ha $\forall\alpha\in Z^+QT^*$ esetén $\alpha$-ból egyetlen konfiguráció vezethető le

Verem - Példa

Ezek mind a verem állapota és az inputból következőket köti ki

$\delta(\#,q,a)=\{(\#a,q)\}$

# van a verem tetején

a jön inputként

felvesszük a-t a verembe

nem változtattuk az állapotunkkat

$\delta(\#,q,a)=\{(\varepsilon,q)\}$

# van a verem tetején

a jön inputként

nem vesszük fel az inputot

nem változtattuk az állapotunkkat

$\delta(a,q,b)=\{(\#,r)\}$

a van a verem tetején

b jön inputként

kitöröljük a verem tetején levő a-t

változtatjuk az állapotot

Verem definíció - Példa

$L=\{a^nb^n\;|\;n\ge 1\}$

A fenti nyelvet felismerő automata: a a definícióban használt halmaz egy elemű, nem szokás jelölni a {}-t

\[ \delta(\#,q_0,a)=\{(\#a,\;q_0)\} \]

\[ \delta(a,q_0,a)=\{(aa,\;q_0)\} \]

\[ \delta(a,q_0,b)=\{(\varepsilon,\;q_0)\} \]

\[ \delta(a,q_1,b)=\{(\varepsilon,\;q_1)\} \]

\[ \delta(\#a,q_1,\varepsilon)=\{(\#,\;q_2)\} \]

Veremautomata - Alternatív jelölés

$\delta(z,q,a)=\{(w_1,r_1),\ldots,(w_k,r_k)\}$ esetén:

\[ zqa\to w_ir_i\qquad 1\le i\le k \]

$\delta(z,q,\varepsilon)=\{(w_1,r_1),\ldots,(w_k,r_k)\}$ esetén:

\[ zq\to w_ir_i\qquad 1\le i\le k \]

Tehát a szabályok bal oldala ZQT vagy ZQ alakúak, a jobb oldal pedig Z*Q alakú

Kétféle elfogadás kapcsolata

Lemma TODO

Ha $L\in\mathcal L_2$, akkor megadható egy $A$ veremautomata úgy, hogy $L=N(A)$, azaz $\mathcal L_2\subseteq \mathcal L_{1V}$

Bizonyítás-sal :/