|
A második kis zh egy jó megoldása
Az alábbi véges automata a kívánt nyelvet fogadja el, az állapotok jelentése a
következõ:
= a szó eleje vagy csak b betû jött eddig
= páratlan sok a jött az utolsó homogén részsorozatban
= páros sok a jött az utolsó homogén részsorozatban
= egy páratlan hosszú teljes homogén a-sorozat után 1 darab b jött
= páratlan hosszú homogén a-sorozat után jött legalább 2 b, vagy páros
hosszú homogén a-sorozat után jött legalább 1 b
Ezt minimalizálva azt kapjuk, hogy és összevonható
(a csapdát nem rajzoltam be):
A reguláris kifejezés:
(1) A minimálautomatából leolvasva (milyen körök után juthatunk a kezdõbõl
elfogadó állapotba?):
.
(2) Máshogy: egyenletrendszert írunk fel a minimálautomatára:
, ,
Az utolsó egyenletet beírjuk a másodikba:
, majd ezt beírjuk az elsõbe:
.
Innen adódik, hogy
.
|