Kleene Stern einer unendlichen unären Sprache ergibt immer eine reguläre Sprache

8

Sei , wobei a 0 = ϵ und a n = a n - 1 a für alle n 1 sind .L={ann0}a0=ϵan=an1an1

Somit besteht aus Sequenzen a aller Längen, einschließlich einer Sequenz der Länge 0 . Lassen L 2 sein , jede unendliche Teilmenge von L . Ich muss zeigen, dass es immer einen DFA gibt, um L 2 zu erkennen .La0L2LL2

Wenn eine endliche Teilmenge ist, ist es sehr offensichtlich, da L 2 ein DFA wäre und daher durch Kleene-Schließung L 2 von einem DFA erkannt würde. Ich kann es jedoch nicht für eine unendliche Teilmenge erhalten, da L 2 möglicherweise nicht als DFA ausgedrückt wird, wenn z. B. Zeichenfolgenlängen Primzahlen sind.L2L2L2L2

Aditya Nambiar
quelle

Antworten:

8

Angenommen, die Sprache enthält zwei Wörter, deren Länge relativ prim ist. Diese Längen seien und y . Wir wissen (siehe dies ), dass wir durch wiederholtes Addieren dieser Zahlen jede Zahl größer als ( x - 1 ) ( y - 1 ) - 1 erhalten können . Also , wenn x und y sind 13 und 7 , können wir eine beliebige Zahl größer als Schreib 72 als eine lineare Kombination von 7 und 13 . Was dies für uns bedeutet: L 2xy(x1)(y1)1xy13772713L2besteht aus einer beliebigen endlichen Sprache (regular, als alle endlichen Sprachen), in der Vereinigung mit der Sprache . Diese Sprache ist regulär, da sie die Sprache aller Wörter ist, bei denen eine endliche Menge von Wörtern entfernt wurde. Da L 2 eine Vereinigung regulärer Sprachen ist, muss es auch regulär sein.{wa|a|>(x1)(y1)1}L2

Wenn alle Wörter in Längen haben, die einen größten gemeinsamen Faktor haben (nennen Sie diesen gemeinsamen Faktor m ), wiederholen Sie das obige Argument, verwenden Sie jedoch anstelle von Zeichenfolgenlängen Zeichenfolgenlängen geteilt durch m . In diesem Fall L * 2 wird die Verkettung einer beliebigen endlichen Sprache (regular) und die Sprache seines { w ( eine m ) * | | w | > m 2 [ ( x / m - 1 ) ( y / mL2mmL2 , auch regulär (da $ (a ^ m) ^ * regulär ist und wir endlich viele Wörter daraus entfernen).{w(am)|w|>m2[(x/m1)(y/m1)1]}

La4a10m=2x/m=4/2=2y/m=10/2=5mm2[(x/m1)(y/m1)1]=22[(21)(51)1]=(4)(3)=12a4a10

Patrick87
quelle