Czy w DFA każdy stan ma przejście na każdy symbol alfabetu?

Jeśli nie, to co to znaczy, że dla jakiegoś stanu $q$ i jakiegoś symbolu $a$ , $\delta(q, a)$ nie istnieje?

Wygląda na to, że natknąłeś się na sporną kwestię. Najwyraźniej informatycy lubią się kłócić. Z pewnością lubię się kłócić, więc proszę!

Moja odpowiedź jest jednoznaczna: nie. Deterministyczne skończone automaty nie potrzebują przejścia z każdego stanu dla każdego symbolu. Kiedy $\delta(q,a)$ nie istnieje, oznacza to po prostu, że DFA nie akceptuje ciągu wejściowego.

Chociaż możesz utworzyć definicję DFA, która wymaga istnienia $\delta(q,a)$ , po prostu nie jest tak, że brakujące przejście powoduje, że wynikowa struktura (jakkolwiek to nazwiesz) nie jest deterministyczna, ponieważ wielu komentujących jest roszczenie Jeśli uczęszczasz na teorię automatów, następnym tematem będą języki bezkontekstowe i automaty push-down, w których rozróżnienie między automatami niedeterministycznymi i deterministycznymi jest krytyczne, i musisz użyć poprawnej definicji niedeterminizmu.

Niedeterminizm wiąże się z więcej niż jednym przejściem prawnym.

Myślę, że wszyscy zgadzamy się z następującą definicją Wikipedii (która pokażę za chwilę jest nieco niejednoznaczna):

Deterministyczny automat skończony $M$ jest 5-krotną ( $Q$ , $\Sigma$ , $\delta$ , $q_0$ , $F$ ), składającą się z

1. skończony zestaw stanów ( $Q$ )
2. skończony zestaw symboli wejściowych zwanych alfabetem ( $\Sigma$ )
3. funkcja przejścia ( $\delta : Q \times \Sigma \rightarrow Q$ )
4. stan początkowy ( $q_0 \in Q)$
5. zestaw stanów akceptacji ( $F \subseteq Q$ ).

Niech $w = a_1 a_2 \cdots a_n$ jest łańcuchem na alfabet $\Sigma$ . Automat $M$ przyjmuje ciąg $w$ jeśli sekwencja stanów, $r_0, r_1, \ldots, r_n$ , istnieje w $Q$ z następującymi warunkami:

1. $r_0 = q_0$
2. $r_{i+1} = \delta(r_i, a_{i+1})$ , dla$i = 0, \ldots, n−1$
3. $r_n \in F$ .

Dwuznaczność i kontrowersje dotyczą definicji funkcji przejścia $\delta$ (liczba „3” na pierwszej wypunktowanej liście). Wszyscy zgadzamy się, że to, co odróżnia DFA od NFA, to to, że $\delta$ jest funkcją, a nie relacją . Ale czy $\delta$ jest funkcją częściową czy całkowitą ?

Definicja DFA działa dobrze, jeśli $\delta$ jest funkcją częściową. Biorąc pod uwagę ciąg wejściowy, jeśli osiągniesz stan $q_i$ za pomocą symbolu wejściowego $a_j$ którym nie ma następnego stanu, automaty po prostu nie akceptują.

Ponadto, gdy rozszerzysz tę definicję, aby utworzyć definicję automatów push-down, będziesz musiał rozróżnić, że automaty push-down z funkcjami przejściowymi, które są funkcjami częściowymi, są klasyfikowane jako deterministyczne, a nie niedeterministyczne.

$\delta$

1. $q_{\mathrm{error}}$
2. $(q_i, s_j)$$\delta$$\delta(q_i, s_j) = q_{\mathrm{error}}$

$\delta$

Edycja, styczeń 2019 r

Komentator @Alex Smart słusznie krytykuje mnie za to, że nie podawałem referencji ani nie wyjaśniałem, dlaczego powinniśmy się tym przejmować. Więc oto idzie:

Powodem, dla którego dbamy o dokładną definicję determinizmu kontra niedeterminizm, jest to, że niektóre klasy automatów niedeterministycznych są silniejsze niż ich deterministyczni kuzyni, a niektóre klasy automatów niedeterministycznych nie są silniejsze niż ich deterministyczni kuzyni. W przypadku automatów skończonych i maszyn Turinga warianty deterministyczne i niedeterministyczne mają równoważną moc. W przypadku automatów wypychających istnieją języki, w których rozróżnienie jest ważne: istnieją NPDA, które akceptują język, i żadna DPDA nie akceptuje języka. W przypadku automatów z ograniczeniami liniowymi pytanie jest (lub było ostatnio sprawdzane) otwarte. Wzrost mocy NPDA w porównaniu z DPDA wynika z dopuszczenia wielu przejścia, a nie z zamiany funkcji przejścia z funkcji całkowitej na funkcję częściową.

Książki ze społeczności kompilatorów:

Aho i Ullman, Principles of Compiler Design , 1977: Najpierw definiuje NFA (strona 88) z relacją przejścia, a następnie (s. 90-91):

$\epsilon$$s$$a$$a$$s$

