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