Automat finit alternativ

În informatică teoretică și în special în teoria automatelor , un automat finit alternativ este o extensie a automatelor finite . Într -un automat finit obișnuit nedeterminist , un cuvânt este acceptat dacă, între statele atinse, există cel puțin o stare finală. Într-o mașină alternativă cu stări finite, valoarea unei funcții booleene pe stările atinse definește condiția de acceptare. $w$

Numele „alternativ” se bazează pe următoarea observație: cu condiția de a permite tranziții ε, două tipuri de condiții sunt suficiente pentru a exprima toate funcțiile booleene posibile asupra stărilor: dintre statele atinse, cel puțin una este finală sau bine toate sunt finale. Prin urmare, alegerile variază între o alegere existențială și o alegere universală.

Automatele finite alternative sunt utilizate pentru recunoașterea cuvintelor infinite, în teoria jocurilor , în verificarea modelelor și în logică . De asemenea, găsesc aplicații în învățarea automată .

Descriere

Există mai multe clase de automate finite care diferă prin „tipul de conexiune”: automatele deterministe , automatele nedeterministe , PLC-urile universale și automatele alternative. Un automat determinist procesează un cuvânt trecând de la o stare la alta în funcție de funcția de tranziție. Controlorul acceptă cuvântul dintr-o stare dacă statul atins după citirea acceptă sufixul . Pe de altă parte, un automat nedeterminist care citește litera într-o stare poate trece în mai multe stări, determinate de relația de tranziție. Regulatorul acceptă de dacă oricare dintre statele se poate introduce după citirea acceptă sufixul . O noțiune duală este cea a unui automat universal . În ceea ce privește un automat nedeterminist, relația de tranziție oferă, pentru o stare și o literă , un set de stări; dar interpretarea aici este că este acceptată de la stat dacă toate statele la care s-a ajuns după citire acceptă sufixul . ${\ displaystyle w = a_ {1} a_ {2} \ cdots a_ {k}}$ $w$ $q$ $a_1$ ${\ displaystyle v = a_ {2} \ cdots a_ {k}}$ $la$ $q$ $w$ $q$ ${\ displaystyle q_ {1}, \ ldots, q_ {m}}$ $a_1$ $v$ $q$ $la$ $w$ $q$ ${\ displaystyle q_ {1}, \ ldots, q_ {m}}$ $a_1$ $v$

Alternativ automatelor generaliza atat automate non-deterministe și controlere universale. Ei delegă rolul de a testa acceptarea sufixului unui cuvânt mai multor state, prin combinarea rezultatelor acestora prin conjuncții și disjuncții. De exemplu, o tranziție care de la stat , citind litera , la expresie , afirmă că cuvântul este acceptat din dacă sufixul său este acceptat din sau ambele din și . $q$ $la$ ${\ displaystyle q_ {1} \ lor (q_ {2} \ land q_ {3})}$ ${\ displaystyle w = av}$ $q$ $v$ $q_ {1}$ $q_ {2}$ $q_ {3}$

Definiție formală

O mașină de stare alternativă este alcătuită din următoarele date: ${\ displaystyle {\ mathcal {A}} = (Q, \ Sigma, q_ {0}, F, g)}$

$Î$ un set finit de stări;
$\ Sigma$ un alfabet de intrare;
$F \ subseteq Q$ un set de stări terminale;
${\ displaystyle h: 2 ^ {Q} \ to \ {0.1 \}}$ , o funcție de acceptare;
${\ displaystyle g \ colon Q \ times \ Sigma \ times \ {0.1 \} ^ {Q} \ to \ {0.1 \}}$ o funcție de tranziție.

Starea inițială obișnuită în PLC-uri este înlocuită de funcția de acceptare . Funcția de tranziție asociază o valoare booleană cu o stare , cu o literă și cu un vector de stări indexate de . Funcția este extinsă la cuvinte prin următoarele două proprietăți: $h$ $g$ $q$ $la$ $v$ $Î$ $g$

