To dobrze znany wynik, że pytanie Czy gramatyka bezkontekstowa generuje zwykły język? jest nierozstrzygalny. Jednak staje się to rozstrzygalne na podstawie jednoznacznego alfabetu, po prostu dlatego, że w tym przypadku klasy języków bezkontekstowych i zwykłych pokrywają się. Moje pytanie...
To jest przeformułowanie Czy programy gramatyczne? poprzednio zadane przez Vag i z wieloma sugestiami komentujących. W jaki sposób można postrzegać gramatykę jako model obliczeń? Jeśli na przykład weźmiemy prostą gramatykę bezkontekstową, taką jak G ::= '1' -> '0' '+' '1' '1' -> '1' '+'...
Wiele lat temu słyszałem, że obliczenie minimalnego NFA (niedeterministycznego automatu skończonego) z DFA (deterministycznego) było otwartym pytaniem, w przeciwieństwie do odwrotnego kierunku, który jest znany od dziesięcioleci i jest dobrze zbadany z wydajnym algorytm. Czy ktoś wymyślił...
2dca (dwukierunkowe deterministyczne automaty licznikowe) (Petersen, 1994) może rozpoznać następujący jednoargumentowy język: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Czy jest jakiś inny nietrywialny, unary język...
Słowo www nazywa się prymitywnym , jeśli nie ma słowa i więc . Zbiór wszystkich prymitywnych słów nad alfabetem jest dobrze znanym językiem. WLOG możemy wybrać .vvvk>1k>1k > 1w=vkw=vkw = v^kQQQΣΣ\SigmaΣ={a,b}Σ={a,b}\Sigma = \{ a,b \} Język jest liczbą pierwszą , jeśli dla każdego języka i B...
Dla języka L ⊆ Σ ^ * zdefiniować składniowej identyczność ≡ z L co najmniej zbieżność na Ď ^ * że nasycone L , tj u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L]. Teraz zdefiniuj równoważność Nerode jako następującą prawą zgodność: u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L]. Niech [u] będzie klasą równoważności u w...
Istnieją teoretyczne dowody na to, że naiwna konstrukcja produktu kartezjańskiego na przecięciu DFA jest „najlepsza, co możemy zrobić”. Co z konkatenacją dwóch DFA? Trywialna konstrukcja polega na przekształceniu każdego DFA w NFA, dodaniu przejścia epsilon i określeniu wynikowego NFA. Czy możemy...
Mówimy, że NFA jest stale niejednoznaczny, jeśli istnieje tak że każde słowo jest akceptowane przez lub (dokładnie) ścieżek.MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Jeśli automat jest stale niejednoznaczny dla , wówczas nazywa się Jednoznacznym FA (UFA).MMMk=1k=1k=1MMM Niech będzie...
Zastanawiałem się, czy istnieje dobra bibliografia prób zbadania hipotezy Collatza jako formalnej gramatyki? (lub wszelkie inne próby w społeczności CS radzenia sobie z tą klasą zjawisk generatywnych i ich
Wyrażenie permutacji jest rozszerzeniem standardu (E) BNF wolne definicji kontekstu gramatyczne: frazę permutacji zawiera n produkcji (lub równoważnie nieterminale) A 1 przez A n . W miejscu wyrażenia permutacyjnego chcielibyśmy zobaczyć każdą z tych produkcji dokładnie raz, ale nie jesteśmy...
Według klasycznego wyniku Kurody, klasa złożoności NSPACE [ ]nnn (znana również jako NLIN-SPACE) jest właśnie klasą CSL języków kontekstowych . Problem satysfakcji SAT występuje w NSPACE [ ], ponieważ domysły o liniowym rozmiarze dla rozwiązania można sprawdzić z co najwyżej liniowym obciążeniem...
Jednoznaczne automaty skończone (UFA) są specjalnym typem niedeterministycznych automatów skończonych (NFA). NFA jest nazywany jednoznacznym, jeśli każde słowo ma co najwyżej jedną ścieżkę akceptującą.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Oznacza to, .D F.A ⊂ UfaA ⊂ NfaZArefaZA⊂UfaZA⊂N.faZADFA\subset...
Zastanawiam się, czy są jakieś dokumenty lub badania dotyczące widocznych automatów przesuwających w dół, ale pozwalające na wypychanie słów zamiast pojedynczych liter na stos. Alternatywnie, konstrukcja umożliwiająca wypychanie symboli na -transitions może osiągnąć ten sam...
Interesują mnie dwa pytania dotyczące języków kontekstowych (CSL) i kompletności: Czy istnieje pojęcie kompletności CSL i które języki są kompletne? Czy istnieją naturalne CSL, które są NP-kompletne? W przypadku 2. z pewnością mogę myśleć o naturalnych językach NP-zupełnych, które są CSL...
Tło: Biorąc pod uwagę dwa deterministyczne automaty skończone A i B, tworzymy iloczyn C, pozwalając, by stany w C były iloczynem kartezjańskim stanów w A i stanów w B. Następnie wybieramy stany przejściowe, początkowe i końcowe, aby język został zaakceptowany przez C to przecięcie języków dla A i...
To niekoniecznie jest pytanie badawcze. Tylko pytanie z ciekawości: Próbuję zrozumieć, czy można zdefiniować języki „nieredukowalne”. Na pierwszy rzut oka nazywam język L „redukowalny”, jeśli można go zapisać jako z i , w przeciwnym razie nazywam język „nieredukowalny” . Czy to prawda:L=A⋅BL=A⋅BL...
(Uogólniona) wysokość gwiazdy w języku jest minimalnym zagnieżdżeniem gwiazd Kleene wymaganym do przedstawienia języka za pomocą rozszerzonego wyrażenia regularnego. Przypomnijmy, że rozszerzonym wyrażeniem regularnym ponad skończonych alfabet spełnia następujące:ZAAA (1) i są rozszerzone...
Wiadomo, że minimalizowanie rozmiaru wyrażenia regularnego jest pełne dla PSPACE, nawet jeśli mamy specyfikację języka jako DFA . Jakie są wyniki, jeśli język jest skończony? Problem ten można rozważyć w dwóch modelach: Dane wejściowe to wszystkie ciągi w języku, a rozmiar wejściowy mierzymy...
Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?L.L.LL.L.L Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla...
Byłoby miło zebrać listę warunków, które sugerują, że bezkontekstowy język L jest regularny, tj. Warunki postaci: „jeśli dany CFG / PDA ma właściwość P, to jego języki są regularne” Właściwość P nie musi charakteryzować CFG generujących zwykłe języki. Ponadto P nie musi być rozstrzygalne, a P...