Pytania oznaczone «closure-properties»

Wiemy, że języki bezkontekstowe nie są zamknięte pod uzupełnieniem. O ile mi zrozumieć, języków bezkontekstowych, które są podzbiorem * b * dla niektórych liter a , b są zamknięte pod dopełniacza (!?)a∗b∗a∗b∗a^*b^*a,ba,ba,b Oto mój argument. Każdy język CF ma półliniowy obraz Parikha π ( L ) = {...

To jest kolejne pytanie tego . W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie...

Niech GGG będzie gramatyką bezkontekstową. Łańcuch zacisków i nieterminali z GGG mówi się zdań tworzą z GGG , czy można go otrzymać stosując produkcje GGG zero lub więcej razy symbolu startu SSS . Niech SF(G)SF⁡(G)\operatorname{SF}(G) będzie zbiorem form zdaniowych GGG . Niech...

to zwykły język nad alfabetem Σ = { a , b } . Lewym ilorazem L dotyczącym w ∈ Σ ∗ jest język w - 1 L : = { v ∣ w v ∈ L }L.LLΣ = { a , b }Σ={a,b}\Sigma = \{a,b\}L.LLw ∈ Σ∗w∈Σ∗w \in \Sigma^*w- 1L : = { v ∣ w v ∈ L }w−1L:={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} Jak mogę udowodnić, że jest...

Naprawdę chciałbym pomóc w następujących kwestiach: W przypadku każdego stałego muszę zdecydować, czy nastąpi zamknięcie w ramach następujących operatorów:L.2)L2L_2 ZAr( L ) = { x ∣ ∃ y∈ L.2): x y∈ L }Ar(L)={x∣∃y∈L2:xy∈L}A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\} .ZAl( L ) = { x ∣ ∃ y∈ L :...

Czy istnieją nierozstrzygalne języki, tak że ich związek / język przecięcia / konkatenacji jest rozstrzygalny? Jaka jest fizyczna interpretacja takiego przykładu, ponieważ ogólnie nierozstrzygalne języki nie są zamknięte w ramach tych operacji? Co możemy powiedzieć o zamknięciu kleene? Czy mamy...

Chcę udowodnić, że dopełnienie nie używa regularnie właściwości zamknięcia.{ 0n1n| N ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\} Rozumiem, że można użyć lematu pompującego, aby udowodnić, że nie jest zwykłym językiem. Rozumiem również, że zwykłe języki są zamknięte w ramach operacji uzupełniania. Czy...

Jeśli jest regularne, to czy wynika z tego, że jest regularne? AA2A2A^2AAA Moja próba na dowód: Tak, ponieważ sprzeczność zakłada, że nie jest regularne. Następnie .A 2 = A ⋅ AAAAA2=A⋅AA2=A⋅AA^2 = A \cdot A Ponieważ łączenie dwóch nieregularnych języków nie jest regularne, nie może być...

Natknąłem się na to pytanie: „Podaj przykłady dwóch zwykłych języków, których związek nie tworzy zwykłego języka”. Jest to dla mnie dość szokujące, ponieważ uważam, że zwykłe języki są zamknięte w związku. Co oznacza dla mnie, że jeśli biorę dwóch języków regularnych i Unii nich, musi uzyskać...

Muszę wiedzieć, pod którą klasą CFL jest zamknięty, tj. Jaki zestaw jest uzupełnieniem CFL. Wiem, że CFL nie jest zamknięty pod dopełnieniem i wiem, że P jest zamknięty pod dopełnieniem. Ponieważ CFL PI może powiedzieć, że dopełnienie CFL jest zawarte w P (prawda?). Pozostaje pytanie, czy...

Przesunięcia cyklicznego (zwany również obracanie lub koniugacji ) języka jest zdefiniowana jako . Według wikipedii (i tutaj ) języki bezkontekstowe są zamknięte w ramach tej operacji, z odniesieniami do artykułów z Osziby i Masłowa. Czy istnieje łatwy dowód tego faktu?L LL{ y x ∣ x y ∈ L...

Jednym ze sposobów patrzenia na wyrażenia regularne jest konstruktywny dowód na następujący fakt: możliwe jest zbudowanie języków regularnych, zaczynając od małego zestawu języków i łącząc je za pomocą małego, stałego zestawu właściwości zamknięcia. W szczególności, jeśli zaczniemy od pustego...

Utknąłem, rozwiązując następne ćwiczenie: Argumentuj, że jeśli L.LL jest bezkontekstowy i RRR jest zatem regularny L / R = { w ∣ ∃ x ∈ Rśww x ∈ L }L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} (tj. odpowiedni iloraz ) jest pozbawiony kontekstu. Wiem, że powinien...