Pytania otagowane jako automata-theory

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

1
Biorąc pod uwagę PDA M taki, że L (M) jest w DCFL konstruuj DPDA N, tak że L (N) = L (M)
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 język przez M ?MMML(M)L(M)L(M)N.NNM.MM Równoważne problemu byłoby skonstruować algorytm, który …
1
Gry Ehrenfeucht-Fraïssé (w rzeczywistości Ajtai-Fagin) dla zwykłych języków.
Immerman (Complexity opisowa, 1999) przedstawia gry EF dla egzystencjalnej monadycznej drugiego rzędu (Gry Ajtai-Fagin) na stronie 127. Jak MSO na słowach jest odpowiednikiem zwykłych języków, gra może być napisany w sposób następujący.∃∃\exists Język jest regularny tylko wtedy, gdy Delilah nie ma strategii wygranej w następującej grze: 1. Samson wybiera , …
2
2DFA, która wymaga wielu stanów w równoważnym DFA?
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 taśmie tylko do odczytu wejścia, w przeciwieństwie …
1
Czy jest rozstrzygalne, czy długość wyjściowa przetwornika jest ograniczona długością wejściową?
Rozważane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff .[ T ] y x x [ T ] yT.TT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pytanie: Czy można rozstrzygnąć następujący problem: Biorąc pod uwagę: Przetwornik …
2
Rozdzielanie list słów
Istnieje problem otwarty w językach formalnych znany jako problem oddzielający; co jest krótko określone jako dane dwa odrębne ciągi o długości , jak duży jest DFA, aby je „rozdzielić”, co oznacza przyjęcie jednego ciągu, ale odrzucenie drugiego.nnn Oto kilka odpowiednich dokumentów 1 , 2 . (Mam jeszcze kilka, ale nie …
2
Minimalizowanie automatów akceptujących słowa (tj. Nieskończone słowa)
Jakie jest standardowe podejście do minimalizacji Büchi-Automata (lub także Müller-Automata)? Przeniesienie zwykłej techniki ze słów skończonych, tj. Ustawienie dwóch stanów na równe, jeśli słowa „wyczerpania” stanów, które są akceptowane, są takie same, nie zadziała. Na przykład rozważmy, że Büchi-Automoton akceptuje wszystkie słowa o nieskończonej liczbie a, składające się z dwóch …
2
Taksonomia znaczących automatów wyrażeń regularnych
Próbuję opracować systematykę algorytmów do przekształcania wyrażeń regularnych w automaty, aby przeprowadzić pewne testy empiryczne ich właściwości złożoności w określonych domenach. Znam kilka „większych” nazw, np. Thompson „Algorytm wyszukiwania wyrażeń regularnych”, Thompson, 1968 Glushkov „Nowy algorytm kwadratowy do przekształcenia wyrażenia regularnego w automat”, Ponty i in. al. 1996 Antimirov „Częściowe …
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.