Pytania otagowane jako formal-languages

Pytania dotyczące języków formalnych, gramatyki i teorii automatów

3
Po co używać języków w teorii złożoności
Właśnie zaczynam wchodzić w teorię obliczeń, która bada, co można obliczyć, jak szybko, z wykorzystaniem ilości pamięci iz jakim modelem obliczeniowym. Mam dość podstawowe pytanie, ale naprawdę mam nadzieję, że niektórzy z was pomogą mi zrozumieć koncepcję: Dlaczego wszystko koncentruje się wokół pojęcia i definicji JĘZYKÓW (tj. Języków zwykłych i …
4
Czy istnieje niezdecydowany skończony język skończonych słów?
Czy istnieje potrzeba, aby L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* była nieskończona, aby była nierozstrzygalna? Chodzi mi o to, że jeśli wybierzemy język L′L′L' jako ograniczoną skończoną wersję L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* , to znaczy |L′|≤N|L′|≤N|L'|\leq N ( N∈NN∈NN \in \mathbb{N} ), a L′⊂LL′⊂LL' \subset L . Czy jest możliwe, L′L′L' być język nierozstrzygalny? Widzę, że …
5
Język wartości funkcji afinicznej
Napisz n¯n¯\bar n dla dziesiętnego rozszerzenia nnn (bez wiodącego 0). Niech aaa i bbb będą liczbami całkowitymi o a>0a>0a > 0 . Rozważmy język rozwinięć dziesiętnych wielokrotności plus stałej:aaa M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈N}M={ax+b¯∣x∈N}M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \} Czy MMM regularne? bez kontekstu? (Kontrast z językiem wykresu funkcji afinicznej ) Myślę, że …
5
Czy istnieje znana metoda konstruowania gramatyki przy skończonym zestawie skończonych łańcuchów?
Z mojego czytania wynika, że ​​większość gramatyk dotyczy generowania nieskończonej liczby łańcuchów. Co jeśli pracowałeś na odwrót? Jeśli podano n łańcuchów o długości m, powinno być możliwe stworzenie gramatyki, która wygeneruje te łańcuchy i tylko te łańcuchy. Czy istnieje znana metoda wykonania tego? Idealnie nazwa techniki, którą mogę badać. Alternatywnie, …
1
Jak można ws z | w | = | s | a my będziemy bez kontekstu, podczas gdy w # s nie jest?
Dlaczego (jeśli tak) separator ##\# robi różnicę między tymi dwoma językami? Powiedzmy: L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} Oto dowód i gramatyk reprezentującyLLL jak CFLCFLCFL A poniżej dodam dowód na to L#∉CFLL#∉CFLL_{\#} \notin CFL : Czy ##\#znak naprawdę …
1
Jak potężne są CFG, które pozwalają na nieskończoną liczbę zasad?
Zastanawiałem się ostatnio, co by się stało, gdybyśmy pozwolili gramatykom bezkontekstowym mieć nieskończoną liczbę reguł. Oczywiście, gdybyśmy zezwolili na arbitralne takie nieskończone zbiory reguł, każdy językLLL nad jakimś alfabetem ΣΣ\Sigma może być opisany przez CFG G=({S},Σ,R,S)G=({S},Σ,R,S)G = (\{S\},\Sigma,R,S) z R={S→w∣w∈L}R={S→w∣w∈L}R = \{S \rightarrow w \mid w \in L \}. Ale …
3
Dlaczego stan pozostaje niezmieniony w niewielkiej semantyce operacyjnej pętli while?
Zwykle widzę, że w strukturalnej reprezentacji operacyjnej semantyki dla pętli while stan programu nie zmienia się: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \> else \> SKIP, \sigma) Dla mnie nie jest to intuicyjne, jeśli stan się nie …
2
Regularność języków jednoargumentowych o długości słowa suma dwóch resp. trzy kwadraty
Myślę o językach jednoargumentowych LkL.kL_k, gdzie LkL.kL_k jest zbiorem wszystkich słów, których długość jest sumą kkkkwadraty. Formalnie: Lk={an∣n=∑i=1kni2,ni∈N0(1≤i≤k)}L.k={zan∣n=∑ja=1knja2),nja∈N.0(1≤ja≤k)}L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} Łatwo to pokazać L1={an2∣n∈N0}L.1={zan2)∣n∈N.0}L_1=\{a^{n^2}\mid n\in\mathbb{N_0}\}nie jest regularny (np. z Pumping-Lemma). Ponadto wiemy, że każda liczba naturalna jest sumą czterech kwadratów, co implikuje, że dlak≥4k≥4k\ge 4 wszystkie języki LkL.kL_k …
1
Jakie są odpowiednie izomorfizmy między językami formalnymi?
Język formalny nad alfabetem jest podzbiorem , czyli zbiór słów nad tym alfabecie. Dwa formalne języki i są sobie równe, jeśli odpowiadające im zbiory są ponadto równe jako podzbiory . W teorii złożoności można używać języków, aby sformalizować pojęcie „problemu”. Można narzekać, że „ogólnie” ekstensywna równość jest nierozstrzygalna, ale wierzę, …
3
Gramatyka kontekstowa dla języka słów połączonych ze sobą
Szukam gramatyki kontekstowej opisującej następujący język: .L={ww∣w∈{a,b}∗,|w|≥1}L={ww∣w∈{a,b}∗,|w|≥1}L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\} Mam problem z tym, że żadne reguły, takie jak są dozwolone i dlatego nie mogę umieścić żadnego nieterminala wskazującego „środek” słowa. Czy jest jakiś sposób na rozwiązanie tego problemu?X→εX→εX \to \varepsilon
1
Różnica między językami akceptowanymi przez dwa DFA o różnych stanach początkowych / stanach akceptacji?
Ostatnio zadałem pytanie na temat Math SE. Na razie brak odpowiedzi. To pytanie jest związane z tym pytaniem, ale bardziej technicznymi szczegółami w kierunku informatyki. Biorąc pod uwagę dwa DFA i gdzie zbiór stanów, alfabet wejściowy i funkcja przejścia i są takie same, stany początkowe i stany końcowe (akceptujące) mogą …
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.