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...
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...
Powiedzmy, że mamy język , ale nie wiemy, jakie ciągi znaków są w rzeczywistości częścią tego języka. Wszystko, co ma, to skończony widok języka: skończony zestaw ciągów A \ subseteq L , o których wiadomo, że są w języku, oraz skończony zestaw ciągów B \ subseteq (\ Sigma ^ * \ setminus L), które...
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...
Czy ktoś może podać przykład dwóch równoważnych (rozpoznających ten sam język) minimalnych niedeterministycznych automatów (NFA), które nie są
Zainspirowany tym pytaniem ciekawi mnie: Jaka jest najgorsza złożoność sprawdzania, czy dany DFA akceptuje ten sam język jako dane wyrażenie regularne? Czy to jest znane? Można mieć nadzieję, że ten problem występuje w P - że algorytm ma wielomian wielkości
Szukam pracy ankietowej na temat ważnych pojęć w dziedzinie automatów kwantowych. Znalazłem teorię automatów kwantowych - recenzję Hirvensalo, ale brzmi to zbyt zwięźle, by zrozumieć ten temat. Czy istnieje dość kompleksowa ankieta na temat automatów kwantowych? Czy mógłbyś również wskazać mi...
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...
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 danego łańcucha,...
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...
Szukam ogólnej techniki, która może mi pomóc udowodnić nie tylko, że automaty Buchi są bardziej ekspresyjnym modelem niż LTL, ale że konkretna formuła może / nie może być wyrażona w LTL. Na przykład „ występuje co najmniej na parzystych pozycjach” można opisać następującymi automatami Buchi: ( q 0...
Czy można zbudować algorytm, który przyjmuje jako dane wejściowe automat do przesuwania wraz z obietnicą, że język zaakceptowany przez ten automat L ( M ) jest deterministycznym językiem bezkontekstowym i wysyła deterministyczny automat do przesuwania N, który akceptuje dokładnie zaakceptowany...
To pytanie jest związane z ostatnim pytaniem przez Janoma . tło Programowania więzów, A regularne globalny ograniczenie docc przez domeny reDD jest parą ( s , M)(s,M)(s, M) z sss krotki zmiennych (zakres, w) oraz M.MM DFA na obszarze reDD . Przypisanie θθ\theta do sss spełnia warunek docc jeśli...
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ś...
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...
Czy istnieje 2DFA ze stanami (gdzie n nie jest łatwe, powiedzmy co najmniej 4), które wymagają co najmniej 2 n stanów do symulacji przy użyciu dowolnego DFA?nnnnnn2)n2n2^n Dwukierunkowy DFA (2DFA) jest deterministyczny automat skończony-państwo, które może poruszać się tam iz powrotem na jej...
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...
Aktualizacja: Wygląda na to, że ten problem został niedawno zbadany i rozwiązany, zobacz ten artykuł wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton A także tę ankietę: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Załóżmy, że zamiast zwykłego zestawu słów {0,1} *, nasze słowa...
DFA lub NFA odczytuje ciąg wejściowy z pojedynczą głowicą, przesuwając się od lewej do prawej. Naturalne wydaje się zastanawianie się nad maszynami o skończonym stanie, które mają wiele głowic , z których każda porusza się po wejściu od lewej do prawej, ale niekoniecznie w tym samym miejscu na...
Jestem zainteresowany niewielkim uogólnieniem DFA. Jak zwykle mamy ustawiony stan , skończony alfabet , działanie zdefiniowane na przez i stan początkowy ; lecz w zwykłym zestawem terminali wziąć rodziny podzbiorów . Wielojęzyczny DFA jest wtedy krotkąQQQΣΣ\SigmaΣ∗Σ∗\Sigma^*QQQδ:Q×Σ→Qδ:Q×Σ→Q\delta...