Az $L_1$ és az $L_2$ nyelveket is az definiálja, hogy bennük az $ab$ és a $ba$ minirészsorozatok száma azonos. Viszont $L_1$ ábécéje az $\{a,b\}$, $L_2$-é pedig az $\{a,b,c\}$. Mindkét nyelvre kell automata. Megoldás vázlata A feladatnak az is része, hogy eldöntsük, hogy milyen automatát akarunk adni. Baj, ha túl erõset adunk. A csel: $L_1$-re van véges automata is, mert az, hogy egy szó $L_1$-beli, az ekvivalens azzal, hogy ugyanazzal a betûvel kezdõdik, amivel végzõdik. $L_2$: Erre már PDA kell, melynek elve: Lesz $q_a$, $q_b$, $q_c$ állapot, ezekben kódoljuk, hogy mit olvastunk utoljára. A veremben ( a $Z_0$-n kívül) mindig csak $A$-k vagy csak $B$-k lesznek, attól függõen, hogy $ab$ vagy $ba$ volt több eddig. Ízelítõ a szabályokból: $\delta(q_a,a,X)=(q_a,X)$, minden $X$ veremszimbólumra $\delta(q_b,b,X)=(q_b,X)$, minden $X$ veremszimbólumra $\delta(q_c,c,X)=(q_c,X)$, minden $X$ veremszimbólumra Azaz ha ugyanolyan betû jön újra, akkor nem történik semmi. $\delta(q_a,b,A)=(q,AA)$, ha eddig az $ab$-k voltak többen és még egy $ab$ jön, akkor plusz egy $A$ a verembe $\delta(q_a,b,B)=(q,\epsilon)$, ha eddig a $ba$-k voltak többen és egy $ab$ jön, akkor ki egy $B$-t a verembõl Ez még csak vázlat, meg a szabályok egy része, befejezni otthon.