Czy regularne?

Kilka tygodni temu podjąłem egzaminy z teorii obliczeń i było to jedno z pytań:

Załóżmy, że język $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 odpowiedź po egzaminie, wydaje się, że jest ona naprawdę regularna (myślę, że powiedział, że wyrażenie jest proste ). Jednak nie rozumiem, dlaczego tak jest. Sposób, w jaki zobaczyć, jej łączenie r razy, na przykład: $(a^*b^*)^*$ $a^nb^m$

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$ ,

który nie jest regularny, ponieważ nie ma sposobu automatem przypomnieć n i m za każdym razem. Gdzie jestem tutaj winna?

EDYCJA: Ponownie rozmawiałem z profesorem, przyznał, że to pomyłka. Język rzeczywiście nie jest regularny.

formal-languages regular-languages regular-expressions Exci
źródło

Powinieneś zapytać swojego nauczyciela, czy język jest taki sam jak język . Jeśli powie „tak”, powiedz mu, że powiedziałem ci, że jego pytanie było źle sformułowane.

L

$L$

K = {a^{n_{1}} b^{m_{1}} a^{n_{2}} b^{m_{2}} \dots a^{n_{r}} b^{n_{r}} ∣ r \geq 0, a_{1}, \dots, a_{r} \geq 0, b_{1}, \dots, b_{r} \geq 0}

$K = \lbrace a^{n_1} b^{m_1} a^{n_2} b^{m_2} \cdots a^{n_r} b^{n_r} \mid r \geq 0, a_1, \ldots, a_r \geq 0, b_1, \ldots, b_r \geq 0\rbrace$

Andrej Bauer

Wydaje się, że jedynym sposobem, może to być regularne, aw rzeczywistości jest to, co pierwotnie szybko myśli i rzeczywiście uznać (a b ) *, ale potem usunięte to realizując N i M pozostają takie same (lub powinien ..), i dał odrzucenie lematu pompującego dla r = 2, mówiąc, że to samo dotyczyło większego r (prawdopodobnie też nie jest to kompletne rozwiązanie, ale wydaje się, że jest w dobrym kierunku). Nie trzeba dodawać, że dostałem 0 za to pytanie. Spróbuję się z nim skontaktować.

Z pewnością zrozumiałbym pytanie tak, jak na początku.

Andrej Bauer

Zobacz tutaj na więcej sposobów, aby pokazać, że język nie jest regularny.

Raphael

możesz to również udowodnić za pomocą pompowania lematu

SAHIL THUKRAL

Odpowiedzi:

Język nie jest regularny, co można udowodnić za pomocą metody Nerode. Rozważ następujące słowa dla . Następnie , ale dla , . Dlatego każdy automat dla musi znajdować się w innym stanie po odczytaniu każdego , co jest sprzeczne z jego skończonością. $L$ $w_n = a^n b$ $n \in \mathbb{N}$ $w_n^2 \in L$ $n \neq m$ $w_n w_m \notin L$ $L$ $w_n$

Yuval Filmus
źródło

W swoim komentarzu zasugerowałeś, że (zacytowałeś) „dałeś odrzucenie lematu pompującego dla , mówiąc, że to samo dotyczyło większego ”. $r=2$ $r$

Można to rzeczywiście sformalizować, stosując właściwość zamknięcia. Zwykłe języki są zamknięte pod skrzyżowaniem. Więc jeśli jest regularne, to tak też byłoby , skutecznie ustawiając i . $L$ $L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\}$ $r=2$ $m=1$

Hendrik Jan
źródło

Drogi czytelniku, proszę nie zabieraj „jeśli nie jest regularne, to też ” tutaj - bo to po prostu fałsz!

L

$L$

