Pytania otagowane jako fl.formal-languages

języki formalne, gramatyka, teoria automatów

1
Czy ciągła dwuznaczność może zmniejszyć złożoność stanu zwykłych języków?
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 zwykłym językiem.LLL Czy jakiś stale dwuznaczny automat dla być mniejszy niż najmniejszy UFA, który akceptuje …
2
Jak mały może być NFA w porównaniu z minimalnym jednoznacznym automatem skończonym (UFA) tego samego języka regularnego?
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 UFA\subset NFA Znane powiązane wyniki automatów: Minimalizacja NFA jest kompletna z PSPACE. Minimalizacja NFA w …
1
Czy istnieją warianty widocznych automatów przesuwających, które umożliwiają wypychanie słów na stos?
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 cel.ϵϵ\epsilon Oczywiście, takie warianty mogą być tworzone, ale zastanawiam się, czy to rujnuje właściwości zamknięcia …
1
Gramatyka kontekstowa dla SAT?
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 dla księgowości. Oznacza to, że SAT musi mieć …
2
Zwroty permutacyjne z analizą LR
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 zainteresowani kolejnością tych nieterminali.{ A1, … , An}{ZA1,…,ZAn}\{ A_1, \dots, …
1
Skuteczne połączenie DFA?
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 zrobić lepiej? Czy znane jest ograniczenie wielkości minimalnej DFA …
1
Języki kompletne i wrażliwe na kontekst.
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 (ponieważ CSL jest równy NSPACE [nnn ], SAT to …
3
Nieredukowalne języki
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 = A \cdot BA∩B=∅A∩B=∅A \cap B = \emptyset|A|,|B|>1|A|,|B|>1|A|,|B|>1 …
2
minimalizowanie wielkości wyrażeń regularnych dla zbiorów skończonych
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 sumą długości wszystkich ciągów. Dane wejściowe to …
2
Automaty Büchi ze strategią akceptacji
Problem Niech = ⟨ Ď , P , Q 0 , F , Δ ⟩ jest automatem Biichi rozpoznawania języka . Zakładamy, że ma strategię odbioru w następującym sensie: jest funkcja , które mogą być używane do tras pilotażowych . Formalizujemy to, spełniając następujące warunki:A=⟨Σ,Q,q0,F,Δ⟩A=⟨Σ,Q,q0,F,Δ⟩A=\langle \Sigma, Q, q_0,F,\Delta\rangleL⊆ΣωL⊆ΣωL\subseteq\Sigma^\omegaAAAσ:Σ∗→Qσ:Σ∗→Q\sigma:\Sigma^*\to QAAA σ(ϵ)=q0σ(ϵ)=q0\sigma(\epsilon)=q_0 …
3
Postęp w ogólnym problemie z wysokością gwiazdy?
(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 wyrażenia regularne dla wszystkich A ∈∅ , 1∅,1\emptyset, 1zaaaa ∈ Aa∈Aa\in A (2) Dla wszystkich rozszerzonych wyrażeń …
4
Reprezentacje base-k w domenie wielomianu - czy jest ona pozbawiona kontekstu?
W rozdziale 4 Drugiego kursu teorii automatu Jeffreya Shallita następujący problem wymieniono jako otwarty: p(n)p(n)p(n)∈Np(n) \in \mathbb{N}n∈Nn \in \mathbb{N} { p ( n ) ∣ n ⩾ 0 }){p(n)∣n⩾0}\{p(n) \mid n \geqslant 0\} jest pozbawione kontekstu, tylko wtedy, gdy stopieńwynosi.ppp ⩽ 1⩽1\leqslant 1 Jaki jest teraz jego status (na październik …
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.