${\ displaystyle g (q, \ varepsilon, v) = v_ {q}}$ , unde este coordonata index a . ${\ displaystyle v_ {q}}$ $q$ $v$
${\ displaystyle g (q, ax, v) = g (q, a, g (x, v))}$ , unde este vectorul . ${\ displaystyle g (x, v)}$ ${\ displaystyle g (q, x, v) _ {q \ în Q}}$

Văzută ca o funcție care funcționează pe vectori de stare, funcția este, prin urmare, extinsă cu ${\ displaystyle g: \ Sigma ^ {*} \ times \ {0.1 \} ^ {Q} \ to \ {0.1 \} ^ {Q}}$

{\ displaystyle g (\ varepsilon, v) = v}

{\ displaystyle g (ax, v) = g (a, g (x, v))}

Setul de cuvinte acceptate de este ${\ mathcal {A}}$

{\ displaystyle L ({\ mathcal {A}}) = \ {w \ mid h (g (w, f)) = 1 \}}

{\ displaystyle f (q) = {\ begin {cases} 1 & {\ text {si}} q \ in F \\ 0 & {\ text {else}} \ end {cases}}}

Aici este funcția caracteristică a setului de stări terminale, reprezentat ca un vector boolean. Prin urmare, un cuvânt este acceptat dacă funcția booleană ia valoarea 1 pe vectorul care este vectorul boolean al tuturor stărilor pentru care calculul rezultă într-o stare finală. $f$ $F$ $w$ $h$ ${\ displaystyle g (w, f)}$ $q$ $w$

Exemple

Un prim exemplu

Considerăm un automat cu două stări, iar pe alfabet , setul de stări terminale este . Funcția de tranziție este dată de $q_ {1}$ $q_ {1}$ ${\ displaystyle \ Sigma = \ {a, b \}}$ ${\ displaystyle F = \ {q_ {2} \}}$

${\ displaystyle g (a, (q_ {1}, q_ {2})) = (q_ {1} \ lor {\ overline {q_ {2}}}, {\ overline {q_ {1}}} \ land {\ overline {q_ {2}}})}$

${\ displaystyle g (b, (q_ {1}, q_ {2})) = (q_ {1} \ land {\ overline {q_ {2}}}, {\ overline {q_ {1}}} \ lor q_ {2})}$

iar funcția de acceptare este

{\ displaystyle h (q_ {1}, q_ {2}) = {\ overline {q_ {1}}} \ lor q_ {2}}

Un exemplu de calcul este atunci

