|
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
szó
alakú (a zi-k itt betűk, azaz a-k vagy b-k), akkor
a ww-1 szó
alakú, tehát a fordítása
uXu-1 alakú lesz, ahol
a
fordítása.
Másrészt viszont igaz az is, hogy minden uXu-1 alakú szó , ahol
,
előáll egy ww-1 szó,
fordítottjaként.
Ha
,
akkor a fordítása is .
Vagyis a nyelv, amire nyelvtan kell:
.
Erre könnyű nyelvtant csinálni:
,
.
|