Czy

12

Jeśli jest regularne, to czy wynika z tego, że jest regularne? $A^2$ $A$

Moja próba na dowód:

Tak, ponieważ sprzeczność zakłada, że nie jest regularne. Następnie . $A$ $A^2 = A \cdot A$

Ponieważ łączenie dwóch nieregularnych języków nie jest regularne, nie może być regularne. Jest to sprzeczne z naszym założeniem. Więc jest regularne. Więc jeśli jest regularne, to jest regularne. $A^2$ $A$ $A^2$ $A$

Czy dowód jest poprawny?

Czy możemy to uogólnić na , itd.? A jeśli jest regularne, to nie musi być regularne? $A^3$ $A^4$ $A^*$ $A$

Przykład: nie jest regularny, ale jest regularny. $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ $A^*$

formal-languages regular-languages closure-properties akshay
źródło

2

Pierwszy dowód to ogromny skok. Jaki jest twój dowód na to, że nie jest regularne, co oznacza, że nie jest regularne? Udowodnienie, że właściwie, może prowadzić do intuicji, która pomoże odpowiedzieć na resztę pytania, jeśli rzeczywiście jest to prawda.

A

$A$

A^{2}

$A^2$

Dave Clarke

@DaveClarke Edytował dowód.

akshay

3

Jak udaje Ci się przeliterować „Czy jestem poprawny?” ten sposób jest bardzo intrygujący. Jako ogólna rada: kiedy setki ludzi czytają to, co napisałeś, ogólna przyzwoitość wymaga, abyś zwracał uwagę na to, jak piszesz ... ;-)

Andrej Bauer,

6

@AndrejBauer OP może być kimś, kto nie jest ojczystym językiem angielskim i który mógł jeszcze nie mieć możliwości uzyskania instrukcji na temat formalnego języka angielskiego. Nie jest to powód, aby zniechęcać kogokolwiek, chociaż może być pomocny w ich poprawieniu.

Yuval Filmus

28

Rozważ cztery kwadratowe twierdzenie Lagrange'a . Stwierdza, że jeśli a następnie . Jeśli jest regularne, weź , w przeciwnym razie weź . Tak czy inaczej, to dowodzi istnienia nieregularnych takie, że jest regularny. $B = \{1^{n^2}| n \geq 0\}$ $B^4 = \{1^n | n \geq 0\}$ $B^2$ $A = B$ $A = B^2$ $A$ $A^2$

Karolis Juodelė
źródło

Nie rozumiem tego dowodu; czy mógłbyś trochę rozwinąć?

G. Bach,

2

Wyjaśniając to (piękne) dowód: Mamy że

, a

. Zauważ, że

. Teraz, jeśli

, to przyjmując

, mamy kontrprzykład, a jeśli

to biorąc

, mamy kontrprzykład.

B \notin R E G

$B\notin REG$

B^{4} \in R E G

$B^4\in REG$

B^{4} = (B^{2})^{2}

$B^4=(B^2)^2$

B^{2} \in R E G

$B^2\in REG$

A = B

$A=B$

B^{2} \notin R E G

$B^2\notin REG$

A = B^{2}

$A=B^2$

Shaull

1

Absolutnie piękna.

vonbrand

3

@YuvalFilmus, rzeczywiście, ale nie miałem dowodu i nie chciałem pozostawiać żadnych wątpliwości. Teraz wydaje mi się, że znalazłem. „Liczba

jest sumą dwóch kwadratów wtedy i tylko wtedy, gdy wszystkie czynniki pierwsze w postaci

mają nawet wykładnik w rozkładzie na czynniki pierwsze

”. Niech

będzie długością pompowania. Rozważ

. Niech

będzie liczbą pierwszą w postaci

i niech

będzie długością, którą wybieramy do pompowania. Następnie

n

$n$

4 k + 3

$4k+3$

n

$n$

n

$n$

w = (n!)^{2}

$w = (n!)^2$

p

$p$

4 k + 3

$4k+3$

m

$m$

ma nieparzysty wykładnik na

a zatem nie ma go w

.

w + (p - 1) \frac{w}{m} \cdot m = p w

$w + (p-1)\frac{w}{m}\cdot m = pw$

p

$p$

B^{2}

$B^2$

Karolis Juodelė

1

@ JonasKölker, zgadzam się.

Karolis Juodelė

8

Oto przykład języka, który nie jest obliczalny taki, że . Weź dowolny niepoliczalny (reprezentowany jako zestaw liczb, np. Kody zatrzymujących się maszyn Turinga) i zdefiniuj Więc zawiera wszystkie słowa, inne niż te, o długości dla pewnego . Jeśli $A$ $A^2 = \Sigma^*$ $K$

A = {w \in Σ^{*} : | w | \neq 4^{k} for all k \in K} .

$A = \{ w \in \Sigma^* : |w| \neq 4^k \text{ for all } k \in K \}.$

A

$A$

4^{k}

$4^k$

k \in K

$k \in K$

A

$A$ były obliczalne, to można było obliczyć

: biorąc pod uwagę

, ustalić, czy

(to znaczy

zera) jest w

czy nie. Ponieważ założyliśmy, że

nie jest obliczalny,

także musi być niepoliczalny.

K

$K$

k

$k$

0^{4^{k}}

$0^{4^k}$

4^{k}

$4^k$

A

$A$

K

$K$

A

$A$

