Czy zdefiniowanie przejść na każdym możliwym alfabecie jest obowiązkowe w deterministycznych automatach skończonych?

Jutro jest moja prezentacja i chcę wyjaśnić moje koncepcje…

Przeczytałem to w DFA: „Dla każdego stanu należy zdefiniować przejście na wszystkie możliwe symbole (alfabet)”.

Czy dla każdego stanu zdefiniowanie przejścia na wszystkie możliwe symbole jest obowiązkowe w DFA? Jeśli nie, proszę podać jakieś przykłady?

automata finite-automata nondeterminism

— HQuser
źródło

Witamy w CS.SE! Wolimy zadać tylko jedno pytanie na post. To wygląda na dwa osobne pytania. Lepiej byłoby opublikować drugi (osobno o NFA) osobno. Czy również dokładnie przeszukałeś tę stronę i sprawdziłeś formalną definicję w swoim podręczniku? Jeśli nie, powinieneś to zrobić przed zapytaniem; i powinieneś pokazać nam w pytaniu, co znalazłeś, kiedy to zrobiłeś.

— DW

Dziękuję za ciepłe powitanie, faktycznie szukałem również na tej stronie i w Google, ale dostaję sprzeczne poglądy, co tak naprawdę mnie dezorientuje ..

— HQuser

Drugie pytanie zostało usunięte, ale można je znaleźć w historii edycji i opublikować osobno jako osobne pytanie za pomocą przycisku „Zadaj pytanie” w prawym górnym rogu. Jednak zanim zapytasz, upewnij się, że wykonałeś sugerowane badania i powiedz nam w pytaniu, jakie badania wykonałeś, w tym powiedz nam, które podręczniki przeczytałeś. Jeśli chodzi o to pytanie, nadal możesz edytować to pytanie, aby odpowiedzieć na opinie, które tu przekazałem, przeglądając formalną definicję w twoim podręczniku, włączając ją w pytaniu i pokazując swoją interpretację tej definicji.

— DW

W każdym razie wydaje się, że jest to objęte cs.stackexchange.com/q/12587/755 . Głosy społeczności, proszę: czy to duplikat?

— DW

Naprawdę nie rozumiem twojego pytania. Wygląda na to, że „przeczytałem, że definicja to X. Czy to definicja X?”

— David Richerby

Odpowiedzi:

DFA określają następujące dane:

Alfabet . $\Sigma$
Zbiorem stanów . $Q$
Początkowy stan . $q_0 \in Q$
Zestaw stanów końcowych . $F \subseteq Q$
Funkcja przejście . $\delta\colon Q \times \Sigma \to Q$

Jak widać z podpisu , określa przejście w każdym stanie dla każdego symbolu. $\delta$

— Yuval Filmus
źródło

Tyle że DFA są czasami definiowane za pomocą funkcji częściowego przejścia.

— Gilles 'SO - przestań być zły'

Masz rację, nie ma „oficjalnej” definicji DFA. Ale czytanie PO wskazuje na wpływ tej konkretnej definicji.

— Yuval Filmus

Należy wyraźnie powiedzieć, że funkcja przejścia jest całkowita.

— Ryan

Załóżmy, że DFA może mieć brakujące przejścia. Co się stanie, jeśli napotkasz symbol, dla którego nie zdefiniowano żadnej zmiany? Wynik jest niezdefiniowany. Wydaje się, że narusza to „deterministyczną” charakterystykę DFA.

Jednak przekształcenie takiego niekompletnego DFA w kompletny DFA jest banalne . Po prostu dodaj nowy stan illegali zamapuj wszelkie niezdefiniowane przejścia do tego illegalstanu. Na koniec dodaj przejścia dla każdego symbolu ze illegalstanu z powrotem do siebie. Ten illegalstan jest często nazywany stanem ujścia , ponieważ gdy dane wpadną do ujścia, nie ma możliwości wyjścia.

Z praktycznego punktu widzenia jest to rodzaj dyskusji, o ile masz dobrze zdefiniowany sposób radzenia sobie z brakującymi przejściami.

— Nathan Davis
źródło

Uwaga: Nieokreślone przejście nie powoduje, że automat jest niedeterministyczny, po prostu niekompletny. Istnieje kilka definicji DFA, które pozwalają na takie niezdefiniowane przejścia właśnie dlatego, że systematyczne ich uzupełnianie jest trywialne.

— Darkhogg

@Darkhogg, niekoniecznie się nie zgadzam, ale czy determinizm niepełnego DFA nie byłby zależny od tego, jak konkretna implementacja obsługuje te niezdefiniowane / brakujące przejścia? I czy taka implementacja nie dokończyłaby DFA?

— Nathan Davis

Nie, to nie zależy od implementacji, zależy od definicji. Jeśli zdefiniujesz DFA jako posiadające całkowitą funkcję przejścia, a następnie użyjesz funkcji częściowej, masz niezdefiniowane zachowanie i może skończyć się niedeterminizmem, ale to nie jest pewne. Jednak DFA są czasami jawnie zdefiniowane, aby używać funkcji częściowej, a gdy napotyka się niezdefiniowane przejście, zachowanie to „nie akceptuje”, kropka. Brak niedeterminizmu lub coś funky, dla jakiejkolwiek implementacji, ponieważ wynik jest zdefiniowany, nawet jeśli przejście nie jest.

— Darkhogg

BTW: możesz także dokonać transformacji odwrotnej. Weź „automat automatyczny” i usuń stan zatapiania, aby uzyskać „niekompletny automat”. Ostatecznie jedyną różnicą jest to, że cały automat zawsze jest w stanie odczytać słowo do końca, a następnie decyduje, czy je przyjmuje, czy nie, podczas gdy automat częściowy jest w stanie odrzucić niektóre słowa przed odczytaniem ich wszystkich postacie.

— Bakuriu

DFA jest często definiowany jako ograniczony typ NFA. Jeśli jest alfabetem wejściowym, a jest zbiorem stanów, struktura przejściowa NFA jest określona jako relacja , lub jako funkcja . Jeśli przyjmiemy tę ostatnią definicję, możemy powiedzieć, że NFA jest deterministyczny, jeśli dla wszystkich i , i uzupełnij jeśli , ponownie, dla wszystkich i . $\Sigma$ $Q$ $\rho \subseteq Q \times \Sigma \times Q$ $\delta : (Q \times \Sigma) \to 2^Q$ $|\delta(q,\sigma)| \leq 1$ $q\in Q$ $\sigma \in \Sigma$ $\delta(q,\sigma) \neq \emptyset$ $q \in Q$ $\sigma \in \Sigma$

Słowo jest akceptowane przez NFA, jeśli ma przebieg akceptacyjny. Automat deterministyczny ma co najwyżej jeden przebieg. Kompletny automat ma co najmniej jeden przebieg.

Niektórzy autorzy definiują automaty przycinania jako te, w których każdy stan znajduje się na drodze od stanu początkowego do końcowego. W przypadku niektórych języków nie można mieć automatów, które są zarówno wykończone, jak i kompletne. W takich przypadkach wygodnie jest utrzymać wymóg kompletności poza definicją automatu deterministycznego.

— Fabio Somenzi
źródło