Regulärer Sprachverschluß unter Einfügen

Question

Angenommen, ich habe eine reguläre Sprache L unter Alphabet Σ. Wie zeige ich, dass die Sprache L 'noch eine reguläre Sprache ist, wenn ich ein Symbol in der Mitte einfüge?

Zum Beispiel enthält L eine Zeichenkette w, die aus zwei Teilstrings u und v besteht (w = uv) Ich möchte zeigen, dass eine reguläre Sprache L 'eine Zeichenkette uxv enthält, wobei x das eingefügte Symbol ist.

Beachten Sie, dass u und v nicht die gleiche Länge haben müssen und x auch im selben Alphabet Σ steht.

Vielen Dank!

Answer 1

Da L regulär ist, gibt es einen endlichen Automaten A, der es akzeptiert. Machen Sie zwei Kopien (A1 und A2) von A. In A2 machen Sie den Startzustand nicht initial. Fügen Sie für jeden Zustand p in A1 einen Übergang p --x -> p zum entsprechenden Zustand in A2 hinzu.

Mit der Beispielnotation liest A1 jetzt u, die neue Transition liest x und A2 liest v.