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...
Rozstrzyga się następujący problem: Biorąc pod uwagę bezkontekstową gramatykę , czy ?L ( G ) = ∅solGGL ( G ) = ∅L(G)=∅L(G) = \varnothing Następujący problem jest nierozstrzygalny: Biorąc pod uwagę bezkontekstową gramatykę , czy L (G) = A ^ {\ ast} ?L ( G ) = A ∗solGGL ( G ) = A∗L(G)=A∗L(G) =...
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...
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...
Niech będzie językiem if : Σ ⋆ × Σ ⋆ → Σ ⋆ funkcja na dwóch parametrach z właściwością, która dla wszystkich x i y , f zwraca element L wtedy i tylko wtedy, gdy oba x i y są elementami L :LL.Lf:Σ⋆×Σ⋆→Σ⋆fa:Σ⋆×Σ⋆→Σ⋆f\colon
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie...
Rozumiem następujące twierdzenia, które są prawdziwe: Dwie różne pochodne łańcucha w danym CFG mogą czasem przypisywać to samo drzewo parsowania łańcuchowi. Kiedy w danym CFG występują pochodne jakiegoś łańcucha, które przypisują różne drzewa parsowania, CFG jest niejednoznaczny. Niektóre języki...
Rozważ następujący problem: Biorąc pod uwagę dwa ciągi x, y, zdecyduj, czy istnieje homomorfizm ciągu f taki, że f (x) = y. Łatwo jest pokazać, że problem ten jest w . Czy są inne rzeczy, które możemy powiedzieć o tym problemie? Jest to na przykład w c o N P lub nawet P...
System dodawania wektorów (VAS) to skończony zestaw działań . jest zbiorem oznaczeń . Trasa jest niepusty słowo oznaczenia st . Jeśli takie słowo istnieje, mówimy, że jest osiągalne z .A⊂ZdA⊂ZdA \subset \mathbb{Z}^dm 0 m 1 … m n ∀ i ∈ { 0 , … , n - 1 } , m i + 1 - m i ∈ A m n m...
Deterministyczne języki bezkontekstowe (DCFL) i języki z widocznym przesunięciem w dół (VPL) są zestawami języków formalnych między językami bezkontekstowymi (CFL) i zwykłymi (REG). Czy istnieje czytelny zapis, który można wyrazić zwykłym ASCII, takim jak Backus-Naur-Form dla CFL i wyrażenia...
Cześć wszystkim, obecnie staram się znaleźć solidny temat pracy magisterskiej dotyczący jakiejś gałęzi teorii automatów lub związany z językami formalnymi. Próbuję wygenerować kilka dobrych pomysłów na temat akceptowalnego tematu, czegoś ambitnego, ale jednocześnie wykonalnego. Wszelkie sugestie...
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,...
Opis problemu: Pozwolić MMM być (potencjalnie niedeterministycznym) automatem wypychającym i pozwól AA\cal Abyć jego alfabetem wejściowym. Czy jest jakieś słowo?w∈A∗w∈A∗w \in \cal A^* św |w|≤k|w|≤k|w| \leq k które jest akceptowane przez MMM ? Czy ten problem NP-jest kompletny? Czy zostało to...
Niech będzie językiem bezkontekstowym. Zdefiniować p p c ( L ) za przed i przyrostek zamknięcie L , innymi słowy, p p c ( L ) obejmują L jest prefiks i postfixes i stąd L siebie. Moje pytanie: jeśli L jest pozbawiony kontekstu i ma niejednoznaczną gramatykę, to czy to samo dotyczy p p c ( L )...
Nie wiadomo czy P⊆CSLP⊆CSLP\subseteq CSL lub P⊈CSLP⊈CSLP\not\subseteq CSL, gdzie PPP jest zbiorem wszystkich języków rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga, oraz CSLCSLCSL jest klasą języków kontekstowych, znanych jako równoważne...
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...
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...
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...
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...
Niech zostanie podana liczba . Rozważ następujący język .nnnL.n= {w w|w ∈ { 0 , 1 }n}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} słowy, jest zbiorem ciągów kopii o długości . 2 nL.nLnL_n2 n2n2n Rozważmy następujący stan złożoność funkcji takie, że jest liczbą stanów w...