Czy istnieje algebraiczna charakterystyka liczby słów o danej długości w zwykłym języku? Wikipedia podaje wynik nieco nieprecyzyjnie: Dla każdego języka regularnego istnieje stałych i wielomiany tak, że dla każdego numer z słowa o długości w spełnia równanie
Ostatnio zadano interesujące pytanie, a następnie usunięto. W przypadku zwykłego języka jego złożoność DFA jest wielkością minimalnej akceptacji DFA, a złożoność NFA jest wielkością minimalnej akceptacji NFA. Dobrze wiadomo, że istnieje wykładnicza separacja między tymi dwoma złożonościami,...
Biorąc pod uwagę alfabet Σ = { a , b }Σ={za,b}\Sigma = \{ a,b \} , ile jest różnych języków regularnych, które może zaakceptować nnn stanowy niedeterministyczny automat skończony? Jako przykład rozważmy n=3n=3n=3 . Następnie mamy 2182182^{18} różnych konfiguracji przejścia i 23232^3 różne...
Wiadomo, że język słów o równej liczbie 0 i 1 nie jest regularny, podczas gdy język słów o równej liczbie 001 i 100 jest regularny ( patrz tutaj ). Biorąc pod uwagę dwa słowa , czy jest rozstrzygalne, czy język słów zawierający taką samą liczbę i jest regularny?w 1 w...
Zastanawiałem się, kiedy języki zawierające taką samą liczbę wystąpień dwóch podciągów będą normalne. Wiem, że język zawierający taką samą liczbę 1 i 0 nie jest regularny, ale jest językiem takim jak , gdzie = liczba wystąpień podłańcucha „001” jest równa liczbie wystąpień podłańcucha „ 100 "...
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
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 :...
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...
Niech język będzie regularny.L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Rozkład na czynniki to maksymalna para zestawów słów z ( X , Y )LL\mathcal{L}(X,Y)(X,Y)(X,Y) X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , gdzie | .x ∈ X , y ∈ Y }X⋅Y={xyX⋅Y={xyX \cdot Y =...
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...
Wiem więc, że sprawdzenie, czy zwykły język jest podzbiorem zwykłego języka jest rozstrzygalne, ponieważ możemy przekonwertować je oba na DFA, obliczyć , a następnie sprawdzić, czy ten język jest pusty.S R ∩ ˉ S.RRRS.S.SR ∩ S¯R∩S.¯R \cap \bar{S} Ponieważ jednak wymaga to konwersji do DFA, możliwe...
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...
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)...
Zastanawiałem się, ponieważ * jest sam język gwiazda wolna, czy istnieje język regularny, który nie jest językiem gwiazdy darmo? Czy możesz podać przykład?za∗za∗a^* (z wikipdii ) Lawson definiuje języki bez gwiazdek jako: Mówi się, że w zwykłym języku nie ma gwiazd, jeśli można go opisać...
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...
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ć...
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...