Feladat:

Készítsünk az

a(b+c(ba)*ca)*b+b

reguláris kifejezéssel megadott nyelvhez VDA-t, a Myhill Nerode tétel alapján, a maradék-nyelvek kiszámításával.

Megoldás:

0 hosszú „előtag” maradéknyelve:

L_ε = L

1 hosszú „előtag”-hoz tartozó maradéknyelvek:
(a szó első betűje a, b, vagy c, mi lehet a folytatás)

L_a = (b+c(ba)*ca)*b (új, tovább kell számolni)

L_b = ε ez a szó vége, nem lehet folytatni, nem kell tovább számolni

L_c = Ø mivel nem kezdődhet c-vel a szó, ez az üres, halmaz, nem számoljuk tovább!

2 hosszú „előtag”-hoz tartozó maradéknyelvek:
(csak az a-val kezdődő nyelvosztályokat kell kiszámolni, tehát meg kell nézni, mi a maradéknyelv aa, ab, és ac kezdet esetén)

L_aa = Ø

L_ab = ε + (b+c(ba)*ca)*b (új, tovább kell számolni)

L_ac = (ba)*ca (b+c(ba)*ca)*b (új, tovább kell számolni)

3 hosszú „előtag”-hoz tartozó maradéknyelvek:
(csak az ab-vel ás ac-vel kezdődők folytatásaival foglalkozunk)

L_aba = Ø

L_abb = ε + (b+c(ba)*ca)*b = L_ab

L_abc = (ba)*ca (b+c(ba)*ca)*b = L_ac

L_aca = Ø

L_acb = a(ba)*ca (b+c(ba)*ca)*b (új, tovább kell számolni)

L_acc = a (b+c(ba)*ca)*b (új, tovább kell számolni)

4 hosszú „előtag”-hoz tartozó maradéknyelvek:
(csak az acb-vel ás acc-vel kezdődők folytatásaival foglalkozunk)

L_acba = (ba)*ca (b+c(ba)*ca)*b = L_ac

L_acbb = Ø

L_acbc = Ø

L_acca =(b+c(ba)*ca)*b = L_a

L_accb = Ø

Laccc = Ø

Nem kaptunk új maradéknyelvet, kész vagyunk. Rajzoljuk le a VDA gráfját!

Állapotok a kapott maradéknyelvek.

Kezdőállapot az L_ε (=L).

Végállapotok azok, amelyekben az ε szerepel: L_b , L_ab .

Az átmenet függvényt abból lehet kiolvasni, hogyan kaptuk meg az egyik maradéknyelvből a következőt (L_a állapotból b-t olvasva jutunk L_ab állapotba, hisz a szó eleje ’a’-ról ’ab’-re növekedett.)

Az automata még nem VDA, mert parciális. A „hiba” állapottal, és a hibába futó élekkel kellene kiegészíteni, hogy VDA legyen, de a jobb áttekinthetőség miatt most ezek nélkül ábrázoljuk.

(ha hibát talál, kérem jelezze: veanna@elte.hu címre, köszönöm)