Aho, Sethi i Ullman, Kompilatory, zasady, techniki i narzędzia , przedruk 1988, są podobne, najpierw definiują NFA z relacją przejścia, a następnie (s. 115-116):

$a$$s$

(Zauważ, że w komentarzach @Alex Smart mówi: „smok specjalnie wspomina, że ​​funkcja jest całkowita.” Zakładam, że mówi o późniejszym wydaniu ze współautorem Lamem, do którego obecnie nie mam dostępu. )

Appel, Modern Compiler Implementation in Java , 1988 (s. 22):

W deterministycznym automacie skończonym (DFA) żadne dwie krawędzie wychodzące z tego samego stanu nie są oznaczone tym samym symbolem.

Następnie Appel wyjaśnia, że ​​używając DFA do rozpoznawania najdłuższych dopasowań, jawnie wykorzystujemy brakujące przejścia, aby zdecydować, kiedy przerwać (s. 23):

po osiągnięciu stanu martwego (stanu nieskończonego bez przejść wyjściowych) zmienne [które rejestrują najdłuższe dopasowanie, jakie do tej pory widzieliśmy] informują, który token został dopasowany i gdzie się zakończył.

Książki ze społeczności teorii przełączania:

Kohavi, Switching and Finite Automata Theory, 2 / e , 1978, s. 1. 611 mówi:

Ponieważ diagram stanów opisuje maszynę deterministyczną , następne przejście stanu musi być określone jednoznacznie przez stan obecny i aktualnie skanowany symbol wejściowy.

Ja zazwyczaj interpretować jednoznacznie oznacza „dokładnie jeden”, a nie „nie więcej niż jeden”. (Tzn. Kohavi wydaje się mówić, że determinizm wymaga całkowitej funkcji)

Książki ze społeczności teorii teorii obliczeń:

Tutaj wydaje się, że bardziej powszechne jest definiowanie DFA przed NFA i wymaganie, aby DFA miały całkowitą funkcję przejścia, ale następnie definiowanie NPDA przed DPDA i definiowanie „determinizmu” jako ograniczenia relacji przejścia do braku nie więcej niż -jeden wpis dla każdej pary stan / symbol.

Dotyczy to Hopcroft i Ullman, 1979, Lewis i Papadimitriou, 1981, a zwłaszcza Sipser, 2006, którzy używają definicji DFA pedagogicznie, aby wprowadzić dokładne definicje formalne oraz wyjaśnić ich znaczenie i wyraźnie powiedzieć (str. 36):

$\delta$

$s\times\Sigma$

Co ciekawe, Rabin i Scott również definiują niedeterministyczne automaty skończone w kategoriach funkcji całkowitej! Strona 120, definicja 9:

$M$$S\times\Sigma$$S$

To znaczy: całkowita funkcja przejścia nie czyni deterministycznego systemu!

Sipser 2006 śledzi Rabina i Scotta i wykorzystuje całkowitą funkcję przejścia ze stanów / symboli do zestawu mocy stanów w swoich definicjach niedeterministycznych automatów skończonych, niedeterministycznych PDA i niedeterministycznych maszyn Turinga, ale pomija temat deterministyczny PDA.

Zarówno Hopcroft, jak i Ullman, 1979, oraz Lewis i Papadimitriou, 1981, używają funkcji cząstkowych w swoich definicjach deterministycznych PDA. Najpierw definiują NPDA za pomocą relacji przejściowych, a następnie, kiedy dochodzą do PDA, Lewis i Papadimitriou mówią (s. 135),

Automat przesuwania jest deterministyczny , mówiąc intuicyjnie, jeśli dla każdej konfiguracji istnieje co najwyżej jedno przejście.

Podczas gdy Hopcroft i Ullman mówią (s. 112):

PDA ... jest deterministyczny w tym sensie, że co najwyżej jeden ruch jest możliwy z dowolnego ID.

$\delta(q,a)$$q \in Q$$a\in \Sigma$$Q$$\Sigma$

$\varepsilon$

Pod względem obliczalności NFA są równoważne DFA - istnieje algorytm do konwersji z NFA na DFA, a DFA jest po prostu trywialnie NFA, który nie używa niedeterminizmu, więc oba definiują zestaw zwykłych języków.

Istnieją definicje DFA na wzór

$A$$|\delta(q,a)| \leq 1$$q$$a$$\delta(q,\varepsilon) \neq \emptyset$$\delta(q,a) = \emptyset$$a \in \Sigma$$A$

W takim przypadku nie potrzebujesz wszystkich przejść. Jeśli automat nie ma przejścia pasującego do następnego symbolu wejściowego, odrzuca.

Miło jest wykazać, że obie definicje są równoważne pod względem tego, które języki mogą być akceptowane.

W definicji DFA każdy stan powinien mieć cały alfabet w £. Na przykład, jeśli £ = {a, b, c} i Q = {q0, q1, q2}, wszystkie te stany powinny mieć wszystkie symbole a, b, c, które przechodzą do innego stanu lub tego samego stanu.

Najprostszą odpowiedzią jest dodanie martwego stanu dla lewego symbolu . Podobnie jak w przypadku konwersji z NFA do DFA, otrzymujemy przejście Φ dla niektórych symboli, co oznacza, że ​​tworzymy dla niego stan martwy.