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...
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...
Niech będzie jakimś językiem, a następnie zdefiniujemy spójność syntaktyczną jako u ∼ v : ⇔ ∀ x , y ∈ X ∗ : x u y ∈ L ↔ x v y ∈ L i iloraz monoidu X ∗ / ∼ L wynosi nazywany składniowym monoid z L .L ⊆ X∗L⊆X∗L \subseteq X^{\ast}u ∼ v : ⇔ ∀ x , y∈ X∗: x u y∈ L ↔ x v y∈ L.u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u...
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...
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...
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:...
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...
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żane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff .[ T ] y x x [ T ] yT.TT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pytanie: Czy można rozstrzygnąć następujący...
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...
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki? Przez niedeterministyczny automat związany liniowo (nLBA) mam na myśli niedeterministyczną maszynę Turinga z pojedynczą taśmą, w której dane wejściowe są „wyściełane” znakami końcowymi na obu...
Pozwolić L⊆A∗L⊆A∗L \subseteq A^* być językiem i zdefiniować fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\} przez fL(x,y)=1fL(x,y)=1f_L(x, y) = 1 iff x⋅y∈Lx⋅y∈Lx\cdot y \in L. Szukam referencji dla: Propozycja. LLL jest regularna w deterministycznej złożoności komunikacji fLfLf_L...
Dla ustalonego języka L.LL na jakiś alfabet ZAAA, rozważmy następujący problem, który nazywam L.LL-WŁOKA WEWNĘTRZNA : Wejście: dwa słowa u , v ∈ZA∗u,v∈A∗u, v \in A^* Wyjście: czy istnieje takie przeplatanie oduuu i vvv która jest w L.LL. Tutaj przeplatają się dwa słowauuu i vvv to słowo www...
Biorąc pod uwagę pełne DFA A=(Q,Γ,δ,F)A=(Q,Γ,δ,F)A=(Q, \Gamma, \delta, F), możemy zdefiniować zbiór funkcji fafaf_a dla każdego a∈Γa∈Γa\in \Gammai z fa:Q→Qfa:Q→Qf_a:Q\rightarrow Q, fa(q)=δ(q,a)fa(q)=δ(q,a)f_a(q)=\delta(q, a). Możemy uogólnić to pojęcie na słowow=a1,⋯,amw=a1,⋯,amw=a_1, \cdots, a_m i...
Pozwolić AAAbyć skończonym alfabetem. Dla danego języka składniowym monoid jest dobrze znanym pojęciem w teorii język form. Co więcej, monoid rozpoznaje język jeśli istnieje morfizm taki, że .L⊆A∗L⊆A∗L \subseteq A^{\ast} M(L)M(L)M(L)MMMLLLφ:A∗→Mφ:A∗→M\varphi : A^{\ast} \to...