Pytania otagowane jako automata-theory

Teoria automatów, w tym maszyny abstrakcyjne, gramatyki, parsowanie, wnioskowanie gramatyczne, przetworniki i techniki skończone

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 …
2
Czy automaty XOR (NXA) dla języków skończonych korzystają z cykli?
Niedeterministyczne automaty Xor (NXA) są składniowo NFA, ale mówi się, że słowo jest akceptowane przez NXA, jeśli ma nieparzystą liczbę ścieżek akceptacji (zamiast co najmniej jednej ścieżki akceptacji w przypadku NFA). Łatwo zauważyć, że dla skończonego języka regularnego LLL istnieje minimalny NFA, który nie zawiera żadnych cykli (jeśli cykl był …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
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 …
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 …
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
Szybki rzadki łańcuch boolowski z matrycą
Mam więc około 100-200 bardzo rzadkich kwadratowych macierzy boolowskich o długości boku ~ kilkudziesięciu i muszę obliczyć ich iloczyn. Wiem, że jeśli pomnożę je szeregowo, produkt zwykle pozostanie tak rzadki na każdym kroku. Czy w tym przypadku są jakieś algorytmy łańcucha macierzy, które działają szczególnie szybko? Na wyższym poziomie problemem …
2
Dlaczego stan FSM tradycyjnie oznacza
Ucząc, jak implementować FSM przy użyciu synchronicznych obwodów logicznych, zauważyłem intrygujący zbieg okoliczności: zarówno w teoretycznym świecie CS, jak iw świecie elektrotechniki „stan” jest zwykle oznaczany jako (i przestrzeń stanu Q ). Najpierw zapytałem na EE.sx , ale potem, badając nieco ten temat, odkryłem, że nawet oryginalny papier Turinga z …
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.