A negyedik kis zh egy jó megoldása (a) A fordító automatája: Magyarázat: $A$ állapotban vagyunk, ha $a$-t olvastunk utoljára, $B$-ben, ha $b$-t. (b) Vegyük észre, hogy a lefordított szó lehet üres (ha csupa $a$ volt a fordítandó szóban) vagy pedig mindenképp $x$-szel kezdõdik, hiszen az elsõ $b$ megjelenésekor kiírunk egy $x$-et. Mivel a szó $a$-ra végzõdik, a következõ váltáskor, amikor $b$ után $a$ jön, kiírunk $y$-t. Innen ugyanígy folytatva, látható, hogy a lefordított szavak ${(xy)}^i$ alakúak lesznek, $i\geq 0$-val. Kell még, hogy minden ilyen szó elõ is áll. Már láttuk, hogy az $\epsilon$ elõáll fordításként, az ${(xy)}^k$ szó pedig, ahol $k\geq 1$, kijön pl. az ${(ab)}^ka$ fordításaként. Emiatt a nyelvtan: $S\ensuremath{\rightarrow}xA\;\vert\;\epsilon$, $A\ensuremath{\rightarrow}yS$. Ez reguláris, a lehetõ legegyszerûbb.