Pytania dotyczące właściwości klasy zwykłych języków i poszczególnych języków.
Istnieje wiele metod, aby udowodnić, że dany język nie jest regularny , ale co muszę zrobić, aby udowodnić, że jakiś język jest prawidłowy? Na przykład, jeśli otrzymam informację, że jest regularne, jak mogę udowodnić, że następujące jest również regularne?L
W mojej klasie uczeń zapytał, czy wszystkie skończone automaty można narysować bez przekraczania krawędzi (wydaje się, że zrobiły to wszystkie moje przykłady). Oczywiście odpowiedź jest przecząca, oczywisty automat dla języka ma strukturę K_5 , kompletny wykres na pięciu węzłach . Yuval pokazał...
Czytałem o Jocie i Jocie i uznałem tę sekcję za mylącą: W przeciwieństwie do Iota, gdzie drzewo syntaktyczne łańcucha może rozgałęzić się po lewej lub po prawej stronie, składnia Jot jest równomiernie rozgałęziona w lewo. W rezultacie Iota jest całkowicie pozbawiona kontekstu, ale Jot jest...
Właśnie zakończyła pierwszy rozdział Wprowadzenie do teorii obliczeń przez Michaela Sipser który wyjaśnia podstawy automatów skończonych. Definiuje zwykły język jako wszystko, co można opisać za pomocą automatów skończonych. Ale nie mogłem znaleźć, gdzie tłumaczy, dlaczego zwykły język nazywa się...
Dla języka regularnego , niech c n ( L ) będzie liczbą słów w L o długości n . Stosując kanoniczną postać Jordana (zastosowaną do niezanotowanej macierzy przejścia dla niektórych DFA dla L ), można wykazać, że dla wystarczająco dużych n , c n ( L ) = k ∑ i = 1 P i ( n ) λ n i , gdzie P i...
Oto przypuszczenie dotyczące wyrażeń regularnych: Dla wyrażenia regularnego , niech długość | R | być liczbą w nim symboli, ignorując nawiasy i operatory. np | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2RRR|R||R||R||0∪1|=|(0∪1)∗|=2|0∪1|=|(0∪1)∗|=2|0 \cup 1| = |(0 \cup 1)^*| = 2 Domysł: Jeśli i L ( R )...
Wiemy, że DFA są równoważne NFA pod względem siły wyrazu; znany jest również algorytm konwersji NFA na DFA (niestety teraz znam twórcę tego algorytmu), który w najgorszym przypadku daje nam 2S2S2^S stany S , jeśli nasz NFA ma stany SSS Moje pytanie brzmi: co determinuje najgorszy...
Wikipedia ma następującą definicję lematu pompującego dla zwykłych języków ... Niech będzie zwykłym językiem. Następnie istnieje całkowita p ≥ 1 zależy wyłącznie od L , tak że każdy ciąg wagowych w L o długości co najmniej p ( p nazywany jest „pompowanie długość”) może być zapisane jako W = xyz...
Utknąłem na następujące pytanie: „Zwykłe języki są dokładnie tymi, które są akceptowane przez automaty skończone. Biorąc pod uwagę ten fakt, pokaż, że jeśli język jest akceptowany przez jakiś automat skończony, wówczas jest również akceptowany przez niektóre skończone; składa się ze wszystkich...
Pozwolić L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. Czy regularny?LLL To pytanie wyglądało podejrzanie na pierwszy rzut oka i zdałem sobie sprawę, że jest związane z hipotezą o podwójnej liczbie pierwszych ....
Próbuję użyć lematu pompującego, aby udowodnić, że nie jest regularne.L = { ( 01 )m2)m∣ m ≥ 0 }L={(01)m2m∣m≥0}L = \{(01)^m 2^m \mid m \ge0\} Oto co mam do tej pory: Załóżmy, że jest regularne i niech p będzie długością pompowania, więc w = ( 01 ) p 2 p . Rozważ każdy rozkład pompowania w = x y z...
Oprawa: wyrażenia regularne z referencjami wstecznymi język jednoargumentowy (alfabet 1-symbolowy) Czy w tym ustawieniu można rozstrzygać następujący problem: Biorąc pod uwagę wyrażenie regularne z odniesieniami wstecznymi, czy definiuje ono zwykły język? Na przykład (aa+)\1definiuje zwykły...
Według Wikipedii , dla każdego zwykłego języka istnieją stałe i wielomiany takie, że dla każdego liczby słów o długości w spełnia
Istnieje wiele (i mam na myśli wiele) języków, które można policzyć w Turingu. Czy jakiś niezliczony język może być rozstrzygalny przez
Nie jestem pewien, czy w teorii komputerowej używa się zwrotów „nieskończony” język lub „skończony” język. Myślę, że źródłem problemu jest to, że język taki jak jest nieskończony w tym sensie, że może wygenerować nieskończoną (ale policzalną) liczbę łańcuchów. Jednak nadal może być rozpoznany...
Uwaga: jest to pytanie związane z nauką na kursie CS na uniwersytecie, NIE jest to zadanie domowe i można je znaleźć tutaj pod egzaminem Fall 2011. Oto dwa pytania, na które patrzę z poprzedniego egzaminu. Wydaje się, że są ze sobą powiązane, pierwsze: Pozwolić F I N I T EC F G= {...
Mówi się, że przecięcie języka L bez kontekstu z językiem zwykłym M jest zawsze wolne od kontekstu. Zrozumiałem dowód na konstrukcję wielu produktów, ale wciąż nie rozumiem, dlaczego nie zawiera kontekstu, ale nie jest regularny. Język generowany przez takie skrzyżowanie ma ciągi znaków, które są...
Biorąc pod uwagę języki i , powiedzmy, że ich konkatenacja jest jednoznaczna, jeśli dla wszystkich słów istnieje dokładnie jeden rozkład z i , a niejednoznaczny inaczej. (Nie wiem, czy istnieje ustalony termin dla tej właściwości - trudna rzecz do wyszukania!) Jako trywialny przykład konkatenacja z...
Jeśli mam gramatykę typu 3, można ją przedstawić na automacie wypychania (bez wykonywania żadnych operacji na stosie), dzięki czemu mogę reprezentować wyrażenia regularne przy użyciu języków bezkontekstowych. Ale czy mogę wiedzieć, czy gramatyka typu 3 to , , itd. Bez konstruowania jakichkolwiek...
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