Unia zwykłych języków, która nie jest regularna

12

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ć język regularny.

I myślę, że rozumiem tego dowód: moim słowem, jeśli języki są regularne, to istnieją automaty, które je rozpoznają. Jeśli weźmiemy wszystkie stany (unia) i dodamy nowy stan dla punktu wejścia i zmodyfikujemy funkcję przejścia dla nowego stanu za pomocą epsilon, wszystko będzie w porządku. Pokazujemy również, że istnieje ścieżka z każdego stanu itp.

Czy możesz mi powiedzieć, gdzie się mylę, a może w inny sposób podejść do pytania.

Źródło pytania, ćwiczenie 4, w języku francuskim.

To samo pytanie zadaje się również na skrzyżowaniu.

formal-languages regular-languages closure-properties

— Dave
źródło

Inny sposób, aby to zobaczyć. Załóżmy, że taki nieskończony związek daje regularny język. Rozważmy dowolny język Nieregularnie

. Możesz podzielić jego elementy na nieskończoną liczbę podjęzyków

gdzie każdy z

jest skończony (a zatem regularny). Teraz wykonaj połączenie wszystkich

. Z założenia jest to język regularny, ale założyliśmy, że

jest językiem nieregularnym, stąd sprzeczność. Umożliwienie zamknięcia w ramach unii nieskończonej sprawiłoby, że wszystkie języki byłyby prawidłowe.

L

$L$

L_{i}

$L_i$

L_{i}

$L_i$

L_{i}

$L_i$

L

$L$

— Bakuriu

Dla nieskończonej unii: weź dowolny nieregularny język

i rozważ każde

. Najwyraźniej

jest regularne.

L = {w_{1}, w_{2}, w_{3}, \dots}

$L = \{w_1, w_2, w_3, \dots \}$

L_{i} = {w_{i}}

$L_i = \{w_i\}$

L_{i}

$L_i$

— Pål GD

26

Istnieje znacząca różnica między pytaniem, jakie zadajesz, a pytaniem postawionym w ćwiczeniu. Pytanie dotyczy przykładu zestawu regularnych języków takich, że ich związek nie jest regularny. Zwróć uwagę na zasięg unii: do . Zwykłe języki są zamknięte w ramach skończonej jedności, a dowody biegną wzdłuż linii, które szkicujesz w pytaniu, jednak rozpada się to w nieskończonej jedności. Możemy to pokazać, przyjmując $L_{1}, L_{2}, \ldots$

L = ⋃_{i = 1}^{\infty} L_{i}

$L = \bigcup_{i=1}^{\infty}L_{i}$

1

$1$

\infty

$\infty$

dla każdego

(przy

). Nieskończony związek tych języków daje oczywiście kanoniczny nieregularny (bezkontekstowy) język

.

L_{i} = {0^{i} 1^{i}}

$L_{i} = \{0^{i}1^{i}\}$

i

$i$

Σ = {0, 1}

$\Sigma = \{0,1\}$

L = {0^{i} 1^{i} ∣ i \in N}

$L = \{0^{i}1^{i}\mid i \in \mathbb{N}\}$

Nawiasem mówiąc, możemy łatwo zobaczyć, gdzie zawodzi normalny dowód. Wyobraź sobie tę samą konstrukcję, w której dodajemy nowy stan początkowy i przejścia do starych stanów początkowych. Jeśli zrobimy to z nieskończonym zestawem automatów, zbudujemy automaty z nieskończoną liczbą stanów, oczywiście sprzeczne z definicją automatów skończonych . $\varepsilon$

Wreszcie zgaduję, że zamieszanie może wynikać ze sformułowania pierwotnego pytania, które zaczyna się od „Donner deux exemples des suites de langages ...”, co oznacza (z ~~grubsza~~ , mój francuski jest trochę zardzewiały, ale zewnętrznie zweryfikowany!) „Podaj dwa przykłady sekwencji języków ...” zamiast „Podaj dwa przykłady języków ...”. Nieostrożne czytanie może jednak pomylić drugie z pierwszym.

