Pytania otagowane jako finite-automata

Pytania dotyczące automatów skończonych, elementarnego modelu automatów ze skończoną pamięcią. Jest to odpowiednik zwykłych języków i podstawa dla wielu bardziej złożonych modeli.

3
Algorytm Brzozowskiego do minimalizacji DFA
Algorytm minimalizacji DFA Brzozowskiego buduje minimalny DFA dla DFA poprzez:GGG odwrócenie wszystkich krawędzi w , czyniąc stan początkowy stanem akceptacyjnym, a stanami początkowymi początkowymi, aby otrzymać NFA N ' dla języka odwrotnego,GGGN′N′N' używając konstrukcji powerset, aby uzyskać dla języka odwrotnego,G′G′G' odwrócenie krawędzi (i zamiana początkowej akceptacji) w aby uzyskać NFA …
1
Wykładniczy podział między NFA i DFA w obecności związków
Ostatnio zadano interesujące pytanie, a następnie usunięto. W przypadku zwykłego języka jego złożoność DFA jest wielkością minimalnej akceptacji DFA, a złożoność NFA jest wielkością minimalnej akceptacji NFA. Dobrze wiadomo, że istnieje wykładnicza separacja między tymi dwoma złożonościami, przynajmniej wtedy, gdy wielkość alfabetu jest nieograniczona. W istocie, pod język nad alfabetu …
7
Dlaczego NFA nazywany jest niedeterministyczny?
Mam na myśli to [zabawne] pytanie. Dlaczego niedeterministyczny automat skończony nazywa się niedeterministyczny, podczas gdy my definiujemy przejścia dla danych wejściowych. Cóż, mimo że istnieje wiele przejść i epsilon , są one zdefiniowane, co oznacza, że ​​maszyna jest deterministyczna dla tych przejść. Co oznacza, że ​​jest deterministyczny.
1
Monadyczna logika drugiego rzędu dla manekinów
Jestem programistą z automatami, ale nie logiką. Przeczytałem w artykułach, że te dwa są ze sobą ściśle powiązane. Deterministyczne automaty skończone (DFA), automaty drzewa i automaty z widocznym przesunięciem w dół są powiązane z logiką Monadic drugiego rzędu (MSO). Chociaż rozumiem automaty i ludzie (w dokumentach) próbowali mi wyjaśnić związek …
2
Jak słowo „produkcja” stało się synonimem słowa „reguła” w kontekście informatyki?
Studiuję języki formalne i systemy baz produkcyjnych (systemy baz reguł) i jestem trochę zdezorientowany, dlaczego te dwa słowa „produkcja” i „reguła” oznaczają to samo w tak wielu kontekstach w informatyce. W języku angielskim nie wydają się oznaczać tego samego. Nie jestem rodzimym językiem angielskim, ale wiem, że reguła odnosi się …
3
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?
3
Jak utworzyć DFA z wyrażenia regularnego bez użycia NFA?
Celem jest utworzenie DFA z wyrażenia regularnego, a użycie opcji „Regular exp> NFA> Konwersja DFA” nie jest opcją. Jak należy to zrobić? Zadałem to pytanie naszemu profesorowi, ale powiedział mi, że możemy korzystać z intuicji i uprzejmie odmówił podania jakichkolwiek wyjaśnień. Więc chciałem cię zapytać. Opcja „Regular exp> NFA> Konwersja …
2
Jaka jest złożoność problemu pustki dla dwukierunkowych DFA?
Zastanawiam się, jaka jest złożoność czasowa określania pustki dla dwukierunkowych DFA? Oznacza to, że skończone automaty mogą przesuwać się wstecz na swojej taśmie wejściowej tylko do odczytu. Według Wikipedii są one równoważne DFA, chociaż równoważny DFA może być wykładniczo większy. Znalazłem złożoność stanu dla ich uzupełnień i skrzyżowań, ale nie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.