6.2. 2-fejű (véges állapotú) automata

11. Definíció. A rendezett (Q, T, q 0, d, F) ötöst kétfejű véges automatának hívjuk, ha (a hagyományos véges automatákhoz hasonlóan)

Q: nemüres véges halmaz: állapotok halmaza,

T: szalagábécé,

q 0Q kezdőállapot,

FQ vég- (vagy elfogadó)állapotok halmaza,

d:Q×(T∪{λ})×(T∪{λ})  → 2 Q leképezés az állapotátmenet-függvény. ★

A konfigurációk halmaza: a még feldolgozandó input és az állapot (u, q) ahol uT *, qQ,

kezdeti konfiguráció: (w, q 0) ahol w az inputszó (feldolgozandó input).

A konfigurációk az állapotátmenet-függvénynek megfelelően változhatnak az automata számítási lépései alapján: (a u b, q)⊦(u, q ') ha q '∈d(q, a, b), ahol a, bT∪{λ}.

* jelölje a ⊦ reláció tranzitív és reflexív lezártját. Akkor mondjuk, hogy egy 2-fejű automata elfogad egy w input szót, ha (w, q 0)⊦*(λ, q) valamely qF állapotra. Egy automata által elfogadott szavak halmaza jelenti az automata által elfogadott/felismert nyelvet.

Az ábrán látható automata az L={a n b n | n>0} nyelvet fogadja el.

Az automata működés közben:

Ha az állapotátmenet-függvény alakja d:((Q 1×T×{λ})∪(Q 2×{λT))  → Q, ahol Q=Q 1Q 2, Q 1 és Q 2 diszjunktak, akkor determinisztikus 2-fejű automatáról beszélünk.

További példák kétfejű automaták működésére:

38. Tétel. A nemdeterminisztikus 2-fejű automaták által elfogadott nyelvek osztálya megegyezik a lineáris nyelvek osztályával.

Bizonyítás. Konstruktív mindkét irányban. Legyen adva egy (N, T, S, H) lineáris nyelvtan normálformában. Ekkor megkonstruáljuk azt a 2-fejű automatát, amely a megadott nyelvtan által generált nyelvet fogadja el:

a (Q, T, q 0, d, F) elemeit adjuk meg a következő módon:

Q=N∪{q f }, ahol q f N ;

T a terminális ábécé megegyezik az automata inputábécéjével;

q 0=S;

F={q f } ;

d pedig a következőképpen van definiálva a H szabályhalmaz alapján:

Ad(B, a, b), ha Ba A bH(A, BN;a, bT∪{λ}),

q f d(A, a, λ), ha AaH(AN;aT∪{λ}).

Könnyen belátható lépésenkénti indukcióval, hogy a nyelvtan minden egyes termináló levezetésének pontosan egy elfogadó út fog megfelelni az automatában, és más elfogadó út nem lesz. Legyen most adva egy (Q, T, q 0, d, F) 2-fejű automata, amihez megkonstruáljuk azt a nyelvtant, ami az automata által elfogadott nyelvet fogja generálni. Az általánosság csorbítása nélkül feltehetjük, hogy Q és T halmazok diszjunktak (ha ez nem teljesül, a Q halmaz elemeinek átnevezésével ez elérhető). Legyen ez alapján az (N, T, S, H) nyelvtan definiálva a következőképpen:

N=Q;

T a terminális ábécé megegyezik az automata inputábécéjével;

S=q 0;

a H halmaz elemeit pedig a következőképpen definiáljuk:

legyen Aa B bH, ha Bd(A, a, b) (A, BQ;a, bT∪{λ}), és

legyen Aa bH, ha Bd(A, a, b) (A, BQ;BF;a, bT∪{λ}).

Könnyen belátható, hogy az automata minden elfogadó útjához pontosan egy termináló levezetés fog tartozni, és csak olyan termináló levezetések lesznek amik ilyenek. ∎

Az ábrán a palindromák nyelvét elfogadó determinisztikus automata látható, az átmenteknél a nyíl iránya mutatja hogy melyik fej (melyik irányba lépő fej) lép az adott átmenetben. (A → a átmenet megfelel a korábban használt (a,λ); míg a ← a a korábbi (λ,a)-val jelölt átmenetnek.)

6.10. példa - Kétfejű automata készítése lineáris nyelvtanhoz

Adott a következő nyelvtan:({S, A, B, C}, {a, b, c}, S, {Sa a a A b b, Sa B a a, Aa a a A b, A → c, Ba B a a, B → C a, C → c C, C → c}). Az ezzel ekvivalens erős normálformájú nyelvtan: ({S, A, B, C, D, E, F, G, I, J, K, L, M, O, P}, {a, b, c}, S, {Sa D, Da E, Ea F, FG b, GA b, S → a I, I → J a, J → B a, A → a K, K → a L, L → a M, M → A b, A → c, B  → a O, O  → P a, P  → B a, B → C a, C → c C, C → c}).


Ennek megfelelően, az ez alapján konstruált 2-fejű elfogadó automata:

 (a, λ) (b, λ) (c, λ) (λ, a) (λ, b) (λ, c)
S D,I      
A K   q f    
B O    C   
C    C,q f    
D E      
E F      
F      G  
G      A  
I     J   
J     B   
K L      
L M      
M       
O     P A  
P     B   
q f       

Az első sor a lehetséges átmeneteket, az első oszlop pedig az állapotokat tartalmazza, S a kezdőállapot, qf pedig az egyetlen végállapot. ★

7. Megjegyzés. A determinisztikus 2-fejű automaták által elfogadott nyelvek osztálya valódi része a lineáris nyelvek osztályának, jele: 2detLin.

Itt jegyezzük meg, hogy a szakirodalomban egy másik automatatípus (egyszerforduló veremautomaták) is ismert, amely pontosan a lineáris nyelveket ismeri fel, ezekről is lesz szó a következő fejezetben.