Wenn

Wir haben zwei Sprachen: $L_1,L_2$ . Wir wissen, dass $L_1L_2$ eine reguläre Sprache ist. Meine Frage ist also, ob $L_2L_1$ eine reguläre Sprache ist.

Ich versuche einen Weg zu finden, es zu beweisen ...

Ich kann natürlich nicht davon ausgehen, dass $L_1,L_2$ regulär sind ...
Also suche ich nach einem Weg, dies zu beweisen.

Ich hätte gerne einen Hinweis!

Vielen Dank!

Nein, ist nicht unbedingt regelmäßig.$L_2L_1$

Sei , was regulär ist, und L 2 = { 1 } ∪ { 0 n 1 n ∣ n ≥ 1 } , was nicht ist. Dann ist L 1 L 2 die Menge aller Zeichenfolgen, die mit 1 enden  , was regulär ist, aber L 2 L 1 ist die Menge aller Zeichenfolgen, die entweder mit  1 beginnen und mit einer Zahl ungleich Null von  0 s beginnen, gefolgt von mindestens ebenso vielen $L_1 = \{0,1\}^*$$L_2 = \{1\} \cup \{0^n1^n\mid n\geq 1\}$$L_1L_2$$1$$L_2L_1$$1$$0$ s. Diese Sprache ist nicht regulär, da sein Schnittpunkt mit { 0 m 1 n | m , n ≥ 1 } ist { 0 m 1 n | 1 ≤ m ≤ n } , die nicht regelmäßig ist.$1$$\{0^m1^n\mid m,n\geq 1\}$$\{0^m1^n\mid 1\leq m\leq n\}$

Ich habe nur einen Hinweis gepostet, dann habe ich andere vollständige Antworten gesehen, also ist dies eine vollständige (versteckte) prägnante Lösung :-)

Sei , L 2 = { 1 ∗ 0 } ; wir haben L $L_1 = \{ 1^p \mid p \text{ is prime}\}$$L_2 = \{ 1^* 0 \}$ was regulär ist, aber L 2 L 1 = { 1 ∗ 0 1 p ∣ p  ist Primzahl }, was nicht regulär ist.$L_1 L_2 = \{ 11^+ 0\}$$L_2 L_1 = \{ 1^* 0 1^p \mid p \text { is prime}\}$

Dies ist kein Hinweis, sondern eine vollständige Antwort. Lesen Sie nicht weiter, wenn Sie immer noch versuchen zu lösen.

Es besteht keine Notwendigkeit für regelmäßig.$L_2\cdot L_1$

Sei eine unäre (nicht reguläre) Sprache, so dass A ⋅ A regulär ist. Solche Sprachen finden Sie in der Post hier . Angenommen, A steht über dem Alphabet { a } .$A$$A\cdot A$$A$$\{a\}$

Definieren Sie und L 2 = A ⋅ { b } . Dann erhalten Sie L 1 ⋅ L 2 = { b } ⋅ A 2 ⋅ { b } , was regulär ist. Jedoch L 2 ⋅ L 1 = A ⋅ { b b } ⋅ A , die sich leicht als nicht-regulären nachgewiesen werden kann, bezogen auf $L_1=\{b\}\cdot A$$L_2=A\cdot \{b\}$$L_1\cdot L_2=\{b\}\cdot A^2\cdot \{b\}$$L_2\cdot L_1=A\cdot \{bb\}\cdot A$$A$ nicht regelmäßig sein.

Die folgenden Regeln definieren die Sprache, die einem regulären Ausdruck zugeordnet ist. Regel 1 Die Sprache, die dem regulären Ausdruck zugeordnet ist, der nur ein einzelner Buchstabe ist, ist nur das Wort aus einem Buchstaben, und die Sprache, die A zugeordnet ist, ist nur {A}, eine Sprache mit einem Wort. Regel 2 Wenn r ein regulärer Ausdruck ist, der der Sprache L zugeordnet ist, und r 2 ein regulärer Ausdruck ist, der der Sprache L2 zugeordnet ist, dann

(i) Der reguläre Ausdruck (rl) (r2) ist der Sprache L, mal L 2 zugeordnet. Sprache (r, r2) = L1L 2 (ii) Der reguläre Ausdruck r, + r2 ist der Sprache zugeordnet, die durch die Vereinigung der Mengen L1 und L2. Sprache (rl + r2) = L, + L2 (iii) Die Sprache, die dem regulären Ausdruck (rl) * zugeordnet ist, ist LI *, der Kleene-Abschluss der Menge LI als eine Menge von Wörtern. Sprache (rl *) = L1 *