next up previous
Next: About this document ...

A fordítandó nyelv automatája:

\includegraphics{gy931.eps}

A fordító átalakított automatája:

\includegraphics{gy932.eps}

A fordított nyelv automatája:

\includegraphics{gy933.eps}

Az $\epsilon$-átmeneteket kiküszöbölve:

\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.



 

Csiga
1999-05-16