— Luke Mathieson
źródło

1

Oraz określenie

jak set-dopełnienie

ich skrzyżowanie byłoby również nieregularne. Twoja francuska lektura jest słuszna, nie tylko z grubsza .

M_{i}

$M_i$

L_{i}

$L_i$

— Laurent LA RIZZA

Masz rację co do francuskiej części tłumaczenia. Myślałem, że ta część sekwencji nie była ważna. ha ha. Dzięki za odpowiedź, różnica jest teraz dla mnie jasna.

— Dave

3

W przypadku drugiego pytania rozważ języki zdefiniowane przez Zauważ, że dla dowolnego , jest regularne , ponieważ (1) lewy zbiór jest skończony, a zatem regularny, (2) prawy zbiór jest oznaczony wyrażeniem regularnym

{M.}_{n} = {{za}^{k^{2)}} ∣ 1 \leq k \leq n} \cup {{za}^{jot} ∣ jot \geq (n + 1)^{2)}}

$M_n = \{a^{k^2}\mid 1\le k \le n\}\cup\{a^j\mid j\ge(n+1)^2\}$

n \geq 1

$n\ge 1$

M_{n}

$M_n$

a^{n} a a^{*}

$a^naa^*$ tak samo jest i (3) zwykłe języki są zamknięte w skończonych związkach, jak już wiesz.

Nietrudno jest pokazać, że dla dowolnej liczby całkowitej mamy a zatem więc indukcyjnie mamy (czego tak naprawdę nie potrzebujemy tutaj, ale jest zbyt ładny, aby go pominąć). $n\ge 1$ $M_{n+1}\subseteq M_n$ $M_n\cap M_{n+1} = M_{n+1}$

⋂_{ja = 0}^{n} {M.}_{ja} = {M.}_{n}

$\bigcap_{i=0}^n M_i = M_n$

$M_n$ $a^{n^2+1},a^{n^2+2}, \dotsc, a^{(n+1)^2-1}$

⋂_{ja = 0}^{\infty} {M.}_{ja} = {{za}^{n^{2)}} ∣ n \geq 1}

$\bigcap_{i=0}^\infty M_i = \{a^{n^2}\mid n\ge 1\}$ który nie jest językiem regularnym. (Jeśli nie znasz tego faktu, jest w wielu tekstach teoretycznych, a dowód jest wart wysiłku przeczytania.)

— Rick Decker
źródło

1

Po co wybierać skomplikowane regularne języki, aby pokazać, że regularne zestawy nie są zamknięte w nieskończonej unii? Języki singleton są wystarczające, aby pokazać, że każdy język RE jest nieskończonym związkiem regularnych zbiorów.

$L$ $w\in L$ $i=index(w)$ $L_i=\{w\mid i=index(w)\}$ $L_i$ $L =\bigcup_{i=1}^{\infty}L_i\;$ jest RE.

$M_i=\Sigma^*\setminus L_i$ $M_i$ $\bigcap_{i=1}^{\infty}M_i= \Sigma^*\setminus L\;$ $L$

Stąd każdy język rekurencyjny jest nieskończonym połączeniem zbiorów regularnych, a także nieskończonym przecięciem zbiorów regularnych (nie tych samych, ale ich uzupełnień :).

Nieskończoność jest pełna niespodzianek, a to, co jest prawdziwe dla dowolnie dużych wartości, może nie być prawdziwe w nieskończoności.

— Babou
źródło

1

$\{\epsilon\} \bigcup \{a\} \bigcup \{b\} \bigcup \{aa\} \bigcup \{bb\} \bigcup \{aaa\} \bigcup \{aba\} \bigcup \{bab\} \bigcup \{bbb\} \bigcup \ ...$

$\Sigma^* - \{ p_i \}$ $p_i$ $i$

— Andres
źródło