L^{'} \supset L

$L' \supset L$

Raphael

@Raphael Right. Zatem poprawną implikacją byłoby „jeśli nie jest regularne, to też nie jest ”, gdzie jest regularne.

L \cap R

$L\cap R$

L

$L$

R

$R$

Hendrik Jan

Oczywiście. Obawiałem się, że nowicjusze mogą przeczytać „skuteczne ustawienie ...” i zastosować to bez użycia właściwości zamknięcia.

Raphael

Język: {(a ⁿ b ^m ) ^r | n, m, r≥0} nie jest regularny, ponieważ chociaż automat / maszyna odczytuje pierwszą sekwencję liter „a”, a następnie liter „b”, musi policzyć, ile razy przeczytał literę „a” i ile razy czytał literę „b” w pierwszej sekwencji, aby poznać wartość n i m .

Jeżeli r> 1, to oczekiwana jest kolejna taka sama sekwencja liter „a” i liter „b”.

Jeśli automat / maszyna ma nie wiedzieć, ile liter „A” i litery „B” to przeczytać w pierwszej kolejności to też ma nie znać wartość n i m , a zatem może nie powiedzieć, czy pozostałe sekwencje od drugiej do ostatniej to słowa, które są równe pierwszej sekwencji.

Ale wiadomo, że tylko maszyny Turinga można liczyć i wiedzieć wartości n i m i rozpoznaje język powyżej, więc nie tylko, że język powyżej jest nie regularny, ale nawet to też jest nie kontekst wolny, czyli robi także nie istnieje automatyczny system rozpoznawania tego języka i nie istnieje gramatyka bezkontekstowa, że każde słowo pochodzące z tej gramatyki bezkontekstowej znajduje się w powyższym języku.

Ze względu na fakt, że zarówno deterministyczny automat skończony automat skończony i rozwijana do dołu może nie liczyć i wiedzieć wartości n i m , w odróżnieniu od maszyny Turinga, mogą nie rozpoznać powyższy język, a zatem powyższe język jest nie za darmo kontekst i nie jest regularny.

Przeciwprzykładem do założenia, że powyższy język jest regularny:

Dla n = 3 ∧ m = 5 ∧ r = 2 następujące słowo jest w powyższym języku:

aaabbbbbaaabbbbb

Ale następujące słowo nie jest w języku:

aaabbbbbaaaaabbb, ponieważ nie istnieje n, m i r więc:

(a ⁿ b ^m ) ^r = aaabbbbbaaaaabbb, ponieważ aby spełnić pierwszą sekwencję liter „a”, a następnie liter „b”, musi być prawdą, że n = 3 ∧ m = 5 , i ponieważ widzimy 2 sekwencje liter ” a ', a następnie litery' b ', następnie r = 2 , ale jeśli n = 3 ∧ m = 5 ∧ r = 2, to (a ⁿ b ^m ) ^r = (a ³ b ⁵ ) ² = (aaabbbbb) ² = aaabbbbbaaabbbbb ≠ aaabbbbbaaaaabbb, ponieważ ich sufiksy są różne, tj. Aaabbbbb ≠ aaaaabbb, chociaż ich prefiksy są równe aaabbbbb dla r = 1.

„Najlepszy” deterministyczny automat skończony, który można zbudować dla tego języka, to deterministyczny automat skończony, który rozpoznaje wyrażenie regularne (a * b *) *, ale nie rozpoznaje powyższego języka, ponieważ mówi, że oba słowa aaabbbbbaaabbbbb i aaabbbbbabaaaabbb są w języku i to nie jest prawda, ponieważ aaabbbbbaaabbbbb jest w języku, ale aaabbbbbaaaaabbb nie jest w tym języku.

Nawet automat skończony przesuwający w dół nie może stwierdzić, czy oba słowa są w języku, czy nie, więc tylko maszyna Turinga może to zrobić.

W drugiej sekwencji maszyna Turinga stwierdziła, że n = 5 ∧ m = 3, a to przeczy temu, że w pierwszej sekwencji stwierdził, że n = 3 ∧ m = 5 , więc mówi, że drugie słowo nie jest w języku , ale w pierwszym słowie nie znaleziono sprzeczności.

Obie sekwencje spełniają, że n = 3 ∧ m = 5 , więc maszyna Turinga mówi, że pierwsze słowo jest w języku.

Tylko Turinga maszyna może, jeśli liczy się i zapamiętuje wartości n i m pisząc swoją wartość na jego taśmy i później je odczytać.

Pożegnalna wymiana stosów
źródło