next up previous
Next: About this document ...

Van ugyan eljárás arra, hogy egy véges fordító automatájából és egy CF nyelv veremautomatájából hogyan kell veremautomatát, aztán meg abból nyelvtant csinálni a fordított CF nyelvre, de ez nagyon bonyolult és hosszadalmas eljárás, kézzel végigszámolni borzalom.
Ehelyett gondolkodunk: ha egy $w\in {\{a,b\}}^+$ szó $z_1z_2\ldots z_{m-1}z_m$ alakú (a zi-k itt betűk, azaz a-k vagy b-k), akkor a ww-1 szó $z_1z_2\ldots z_{m-1}z_mz_mz_{m-1}\ldots z_1$ alakú, tehát a fordítása uXu-1 alakú lesz, ahol $u\in {\{X,Y\}}^*$ a $z_1z_2\ldots z_m$ fordítása. Másrészt viszont igaz az is, hogy minden uXu-1 alakú szó , ahol $u\in {\{X,Y\}}^*$, előáll egy ww-1 szó, $w\in {\{a,b\}}^+$ fordítottjaként. Ha $ww^{-1}=\epsilon$, akkor a fordítása is $\epsilon$.
Vagyis a nyelv, amire nyelvtan kell:
$L=\{\epsilon\}\cup \{uXu\;\vert\;u\in {\{X,Y\}}^*\}$. Erre könnyű nyelvtant csinálni: $S\ensuremath{\rightarrow}\epsilon\vert S'$, $S'\ensuremath{\rightarrow} XS'X\vert YS'Y\vert X$.

 

Csiga
1999-05-16