Roszczenie: . Niech będzie dowolnym słowem o długości . Jeśli nie jest potęgą , to a puste słowo jest w , więc . Jeśli jest potęgą to nie jest potęgą . Napisz , gdzie $A^2 = \Sigma^*$ $w$ $n$ $n$ $4$ $w \in A$ $A$ $w \in A^2$ $n$ $4$ $n/2$ $4$ $w = xy$ . Zarówno więc . $|x| = |y| = n/2$ $x,y \in A$ $w = xy \in A^2$

Yuval Filmus
źródło

1

Dla początkujących, dowód szkic do „ nierozstrzygalne” może być w porządku. Niewielką przeszkodą może być to, że używasz

jako języka formalnego i zestawu liczb (co jest sprawiedliwe, przy założeniu odpowiedniej semantyki dla

, ale może nie jest znane). W przeciwnym razie bardzo fajny pomysł.

A

$A$

K

$K$

K

$K$

Raphael

2

Twój dowód wciąż robi ogromny skok (argumentując, że łączenie języków nieregularnych jest nieregularne).

Jeśli hipoteza Goldbacha jest prawdziwa, wówczas odpowiedź na pytanie brzmi: nie. Rozważ nieregularny język . Następnie według hipotezy Goldbacha , która jest regularna. $A=\{1^p: p\text{ is a prime}\}$ $A^2=\{1^{2k}: k>1\}$

Nie rozwiązuje to całkowicie pytania, ale daje mocny dowód, że odpowiedź jest przecząca (w przeciwnym razie hipoteza Goldbacha jest fałszywa). Jednak odpowiedź może być bardzo trudna do udowodnienia, jeśli jest to jedyny znany przykład.

Shaull
źródło

Co możemy wyciągnąć z tego pytania?

akshay

Zakładając, że hipoteza Goldbacha - jeśli

jest regularna, to

może nadal być nieregularna. A zatem: udowodnienie, że odpowiedź brzmi „tak”, oznaczałoby, że hipoteza Goldbacha jest fałszywa (mało prawdopodobna).

A^{2}

$A^2$

A

$A$

Shaull

2

W obecności „prawdziwych” dowodów nie sądzę, aby stosowanie niesprawdzonej hipotezy było sprawiedliwe. Może połączenie jest dla niektórych interesujące?

Raphael

Rzeczywiście, po poniższych odpowiedziach jest to zbędne. Można jednak zobaczyć tutaj ładny rozwój matematyczny: odpowiedź oparta na dobrze znanej hipotezie, a następnie odpowiedź pokrewną (używając twierdzenia Lagrange'a), która opiera się na podobnym pomyśle (rozkładając liczbę na sumę).

Shaull

1

W rzeczywistości, jeśli używasz liczb pierwszych i półpierwszych, możesz użyć twierdzenia Chena .

sdcvvc

2

Roszczenie jest błędne.

Niech będzie nieregularnym językiem, który jest „rzadki”: jeśli to każdy inny spełnia (lub ) . Nietrudno dostrzec, że wiele nieregularnych języków może być rzadkich. $D$ $x \in D$ $y\in D$ $|y| > 4|x|$ $|x|>4|y|$ ^$\dagger$

Teraz definiować . Z właściwości zamknięcia (uzupełnienia), musi być nieregularne. $A = \Sigma^* \setminus D$ $A$

Jednak (widzisz dlaczego?) $A^2 = \Sigma^*$ $\ \ \$

^$\dagger$_{Myślę, żewystarczy, ale może powodować pewne nieprzyjemne przypadki krawędzi. powinno wystarczyć, więc weźmybyć po bezpiecznej stronie. $|y|>2|x|$ $|y|>2|x|+2$ $|y|>4|x|$}

Ran G.
źródło

Podoba mi się, jak to pytanie staje się coraz bardziej trywialne. Twój pomysł na rzadkość można dodatkowo uprościć, wymagając, aby

i

1 \in A

$1 \in A$

.

1^{k} \notin A ⟹ 1^{k - 1} \in A

$1^k \notin A \implies 1^{k-1} \in A$

Karolis Juodelė

2

Weź dowolne nieregularne i zdefiniuj . $X \subseteq {1}^\ast$ $A=\{1\} \cup \{1^{2x}:x \in \mathbb N\} \cup \{1^{2x+1}:1^x \in X\}$

Łatwo zauważyć, że jest nieregularne, podczas gdy . $A$ $A^2=1^{\ast}$

sdcvvc
źródło

2

Niech będzie dowolnym niezdecydowanym zbiorem, niech i niech . jest nierozstrzygalny, więc na pewno nie jest regularny. Ale $U\subseteq \mathbb{N}$ $I = \{2u+1\mid u\in U\}\cup\{0,2,4,\dots\}$ $L = \{a^i\mid i\in I\}$ $L$ , która jest regularna, ponieważ jej uzupełnienie jest skończone. $L^2 = \{a^{2n}\mid n\in \mathbb{N}\} \cup \{a^n\mid n\geq \min\,I\}$

David Richerby
źródło

0

Innym przykładem z pytania oznaczonego jako duplikat tego jest rozważenie nieregularnego języka $\{a^k\mid m\text{ is composite}\}$ . Dowolna liczba parzysta jest sumą i , które są złożone; dowolna liczba nieparzysta jest sumą i , które są złożone ( dla niektórych ). Dlatego $n\geq 8$ $n-4$ $4$ $n\geq 13$ $n-9$ $9$ $n-9=2m$ $m\geq 2$ $A^2 = \{a^8,a^{10}\}\cup\{a^k\mid k\geq 12\}$ , który jest regularny, bo to co skończone (jest dopełnieniem $\{\epsilon,a,aa,\dots,a^6,a^7,a^9,a^{11}\}$ ).

David Richerby
źródło

Czy

Odpowiedzi: