Pytania otagowane jako fl.formal-languages

języki formalne, gramatyka, teoria automatów

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
Wprowadzenie do automatów probabilistycznych
Gdzie mogę znaleźć wprowadzenie do automatów probabilistycznych i co one rozpoznają (niektóre funkcje od słów do )? Czy istnieje standardowy termin określający takie funkcje, które są rozpoznawane przez automaty probabilistyczne, analogiczne do „zwykłych języków”, dla których rozpoznają deterministyczne automaty skończone (DFA)?[ 0 , 1 ][0,1][0,1] Szukam czegoś, co podchodzi do …
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 …
1
Odwracalne plandeki Turinga?
To pytanie o to, czy istnieją jakieś znane tarpits odwracalny Turinga, gdzie „odwracalne” oznacza w sensie Axelsen i Glück , a „Tarpit” jest znacznie bardziej nieformalny pojęcie (i może nie być bardzo dobrym wyborem słowa), ale postaram się wyjaśnić, co mam na myśli. Co rozumiem przez „tarpit” Niektóre modele obliczeń …
2
Dlaczego linearyzowalność jest właściwością bezpieczeństwa i dlaczego zestawy właściwości bezpieczeństwa są zamknięte?
W rozdziale 13 „Obiekty atomowe” książki „Algorytmy rozproszone” Nancy Lynch udowodniono, że linearyzowalność (znana również jako atomowość) jest właściwością bezpieczeństwa. To znaczy, że jego odpowiednia właściwość śledzenia jest niepusta, zamknięta z prefiksem i zamknięta z ograniczeniem , jak zdefiniowano w sekcji 8.5.3. Nieformalnie właściwość bezpieczeństwa jest często interpretowana jako powiedzenie, …
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.