Przemienny automat skończony

W teorii automatów zmienny automat skończony ( AFA ) jest niedeterministycznym automatem skończonym , którego przejścia dzielą się na przejścia egzystencjalne i uniwersalne . Na przykład niech A będzie automatem przemiennym .

Dla przejścia egzystencjalnego ${\ Displaystyle (q, a, q_ {1} \ vee q_ {2})}$ A niedeterministycznie wybiera przełączenie stanu na ${\ displaystyle q_ {1}}$ lub ${\ Displaystyle q_ {2}}$ , czytając . Tym samym zachowując się jak zwykły niedeterministyczny automat skończony .
Dla uniwersalnego przejścia ${\ Displaystyle (q, a, q_ {1} \ klin q_ {2})}$ , A przenosi się do ${\ Displaystyle q_ {1}}$ ${\ displaystyle q_ {2}}$ , czytając a , symulując zachowanie maszyny równoległej.

Należy zauważyć, że ze względu na uniwersalną kwantyfikację przebieg jest reprezentowany przez drzewo przebiegów . A akceptuje słowo w , jeśli istnieje drzewo uruchamiania na w takie, że każda ścieżka kończy się stanem akceptacji.

Podstawowe twierdzenie mówi, że dowolny AFA jest równoważny deterministycznemu automatowi skończonemu (DFA), stąd AFA akceptują dokładnie języki regularne .

Często używanym modelem alternatywnym jest ten, w którym kombinacje boolowskie są w rozłącznej postaci normalnej , tak że np. $) {\$ ${\ Displaystyle \ {\ {q_ {1} \}$ ${3}) }$ Displaystyle q_ {1} \ vee (q_ {2} \ klin . Stan tt ( prawda ) jest w tym przypadku reprezentowany przez , a ff ( fałsz ) przez . $\ pusty zbiór}}$ $Displaystyle \ {$ . Ta reprezentacja jest zwykle bardziej wydajna.

Naprzemienne automaty skończone można rozszerzyć, aby akceptowały drzewa w taki sam sposób, jak automaty drzewne , uzyskując naprzemienne automaty drzewne .

Definicja formalna

Przemienny automat skończony (AFA) to 6-krotka , ${\ Displaystyle (S (\ istnieje), S (\ forall), \ Sigma ,\delta ,P_{0},F)}$ , gdzie

${\ Displaystyle S (\ istnieje)}$ to skończony zbiór stanów egzystencjalnych. Również powszechnie przedstawiane jako ${\ Displaystyle S (\ vee)}$ .
${\ Displaystyle S (\ forall)}$ to skończony zbiór stanów uniwersalnych. Również powszechnie przedstawiane jako ${\ Displaystyle S (\ klin)}$ .
${\ Displaystyle \ \ Sigma}$ to skończony zbiór symboli wejściowych.
${\ Displaystyle \ \ delta}$ to zbiór relacji przejściowych do następnego stanu ${\ Displaystyle (S(\exists )\cup S(\forall ))\times (\Sigma \cup \{\varepsilon \})\to 2^{S(\exists )\cup S(\forall )}}$ .
${\ Displaystyle \ P_ {0}}$ jest stanem początkowym (początkowym), takim, że ${\ Displaystyle P_ {0} \ w S (\ istnieje) \ kubek S (\ na zawsze )}$ .
$\$ $subseteq S (\ istnieje) \ kubek S (\ forall$ ) .

Model ten wprowadzili Chandra , Kozen i Stockmeyer .

Złożoność stanu

Chociaż AFA może przyjąć dokładnie języki regularne , różnią się one od innych typów automatów skończonych zwięzłością opisu, mierzoną liczbą ich stanów.

Chandra i in. udowodnił $,$ że konwersja $AFA$ na równoważny DFA wymaga w najgorszym Kolejna konstrukcja Fellaha, Jürgensena i Yu. konwertuje AFA ze $)$ na niedeterministyczny automat skończony (NFA ze stanami do ${\ displaystyle 2 ^ {n}}$ , wykonując podobny rodzaj konstrukcji powerset, jak używany do transformacji NFA do DFA.

Złożoność obliczeniowa

Problem z członkostwem pyta, biorąc pod uwagę $displaystyle$ $}$ słowo $akceptuje$ czy ZA { $w$ . Ten problem jest P-zupełny . Dzieje się tak nawet w przypadku alfabetu singletonowego, tj. gdy automat akceptuje język jednoargumentowy .

Problem niepustości (czy język wejściowego AFA jest niepusty?), problem uniwersalności (czy dopełnienie języka wejściowego AFA jest puste?) i problem równoważności (czy dwa wejściowe AFA rozpoznają ten sam język ) są PSPACE-kompletne dla AFA.

Pippenger, Mikołaj (1997). Teorie obliczalności . Wydawnictwo Uniwersytetu Cambridge . ISBN 978-0-521-55380-3 .