{\ displaystyle {\ begin {align} g (ba, f) & = g (b, g (a, f)) \\ & = g (b, g (a, (0,1)) \\ & = g (b, (0 \ lor {\ bar {1}}, {\ bar {0}} \ land {\ bar {1}})) = g (b, (0,0)) \\ & = ( 0 \ land {\ bar {0}}, {\ bar {0}} \ lor 0) = (0,1) \\\ end {align}}}

De unde

{\ displaystyle h (g (ba, f)) = h ((0,1)) = {\ bar {0}} \ lor 1 = 1}

iar cuvântul este deci acceptat. $ba$

Un al doilea exemplu

Considerăm un automat al alfabetului care are o singură stare , de asemenea starea finală. Funcția de tranziție este dată de: ${\ mathcal {A}}$ ${\ displaystyle \ Sigma = \ {a, b \}}$ ${\ displaystyle Q = \ {q \}}$

{\ displaystyle g (a, q) = {\ overline {q}}}

{\ displaystyle g (b, q) = 0}

iar funcția de acceptare este . Noi vedem asta ${\ displaystyle h (q) = q}$

{\ displaystyle g (a, 1) = 0, \ g (aa, 1) = g (a, 0) = 1, g (b, 1) = g (b, 0) = 0, g (bw, 1 ) = g (bw, 0) = 0}

Prin urmare, limba acceptată de PLC este:

{\ displaystyle L ({\ mathcal {A}}) = \ {a ^ {2n} \ mid n \ geq 0 \} \ cup \ {a ^ {2n + 1} bw \ mid n \ geq 0, w \ în \ Sigma ^ {*} \}}

Acest automat are o singură stare, în timp ce cel mai mic automat nedeterminist care recunoaște limbajul său are 2 stări, iar cel mai mic automat determinist are 4 stări.

Proprietăți și utilizări

Automatele finite nedeterministe sunt un caz special al automatelor alternative; orice limbaj rațional este, prin urmare, acceptat de un automat alternativ. În schimb, orice automat alternativ poate fi transformat într-un automat finit determinist . Prin urmare, automatele finite alternante acceptă cu precizie limbaje obișnuite. Cu toate acestea, un automat alternativ poate fi mult mai mic. Putem câștiga un exponențial trecând de la un automat nedeterminist la un automat alternativ și un dublu exponențial trecând de la un automat determinist la un automat alternativ. Terminalul exact depinde de definiția exactă a automatelor alternative. Astfel, atunci când permitem negații în formulele booleene, există un automat finit de stare alternativă pentru care cel mai mic automat finit determinist necesită stări. Când nu permitem negarea, atunci legătura este . $nu$ $2 ^ {2 ^ n}$ ${\ displaystyle 2 ^ {2 ^ {n} / {\ sqrt {n}}}}$

Automatele alternante, pe cuvinte infinite, sunt definite într-un mod analog, luând ca condiție de acceptare, de exemplu, condiția automatelor Büchi . Automatele alternative recunosc aceleași limbaje infinite de cuvinte ca și automatele Büchi nedeterministe, dar alternanța poate face automatele mai mici exponențial.

Variații

Există diferite variații în definiția alternativelor automate finite. Ele nu modifică puterea de exprimare, dar pot fi mai mult sau mai puțin ușor de definit și mai mult sau mai puțin ușor de implementat. Mai presus de toate este apreciată flexibilitatea structurii combinatorii a unui automat alternativ: simplifică considerabil translația specificațiilor proprietăților în automate, care este baza algoritmilor de verificare a modelului . PLC-urile sunt utilizate pentru specificarea și verificarea programelor. Când un program este definit relativ la un set P de propoziții, fiecare stare dintr-o execuție a programului corespunde unei părți din P , și anume setului de propoziții care sunt adevărate în acea stare. O execuție a programului definește astfel un cuvânt finit sau infinit pe alfabetul părților lui P , iar programul în sine oferă un set de cuvinte care pot fi definite de un automat. La fel, specificația unui program care descrie posibilele calcule poate fi văzută ca un limbaj de cuvinte pe alfabetul părților din P și, prin urmare, poate fi definită de un automat. Astfel, întrebările despre programe se rezumă la întrebări despre automate. De exemplu, întrebările privind satisfacția specificației și corectitudinea unui program se rezumă la întrebări precum testul de vid sau problema de includere pentru limbaje formale. Traducerea specificațiilor către automate are grijă de aspectele logice și deplasează dificultățile combinatorii către probleme de teorie combinatorie.

O variantă a automatelor constă în a nu permite negații. Aceasta este opțiunea aleasă în anumite lucrări privind învățarea limbilor obișnuite.

O variantă în însăși definiția automatelor constă în introducerea unei stări inițiale în locul funcției de evaluare . Condiția acceptării $q_0$ $h$

{\ displaystyle h (g (w, f)) = 1}

este înlocuit de condiția, mai restrictivă în aparență, a

{\ displaystyle g (q_ {0}, w, f) = 1}

O altă alternativă , mai pronunțată, este definirea automatelor alternante după cum urmează: Setul de stări este împărțit în două părți, stările existențiale și universale . Ideea din spatele acestui lucru este că tranzițiile care părăsesc o stare de sunt interpretate ca tranziții sau , iar tranzițiile care părăsesc o stare de ca tranziții și . Sintaxic, aceasta este singura diferență între automatele alternante și automatele nedeterministe. $Î$ ${\ displaystyle Q _ {\ există}}$ ${\ displaystyle Q _ {\ forall}}$ ${\ displaystyle Q _ {\ există}}$ ${\ displaystyle Q _ {\ forall}}$

Sau , cu un automat finit obișnuit nedeterminist. Un cuvânt este acceptat dintr-o stare dacă este o stare finală și este cuvântul gol, sau dacă pentru o literă și un cuvânt , și dacă fie: ${\ displaystyle {\ mathcal {A}} = (Q, \ Sigma, s, F, \ delta)}$ ${\ displaystyle Q = Q _ {\ există} \ cup Q _ {\ forall}}$ $w$ $q$ $q$ $w$ ${\ displaystyle w = av}$ $la$ $v$

${\ displaystyle q \ în Q _ {\ există}}$ , și este acceptat de cel puțin unul dintre statele din sau $v$ $\ delta (q, a)$
${\ displaystyle q \ în Q _ {\ forall}}$ , și este acceptat de toate statele din . $v$ $\ delta (q, a)$

Limbajul acceptat de un astfel de automat este setul de cuvinte acceptate din starea inițială.

Funcția de tranziție definită mai sus este înlocuită de o funcție mai simplă care asociază cu o stare și o literă o formulă booleană pe : Pentru o stare , o literă și , funcția ia valoarea . ${\ displaystyle g \ colon Q \ times \ Sigma \ times \ {0.1 \} ^ {Q} \ to \ {0.1 \}}$ ${\ displaystyle g \ colon Q \ times \ Sigma \ to \ mathbb {B} (Q)}$ $q$ $la$ $Î$ $q$ $la$ ${\ displaystyle \ delta (q, a) = \ {q_ {1}, \ ldots, q_ {k} \}}$ $g$ ${\ displaystyle g (q, a) = {\ begin {cases} q_ {1} \ lor q_ {2} \ lor \ cdots \ lor q_ {k} & {\ text {si}} q \ in Q _ { \ există} \\ q_ {1} \ land q_ {2} \ land \ cdots \ land q_ {k} și {\ text {si}} q \ în Q _ {\ forall} \ end {cases}}}$

Note și referințe

În articolul Chandra, Kozen și Stockmeyer, 1981 , există o stare inițială.
Chandra, Kozen și Stockmeyer, 1981 .
Kupferman și Vardi 2001 .
Angluin, Eisenstat și Fisman 2015 .
Kumar, Automate alternative .

Bibliografie

Articol fondator

Ashok K. Chandra , Dexter C. Kozen și Larry J. Stockmeyer, „ Alternation ” , Jurnalul ACM , vol. 28, n o 1,Ianuarie 1981, p. 114-133 ( DOI 10.1145 / 322234.322243 ).

Alte articole

Orna Kupferman și Moshe Y. Vardi, „ Automat alternativ slab și golul automatelor copacilor ”, Lucrările celui de-al treizecelea simpozion anual ACM pe teoria calculelor (STOC '98) ,1998, p. 224-233 ( DOI 10.1145 / 276698.276748 , citiți online )
Orna Kupferman și Moshe Y. Vardi , „ Automatele slabe alternante nu sunt atât de slabe ”, ACM Transactions on Computational Logic , vol. 2 n o 3,2001, p. 408-429 ( DOI 10.1145 / 377978.377993 , citiți online )
Dana Angluin, Sarah Eisenstat și Dana Fisman, „ Învățarea limbilor regulate prin automate alternativ “, Proceedings al douăzeci și patra conferință comună internațională asupra inteligenței artificiale (IJCAI 2015) ,2015, p. 3308-3314 ( citiți online )

Clase

K. Narayan Kumar, „ Automate alternante ” , Note despre automate, logică, jocuri și algebră , Chennai Mathematical Institute, Chennai .
Pascal Raiola, „ Introducere în automatele finite alternative ” , Teoria automatelor - Ingineria software-ului , Informatik Universität Freiburg,2013.

Articole similare