Pytania otagowane jako automata-theory

Teoria automatów, w tym maszyny abstrakcyjne, gramatyki, parsowanie, wnioskowanie gramatyczne, przetworniki i techniki skończone

1
Zwykły język, który rozróżnia dwa deterministyczne CFG
Załóżmy, że masz dwa deterministyczne automaty wypychające, które rozpoznają języki i B , i chcesz ustalić, czy istnieje regularny język R, taki jak A ⊆ R i R ∩ B = ∅ . Zasadniczo wyzwanie polega na ustaleniu, czy istnieje DFA, który może rozpoznać, który z dwóch języków pochodzi z …
2
Generator pseudolosowy dla automatów skończonych
Niech będzie stałą. Jak możemy w sposób wiarygodny skonstruować pseudolosowy generator, który oszuka -state skończone automaty?dreddredd Tutaj automat skończony -state ma węzły, węzeł początkowy, zestaw węzłów reprezentujących stany akceptacji i dwie skierowane krawędzie oznaczone 0, 1 wychodzące z każdego węzła. Zmienia stan w naturalny sposób, odczytując dane wejściowe. Biorąc pod …
1
Minimalizowanie resztkowych automatów skończonych
Automaty szczątkowego stanu skończonego (RFSA, zdefiniowane w [DLT02]) to NFA, które mają kilka fajnych cech wspólnych z DFA. W szczególności zawsze istnieje kanoniczny minimalny rozmiar RFSA dla każdego zwykłego języka, a język rozpoznawany przez każdy stan w RFSA jest resztkowy, podobnie jak w DFA. Jednakże, podczas gdy minimalne stany DFA …
1
Czy istnieje książka / artykuł przeglądowy przedstawiający hierarchie klas językowych, właściwości zamknięcia itp
Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp. Zastanawiam się, czy ktokolwiek wie o dobrej książce lub opracowaniu, które opisuje właściwości tych języków. Większość tego, na …
2
Ekspresyjność Büchi vs CTL (*)
Jaki jest związek między ekspresyjnością LTL , Büchi / QPTL , CTL i CTL * ? Czy możesz podać odniesienia, które obejmują tak wiele logiki czasowej, jak to możliwe (szczególnie między czasem liniowym a rozgałęzieniem)? Idealny byłby diagram Venna z logiką czasową i pewnymi praktycznymi właściwościami jako przykładami. Na przykład: …
2
Czy automaty wielopłytkowe mogą decydować o wszystkich deterministycznych językach kontekstowych?
MPA (automat multipebble) to 2DFA (dwukierunkowy deterministyczny automat skończony), który może wykorzystywać dowolną liczbę otoczek (w rzeczywistości najwyżej otoczki na danym wejściu - wejście jest zapisywane na taśmie między dwoma końcami -markery jak ). Podczas obliczeń MPA może wykryć, czy symbol pod głową ma kamyk, a następnie może umieścić kamyk …
3
„Prosty” język poza
Szukam języka L o następujących właściwościach: L nie powinien być pozbawiony kontekstu. Uzupełnienie L nie powinno być pozbawione kontekstu. (Wszystko, co widzisz w podręcznikach jako główny przykład języków bezkontekstowych, wydaje się nie spełniać tego drugiego wymogu). L nie powinien być zbyt trudny. Na przykład wiem, że nierozstrzygalne języki spełniają dwa …
2
Czy dany język regularny zawiera nieskończony podzbiór bez prefiksów?
Zestaw słów nad skończonym alfabetem nie zawiera prefiksu, jeśli nie ma dwóch odrębnych słów, w których jedno jest prefiksem drugiego. Pytanie brzmi: Jaka jest złożoność sprawdzania, czy zwykły język podany jako NFA zawiera nieskończony podzbiór bez prefiksów? Odpowiedź (z powodu Michaiła Rudoya, tutaj poniżej) : Można to zrobić w czasie …
3
Czy istnieją niekonstruktywne dowody na istnienie „małych” maszyn Turinga / NFA?
Po przeczytaniu powiązanego pytania dotyczącego niekonstruktywnych dowodów istnienia algorytmów, zastanawiałem się, czy istnieją metody pokazania istnienia „małych” (powiedzmy, stanowych) maszyn obliczeniowych bez ich budowania. Formalnie: załóżmy, że otrzymaliśmy język i naprawiliśmy jakiś model obliczeniowy (NFA / maszyna Turinga itp.).L ⊆ Σ∗L⊆Σ∗L\subseteq \Sigma^* Czy istnieją jakieś niekonstruktywne wyniki istnienia pokazujące, że …
1
Czy jednokierunkowe przemienne automaty z jednym licznikiem rozpoznają niektóre jednoargumentowe nieregularne języki?
Jednokierunkowe naprzemienne automaty wypychające (1APDA) mogą rozpoznać dowolny język w (Alternacja autorstwa Chandra, Kozen i Stockmeyer, 1981) . Zastępując przechowywanie w dół 1APDA przez licznik, możemy uzyskać jednokierunkowy automat na przemian z jednym licznikiem (1ACA). Moje pytanie dotyczy 1ACA w językach jednoargumentowych.D T.jaM.mi( 2O ( n ))reT.jaM.mi(2)O(n)) DTIME(2^{O(n)}) Czy 1ACA …
1
Jakie algorytmy istnieją do budowy DFA, który rozpoznaje język opisany przez dane wyrażenie regularne?
Wszystkie moje podręczniki używają tego samego algorytmu do tworzenia DFA, biorąc pod uwagę regex: Najpierw utwórz NFA, który rozpoznaje język regex, a następnie, używając konstrukcji podzbioru (aka „powerset”), przekonwertuj NFA na równoważny DFA ( opcjonalnie minimalizując DFA). Kiedyś słyszałem też, jak profesor wspomina o istnieniu innych algorytmów. Czy ktoś o …
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.