A feladat Adott az alábbi véges fordító kell: bemenő ábécé az $\{a,b\}$ és a fordító ezt teszi: ha az utoljára olvasott karakter megegyezik az azelőttivel, akkor írjon x -et, ha különböznek, akkor írjon y -t. Az első karakter beolvasása után ne írjon semmit, így egy n hosszú szöveg fordítása n-1 hosszú lesz. Ezzel a fordítóval lefordítjuk azt a nyelvet, mely azon szavakból áll, ahol a szavakban a karakterek száma páratlan. Mi lesz a fordított nyelv automatája?

Megoldás:

A fordítandó nyelv automatája:

\includegraphics{gy931.eps}

A fordító átalakított automatája (olyan értelemben átalakított, hogy egyszerre csak vagy írás vagy csak olvasás van, és azokból is csak egy betű egyszerre):

\includegraphics{gy932.eps}

A fordított nyelv automatája:

\includegraphics{gy933.eps}

Az $\epsilon$-átmeneteket kiküszöbölve (azaz, a zárójeles nyilakat epszilon-átmenetnek vesszük és determinizálunk):

\includegraphics{gy934.eps}

Minimalizálva:

\includegraphics{gy935.eps}

Megjegyzés: ugyanezt egy pici gondolkodással is megkaphattuk volna és akkor nem kellett volna ennyit számolni: Mivel az első karakter után a fordító nem ír ki semmit, az összes többi karakter után pedig egy szimbólumot ír ki, könnyű meggondolni, hogy a fordított nyelv épp a páros hosszú szavakat fogja tartalmazni. Az világos, hogy minden fordított szó páros sok karakterből áll és az is világos, hogy minden páros hosszú szó megkapható valami páratlan szó fordítottjaként.
Tanulság: érdemes gondolkodni.