Pytania otagowane jako regular-language

Pytania o języki formalne, które można opisać wyrażeniami regularnymi (w sensie Kleene) lub, równoważnie, języki, które mogą być akceptowane przez automaty skończone.

5
Niejednoznaczność i logika
W teorii automatów (automaty skończone, automaty wypychające, ...) i złożoności występuje pojęcie „dwuznaczności”. Automat jest dwuznaczny, jeśli istnieje słowo z co najmniej dwoma odrębnymi przebiegami akceptującymi. Maszyna jest k- dwuznaczna, jeśli dla każdego słowa w zaakceptowanego przez maszynę istnieje co najwyżej k różnych przebiegów do zaakceptowania w .wwwkkkwwwkkkwww Pojęcie to …
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 …
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 …
4
Hierarchie w zwykłych językach
Czy istnieje jakaś znana „ładna” hierarchia L0⊆L1⊆L2⊆…L0⊆L1⊆L2⊆…L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots (może być skończona) w klasie zwykłych języków LLL ? Przyjemnie tutaj, klasy w każdej hierarchii przechwytują różną ekspresję / siłę / złożoność. Przynależność do każdej klasy jest „ładnie” wykazana przez niektóre elementy (w przeciwieństwie do problemu wysokości …
2
Zwykły kontra TC0
Według Zoo Złożoności , Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1} i wiemy, że RegReg\mathsf{Reg} nie może się liczyć, więc TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg} . Jednakże nie mówi, czy Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0} czy nie. Ponieważ nie znamy NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0} , nie znamy również Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} . Czy jest kandydatem do problemu w , który nie …
3
Znaczenie złożoności stanu w automatach i językach regularnych?
Czytam „ Łączenie zwykłych języków i złożoności opisowej ” Galiny Jiraskowej z 2009 r. Na temat złożoności państwa wynikającej z połączenia dwóch zwykłych języków (Galiny Jiraskowej), ale nie rozumiem, jakie byłyby praktyczne implikacje złożoności państwa . Pierwszą trywialną myślą, która mnie uderzyła, było to, że większa złożoność wymagałaby więcej czasu …
1
Wystarczające warunki dla prawidłowości języka bezkontekstowego
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 powinno „w jakiś sposób …
2
Automatyczne uczenie się bez kontrprób
W programie do nauki automatów Angluin , uczeń chce nauczyć się zwykłego języka , zadając swojemu nauczycielowi dwa rodzaje pytań:L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* Zapytania słowne: biorąc pod uwagę , czy ?w∈Σ∗w∈Σ∗w\in \Sigma^*w∈Lw∈Lw\in L Zapytania o równoważność: biorąc pod uwagę język , czy ? Jeśli nie, nauczyciel daje kontrprzykład, to słowo .K⊆Σ∗K⊆Σ∗K\subseteq \Sigma^*K=LK=LK=Lw∈K∖L∪L∖Kw∈K∖L∪L∖Kw\in …
1
Odległość między zwykłymi językami
Chcę zdefiniować pojęcie „bliskości” między dwoma regularnymi językami skończonych słów w (i / lub nieskończonych słów w Σ ω ). Podstawową ideą jest to, że chcemy, aby dwa języki były blisko siebie, jeśli nie różnią się wieloma słowami. Możemy również w jakiś sposób wykorzystać odległość edycji ... Nie mogłem znaleźć …
4
(N) DFA z tymi samymi stanami początkowymi / akceptującymi
Co wiadomo o klasie języków rozpoznawanych przez automaty skończone posiadające ten sam stan początkowy i akceptacji? Jest to właściwy podzbiór zwykłych języków (ponieważ każdy taki język zawiera pusty ciąg znaków), ale jak bardzo jest słaby? Czy istnieje prosta charakterystyka algebraiczna? To samo dotyczy języków rozpoznawanych przez niedeterministyczne automaty posiadające ten …
1
Sparametryzowana złożoność włączenia zwykłych języków
Interesuje mnie klasyczny problem REGULARNE WŁĄCZENIE JĘZYKA. Biorąc pod uwagę wyrażenie regularne , oznaczamy przez L ( E ) powiązany z nim język regularny. (Wyrażenia regularne są na stałej alfabetu Ď z unii operacji, Kleene-gwiazdkowe i konkatenacji).miEEL ( E)L(E)L(E)ΣΣ\Sigma Dane wejściowe: dwa wyrażenia regularne i E 2 Pytanie: Czy to …
3
Dwuznaczność w zwykłych i pozbawionych kontekstu językach
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 bezkontekstowe generowane przez niejednoznaczne CFG są również generowane przez jednoznaczne CFG. …
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.