Ist

12

Wenn regulär ist, folgt daraus, dass regulär ist?A 2A2EINA

Mein Beweisversuch:

Ja, für den Widerspruch wird angenommen, dass nicht regulär ist. Dann .A AA 2 = A AA2=AA

Da die Verkettung von zwei nicht regulären Sprachen nicht regulär ist, kann nicht regulär sein. Dies widerspricht unserer Annahme. Also ist regelmäßig. Wenn also regulär ist, dann ist regulär.A 2A2 A AA 2A2 AA

Ist der Beweis richtig?

Können wir dies auf , usw. verallgemeinern ? Und auch wenn regulär ist, muss nicht regulär sein?A 3 A3A 4 A4A A AA

Beispiel: ist nicht regulär, aber ist regulär.A = { 1 2 ii 0 } A={12ii0}A A

akshay
quelle
2
Der erste Beweis macht einen großen Sprung. Was ist Ihr Beweis, dass nicht regulär ist, was bedeutet, dass nicht regulär ist? Wenn Sie dies beweisen, werden Sie möglicherweise eine Eingebung finden, die Ihnen hilft, den Rest der Frage zu beantworten, wenn dies tatsächlich der Fall ist. A A 2AA2
Dave Clarke
@ DaveClarke Bearbeitet den Beweis.
Akshay
3
Wie du es schaffst, "Am i Correct" zu schreiben? Dieser Weg ist sehr faszinierend. Ein allgemeiner Ratschlag: Wenn Hunderte von Menschen lesen, was Sie geschrieben haben, verlangt der allgemeine Anstand, dass Sie genau darauf achten, wie Sie schreiben ... ;-)
Andrej Bauer,
6
@AndrejBauer Das OP könnte jemand sein, der nicht Englisch als Muttersprache spricht und möglicherweise noch keine Gelegenheit hatte, Unterricht in formellem Englisch zu erhalten. Dies ist kein Grund, jemanden zu entmutigen, obwohl es hilfreich sein könnte, sie zu korrigieren.
Yuval Filmus

Antworten:

28

Betrachten wir Lagranges Vierquadratsatz . Es heißt, wenn B = { 1 n 2 | n 0 },B={1n2|n0} dann ist B 4 = { 1 n | n 0 }B4={1n|n0} . Wenn B 2B2 regulär ist, nimm A = B,A=B sonst nimm A = B 2A=B2 . In jedem Fall beweist dies die Existenz von unregelmäßigem A,A so dass A 2A2 regelmäßig ist.

Karolis Juodelė
quelle
Ich verstehe diesen Beweis nicht. Könntest du etwas näher darauf eingehen?
G. Bach
2
Erklären Sie diesen (schön) Beweis: Wir haben die B R E G , und das B 4R E G . Beachten Sie, dass B 4 = ( B 2 ) 2 ist . Wenn nun B 2R E G ist , dann haben wir durch Nehmen von A = B ein Gegenbeispiel, und wenn B 2R E G ist, dann haben wir durch Nehmen von A = B 2 ein Gegenbeispiel. BREGB4REGB4=(B2)2B2REGA=BB2REGA=B2
Shaull
1
Wunderschön.
Vonbrand
3
@YuvalFilmus, in der Tat, aber ich hatte keinen Beweis und wollte keinen Zweifel lassen. Jetzt scheine ich einen gefunden zu haben. "Eine Zahl n ist genau dann eine Summe von zwei Quadraten, wenn alle Primfaktoren der Form 4 k + 3 einen geraden Exponenten in der Primfaktorisierung von n haben ." Sei n die Pumplänge. Betrachte w = ( n ! ) 2 . Sei p eine Primzahl der Form 4 k + 3 und sei m die Länge, die wir pumpen möchten. Dann ist w + ( p - 1 )n4k+3nnw=(n!)2p4k+3mwmm=pwhat aufpeinen ungeraden Exponentenund ist daher nicht inB2. w+(p1)wmm=pwpB2
Karolis Juodelė
1
@ JonasKölker, stimme zu.
Karolis Juodelė
8

Hier ist ein Beispiel einer nicht berechenbaren Sprache A , so dass A 2 = Σ * . Nehmen Sie ein nicht berechenbares K (dargestellt als eine Menge von Zahlen, z. B. die Codes von Turing-Maschinen, die anhalten) und definieren Sie A = { w Σ : | w | 4 k  für alle  k K } . Also enthält A für einige k K alle Wörter mit Ausnahme von Wörtern der Länge 4 k . Wenn AAA2=ΣK

