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...
Które z następujących wyrażeń jest poprawne? istnieją wystarczające i konieczne warunki dotyczące prawidłowości języka, ale jeszcze ich nie odkryto. Nie ma wystarczających i koniecznych warunków dotyczących prawidłowości języka. Pompowanie lematu jest niezbędnym warunkiem nieregularności...
Regularne expresssion jest zdefiniowany rekurencyjnie jako aaa dla niektórych jest wyrażeniem regularnym,a∈Σa∈Σa \in \Sigma εε\varepsilon jest wyrażeniem regularnym, ∅∅\emptyset jest wyrażeniem regularnym, (R1∪R2)(R1∪R2)(R_1 \cup R_2) gdzie i są wyrażeniami regularnymi, jest wyrażeniem...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
Na przykład wiem, że nieregularny język zanbnzanbna^nb^n jest w . Chciałbym poznać więcej takich przykładów.A
Biorąc pod uwagę dwa zbiory ciągów znaków nad alfabetem Σ , czy możemy obliczyć najmniejszy deterministyczny automat skończony (DFA) M taki, że A ⊆ L ( M ) i L ( M ) ⊆ Σ ∗ ∖ BA,BA,BA,BΣΣ\SigmaMMMA⊆L(M)A⊆L(M)A \subseteq L(M)L(M)⊆Σ∗∖BL(M)⊆Σ∗∖BL(M) \subseteq \Sigma^*\setminus B ? Innymi słowy,...
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest prawidłowy? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak L={anbn:n∈N}L={anbn:n∈N}L=\{a^n b^n : n \in \mathbb{N}\}), sprawdź, czy język jest prawidłowy, czy nie. Wyobraź...
Załóżmy, że to zwykły język nad uporządkowanym alfabetem. Czy język jest zbudowany przez wzięcie każdego słowa w i posortowanie go zawsze jako zwykłego
Wiem, że języki, które można zdefiniować za pomocą wyrażeń regularnych i te rozpoznawane przez DFA / NFA (automaty skończone) są równoważne. Nie istnieje również DFA dla języka . Ale nadal może być napisane przy użyciu wyrażeń regularnych (zresztą każdy non-język regularny może być) jako . Wiemy...
Opisz zwykły język, którego nie może zaakceptować żaden DFA, który ma tylko trzy stany. Nie jestem do końca pewien, od czego zacząć i zastanawiałem się, czy ktoś mógłby dać mi jakieś wskazówki lub porady. Rozumiem, że lematu pompującego można użyć do udowodnienia, że język nie jest regularny,...
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...
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...
Lub przynajmniej wygeneruj zestaw ciągów, które akceptuje jeden NFA, więc mogę wprowadzić go do drugiego NFA. Czy jeśli przeszukam wszystkie ścieżki NFA, czy to zadziała? Chociaż zajmie to dużo
Kilka tygodni temu podjąłem egzaminy z teorii obliczeń i było to jedno z pytań: Załóżmy, że językL = { (zanbm)r∣ n , m , r ≥ 0 }L.={(zanbm)r∣n,m,r≥0}L=\{(a^nb^m)^r \mid n,m,r\ge 0\} Czy L jest regularny? Jeśli tak, podaj wyrażenie regularne lub automat. Po tym, jak krótko zapytałem go o...
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...
Możemy utworzyć DFA, przyjmując liczby binarne podzielne przez .nnn Na przykład DFA akceptujący liczby binarne podzielne przez 2 można utworzyć w następujący sposób: Podobnie DFA akceptujący liczby binarne podzielne przez 3 można utworzyć w następujący sposób: Możemy zastosować dobrze...
Biorąc pod uwagę język , jak mogę powiedzieć bezpośrednio, nie patrząc na reguły produkcji, że ten język nie jest regularny?L = {zanbndon}L.={zanbndon} L= \{a^n b^n c^n\} Mógłbym użyć lematu pompującego, ale niektórzy mówią tylko patrząc na gramatykę, że to nie jest normalne. Jak to jest...
Zacząłem studiować niedeterministyczne automaty, korzystając z książki Hopcroft i Ullman . Utknąłem w problemie, który uznałem za bardzo interesujący: Daj niedeterministyczny automat skończony akceptujący wszystkie ciągi, które mają tę samą wartość, gdy są oceniane od lewej do prawej, od prawej...
Pracuję nad Sipser Book (wydanie drugie) i natknąłem się na ten przykład, którego nie rozumiem. W książce stwierdzono, że ten NFA akceptuje pusty ciąg .ϵϵ\epsilon Czy ktoś mógłby mnie przekonać, dlaczego tak jest? Rozumiem, że przejdzie do co nie jest stanem