Szukam wydajnego algorytmu dla następującego problemu lub dowodu twardości NP. Niech będzie zbiorem, a A ⊆ P ( Σ ) zbiorem podzbiorów Σ . Znaleźć sekwencję wagowo ∈ Ď * o najmniejszej długości tak, że dla każdego L ∈ A , jest k ∈ N w taki sposób, { w k + I | 0 ≤ i < | L | } = L .ΣΣ\SigmaA ⊆ P(...
Czy istnieje jakiś naturalny lub znaczący sposób na powiązanie lub połączenie grup matematycznych i języków formalnych CS lub jakieś inne podstawowe pojęcie CS, np. Maszyny Turinga? Szukam referencji / aplikacji. Zauważ jednak, że jestem świadomy związku między półgrupami a językami CS...
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 :...
Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie. Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i...
Problem Nie ma łatwego sposobu na uzyskanie permutacji za pomocą wyrażenia regularnego. Permutacja: Uzyskanie słowa („aabc”) w innym porządku, bez zmiany liczby lub rodzaju liter.w=x1…xnw=x1…xnw=x_1…x_n Regex: wyrażenie regularne. Dla weryfikacji: „Permutacje regexów bez powtórzeń” Odpowiedź...
Wiem, że istnieją nieregularne języki, więc jest regularny, ale wszystkie przykłady, które mogę znaleźć, są zależne od kontekstu, ale nie pozbawione kontekstu.L.∗L∗L^* Jeśli nie ma, jak to
Wygląda na to, że „podstawowe wyrażenia regularne” zdefiniowane w POSIX.1-2008 nie obsługują naprzemiennego działania a|b(chociaż niektóre implementacje grep rozpoznają wersję ucieczkową \|). Skoro zwykłe języki są z definicji zamknięte w unii, czy to oznacza, że POSIX BRE ma mniejszą moc...
Wykonując bieżące zadanie dla moich kursów języków formalnych i automatów, w pewnym sensie utknąłem na ćwiczeniach obejmujących języki jednoargumentowe (mam nadzieję, że to właściwy termin), tj. Języki oparte na jednej literze. Nie chcę jednak pytać o konkretne ćwiczenia, ale raczej o bardziej...
Myślałem o gramatyce dla języków wrażliwych na indukcje i wygląda na to, że gramatyki CF zrobiłyby to samo, gdyby były połączone z parametrami. Jako przykład rozważ ten fragment uproszczonej gramatyki języka Python w formacie podobnym do ANTLR: // on top-level the statements have empty...
Studiuję języki formalne i systemy baz produkcyjnych (systemy baz reguł) i jestem trochę zdezorientowany, dlaczego te dwa słowa „produkcja” i „reguła” oznaczają to samo w tak wielu kontekstach w informatyce. W języku angielskim nie wydają się oznaczać tego samego. Nie jestem rodzimym językiem...
Niech będzie regularne, L 1 ∩ L 2 regularne, L 2 nie regularne. Pokaż, że L 1 ∪ L 2 nie jest regularne lub podaj kontrprzykład.L.1L1L_1L.1∩ L.2)L1∩L2L_1 \cap L_2L.2)L2L_2L.1∪ L.2)L1∪L2L_1 \cup L_2 Próbowałem tego: spójrz na . Ten jest regularny. Mogę w tym celu zbudować automat skończony: L 1...
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ć...
Rozumiem, że gramatyki bezkontekstowe mogą być używane do reprezentowania języków bezkontekstowych. Mogą być niejasne. Mamy również normalne formy, takie jak normalna postać Chomsky'ego i Greibacha . Nie mogłem zrozumieć takiej potrzeby. Dlaczego są ważne w teorii języków? Wszystkie podręczniki, o...
Na przykład, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Jak więc możemy udowodnić, że L∗L∗L^* jest regularne? Jeśli LLL jest regularne, to oczywiście L∗L∗L^* jest również regularne. Jeśli LLL jest skończone, to jest regularne i znowu L∗L∗L^* jest regularne. Zauważyłem również, że dla L={0p∣p is a...
Zastanawiam się, jaka jest złożoność czasowa określania pustki dla dwukierunkowych DFA? Oznacza to, że skończone automaty mogą przesuwać się wstecz na swojej taśmie wejściowej tylko do odczytu. Według Wikipedii są one równoważne DFA, chociaż równoważny DFA może być wykładniczo większy. Znalazłem...
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ć...
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...
Oto problem: Udowodnij, że maszyny Turinga z pojedynczą taśmą, które nie mogą pisać na części taśmy zawierającej łańcuch wejściowy, rozpoznają tylko zwykłe języki. Moim pomysłem jest udowodnienie, że ta konkretna baza TM jest odpowiednikiem DFA. Używanie tej TM do symulacji DFA jest bardzo...
Myślałem, że wszystkie języki regularne można wyrazić za pomocą wyrażeń regularnych (jeśli język jest regularny, można go wyrazić za pomocą wyrażenia regularnego), ale powiedziano mi, że potrzebujesz do tego wszystkich trzech operacji regularnych (konkatenacji, zjednoczenia i gwiazdki)...
Natknąłem się na ten rysunek, który pokazuje, że języki kontekstowe i zwykłe są (odpowiednimi) podzbiorami sprawnych problemów (podobno ). Doskonale rozumiem, że wydajne problemy stanowią podzbiór wszystkich rozstrzygalnych problemów, ponieważ możemy je rozwiązać, ale może to zająć bardzo dużo...