Wenn

8

Wir haben zwei Sprachen: L1,L2 . Wir wissen, dass L1L2 eine reguläre Sprache ist. Meine Frage ist also, ob L2L1 eine reguläre Sprache ist.

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

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

Ich hätte gerne einen Hinweis!

Vielen Dank!

stud1
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Raphael

Antworten:

7

Nein, ist nicht unbedingt regelmäßig.L2L1

Sei , was regulär ist, und L 2 = { 1 } { 0 n 1 nn 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 L1={0,1}L2={1}{0n1nn1}L1L21L2L110 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{0m1nm,n1}{0m1n1mn}

David Richerby
quelle
Danke David, aber warum ist das " " bei L 2 ? warum brauchen wir es Vielen Dank! {1}L2
Stud1
1
@ stud1 Um sicherzustellen, dass regelmäßig ist. L1L2
David Richerby
Aber (ohne { 1 } ) sind es immer noch alle Wörter, die mit 1 enden , oder? Also versuche ich immer noch zu verstehen, warum wir die { 1 } brauchen , ich hoffe es ist in Ordnung, ich frage es :-) Danke! L1L2{1}1{1}
Stud1
1
@ stud1 Wenn Sie löschen, dann zum Beispiel 1 {1} . Im Allgemeinen wären die einzigen Zeichenfolgen, die in L 1 L 2 wären, diejenigen, diefür m n 1 mit 0 m w n enden. 1L1L2L1L20mwnmn1
David Richerby
1
@ stud1 Richtig.
David Richerby
13

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 1L1={1pp is prime}L2={10} was regulär ist, aber L 2 L 1 = { 1 0 1 pp  ist Primzahl }, was nicht regulär ist.L1L2={11+0}L2L1={101pp is prime}

Vor
quelle
1
Elegante Lösung!
Anton Trunov
2
@AntonTrunov: ziemlich elegant :-) kann verwendet werden, um nicht reguläres UNARY L 1 zu "maskieren", aber sobald sie getauscht werden, wird L 1 wieder "freigelegt" :-)L2={10}L1L1
Vor
Was bedeutet bei 11 + ? +11+
Stud1
1
@ stud1: bedeutet "eine oder mehrere 1 s "; Mit anderen Worten, es ist eine "Abkürzung" für { 1 nn 1 } . Also { 11 + 0 } =1+1s{1nn1}{11+0}={110,1110,11110,...}
Vor
6

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.L2L1

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 } .AAAA{a}

Definieren Sie und L 2 = A { b } . Dann erhalten Sie L 1L 2 = { b } A 2{ b } , was regulär ist. Jedoch L 2L 1 = A { b b } A , die sich leicht als nicht-regulären nachgewiesen werden kann, bezogen auf AL1={b}AL2=A{b}L1L2={b}A2{b}L2L1=A{bb}AA nicht regelmäßig sein.

Shaull
quelle
1

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 *

Shashi Kumar
quelle