Pytania otagowane jako regular-languages

Pytania dotyczące właściwości klasy zwykłych języków i poszczególnych języków.

10
Jak udowodnić, że język nie jest regularny?
Dowiedzieliśmy się o klasie języków zwykłych . Charakteryzuje go dowolna koncepcja wśród wyrażeń regularnych, automatów skończonych i gramatyk lewostronnych, więc łatwo jest wykazać, że dany język jest regularny.REGREG\mathrm{REG} Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że ​​aby to zrobić, musielibyśmy wykazać dla wszystkich wyrażeń regularnych (lub dla wszystkich …
8
Jak udowodnić, że język jest regularny?
Istnieje wiele metod, aby udowodnić, że dany język nie jest regularny , ale co muszę zrobić, aby udowodnić, że jakiś język jest prawidłowy? Na przykład, jeśli otrzymam informację, że jest regularne, jak mogę udowodnić, że następujące jest również regularne?L ′LLLL′L′L' L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}\qquad \displaystyle …
2
Zwykłe języki planarne
W mojej klasie uczeń zapytał, czy wszystkie skończone automaty można narysować bez przekraczania krawędzi (wydaje się, że zrobiły to wszystkie moje przykłady). Oczywiście odpowiedź jest przecząca, oczywisty automat dla języka ma strukturę K_5 , kompletny wykres na pięciu węzłach . Yuval pokazał podobną strukturę dla pokrewnego języka.{x ∈ { a …
2
Dlaczego zwykły język nazywa się „zwykłym”?
Właśnie zakończyła pierwszy rozdział Wprowadzenie do teorii obliczeń przez Michaela Sipser który wyjaśnia podstawy automatów skończonych. Definiuje zwykły język jako wszystko, co można opisać za pomocą automatów skończonych. Ale nie mogłem znaleźć, gdzie tłumaczy, dlaczego zwykły język nazywa się „zwykłym”. Jakie jest pochodzenie terminu „regularny” w tym kontekście? UWAGA: Jestem …
3
Czy ten język jest zdefiniowany przy użyciu podwójnych liczb pierwszych regularnych?
Pozwolić L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. Czy regularny?LLL To pytanie wyglądało podejrzanie na pierwszy rzut oka i zdałem sobie sprawę, że jest związane z hipotezą o podwójnej liczbie pierwszych . Mój problem polega na …
4
Jak pokazać, że „odwrócony” język regularny jest regularny
Utknąłem na następujące pytanie: „Zwykłe języki są dokładnie tymi, które są akceptowane przez automaty skończone. Biorąc pod uwagę ten fakt, pokaż, że jeśli język jest akceptowany przez jakiś automat skończony, wówczas jest również akceptowany przez niektóre skończone; składa się ze wszystkich słów z odwrócone. ”LLLLRLRL^{R}LRLRL^{R}LLL
1
Wyrażenia regularne z odniesieniami wstecznymi do jednoznacznego alfabetu
Oprawa: wyrażenia regularne z referencjami wstecznymi język jednoargumentowy (alfabet 1-symbolowy) Czy w tym ustawieniu można rozstrzygać następujący problem: Biorąc pod uwagę wyrażenie regularne z odniesieniami wstecznymi, czy definiuje ono zwykły język? Na przykład (aa+)\1definiuje zwykły język, podczas gdy (aa+)\1+nie. Czy możemy zdecydować, który jest właściwy? Dla konkretności, „wyrażenia regularne z …
3
Liczba słów w zwykłym języku
Według Wikipedii , dla każdego zwykłego języka istnieją stałe i wielomiany takie, że dla każdego liczby słów o długości w spełnia równanieLLLλ1,…,λkλ1,…,λk\lambda_1,\ldots,\lambda_kp1(x),…,pk(x)p1(x),…,pk(x)p_1(x),\ldots,p_k(x)nnnsL(n)sL(n)s_L(n)nnnLLL sL(n)=p1(n)λn1+⋯+pk(n)λnksL(n)=p1(n)λ1n+⋯+pk(n)λkn\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n . Język L={02n∣n∈N}L={02n∣n∈N}L =\{ 0^{2n} \mid n \in\mathbb{N} \} jest zwykły ( (00)∗(00)∗(00)^* pasuje do niego). sL(n)=1sL(n)=1s_L(n) = 1 iff n jest parzyste, a sL(n)=0sL(n)=0s_L(n) …
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.