A={wΣ:|w|4k for all kK}.
A4kkKAWären berechenbar, könnten Sie K berechnen : Wenn k gegeben ist , bestimmen Sie, ob 0 4 k ( dh 4 k Nullen) in A sind oder nicht. Da wir angenommen haben, dass K nicht berechenbar ist, muss A auch nicht berechenbar sein.Kk04k4kAKA

Claim: A 2 = Σ * . Sei w ein beliebiges Wort der Länge n . Wenn n keine Potenz von 4 ist , dann ist w A und das leere Wort ist in A , also ist w A 2 . Wenn n eine Potenz von 4 ist, dann ist n / 2 keine Potenz von 4 . Schreiben Sie w = x y , wobei | x | = | y | = n /A2=Σwnn4wAAwA2n4n/24w=xy2 . Beide x , y A also w = x y A 2 .|x|=|y|=n/2x,yAw=xyA2

Yuval Filmus
quelle
1
For beginners, a proof sketch for "AA undecidable" may be in order. Also, a small hurdle may be that you use KK as a formal language and as a set of numbers (which is fair, assuming suitable semantics for KK, but maybe unfamiliar). Otherwise, very nice idea.
Raphael
2

Your proof still makes a huge jump (arguing that concatenation of non-regular languages is non-regular).

If the Goldbach conjecture is true, then the answer to the question is no: Consider the non-regular language A={1p:p is a prime}A={1p:p is a prime}. Then by the Goldbach conjecture, A2={12k:k>1}A2={12k:k>1}, which is regular.

This doesn't solve the question entirely, but it gives strong evidence that the answer is no (otherwise the Goldbach conjecture is false). However, the answer may be very hard to prove, if this is the only known example.

Shaull
quelle
What can we conclude about the question?
akshay
Assuming the Goldbach conjecture -if A2A2 is regular, than AA may still be non-regular. So: proving that the answer is "yes" would mean that the Goldbach conjecture is false (unlikely).
Shaull
2
In the presence of "real" proofs, I don't think using an unproven conjecture is fair. Maybe the connection is interesting for some?
Raphael
Indeed, after the following answers, this is redundant. However, you can see a nice mathematical development here: an answer based on a well known conjecture, then a related answer (using Lagrange's theorem), which is based on a similar idea (decomposing a number to a sum).
Shaull
1
In fact if you use primes and semiprimes, you can use Chen's theorem.
sdcvvc
2

The claim is wrong.

Let DD be non-regular language which is "sparse": if xDxD then any other yDyD satisfies |y|>4|x||y|>4|x| (or |x|>4|y||x|>4|y|). It's not too difficult to see that many non-regular languages can be sparse.

Now define A=ΣDA=ΣD. From closure properties (complementation), AA must be non-regular.

However, A2=ΣA2=Σ        (can you see why?)

I think |y|>2|x||y|>2|x| is enough, but may cause some nasty edge cases. |y|>2|x|+2|y|>2|x|+2 should be enough though, so let's take |y|>4|x||y|>4|x| to be on the safe side.

Ran G.
quelle
I like how this question is getting increasingly more trivial proofs. Your idea of sparseness could be further simplified to a requirement that 1A1A and 1kA1k1A1kA1k1A.
Karolis Juodelė
2

Take any nonregular X1X1 and define A={1}{12x:xN}{12x+1:1xX}A={1}{12x:xN}{12x+1:1xX}.

It is easy to see AA is nonregular, while A2=1A2=1.

sdcvvc
quelle
2

Let UNUN be any undecidable set, let I={2u+1uU}{0,2,4,}I={2u+1uU}{0,2,4,} and let L={aiiI}L={aiiI}. LL is undecidable so it certainly isn't regular. But L2={a2nnN}{annminI}L2={a2nnN}{annminI}, which is regular because its complement is finite.

David Richerby
quelle
0

Another example, from a question that was marked as a duplicate of this, is to consider the non-regular language {akm is composite}{akm is composite}. Any even number n8n8 is the sum of n4n4 and 44, which are both composite; any odd number n13n13 is the sum of n9n9 and 9, which are both composite (n9=2m for some m2). Therefore, A2={a8,a10}{akk12}, which is regular because it's co-finite (it's the complement of {ϵ,a,aa,,a6,a7,a9,a11}).

David Richerby
quelle