Reguläre Ausdrücke - Sie sind die gleichen regulären Ausdrücke?

Question

Ich habe zwei Fragen. Sind diese regulären Ausdrücke gleich?

(1) b * (b *) * und (b * a) * b *

(2) b * (aaab *) * und (b * aaa) * b *

Ich habe das Gefühl, dass beide Sprachen schaffen, die Palindromwelten haben. Ist das richtig? In der ersten sind beide a sind must und b sind null oder unbegrenzt. Der zweite ist der gleiche. Die Zeichenfolge aaa ist ein Muss in beiden und b sind Null oder unbegrenzt.

Bin ich richtig?

Answer 1

In beiden Fällen sind die beiden regulären Ausdrücke nicht identisch (sie sind unterschiedliche reguläre Ausdrücke), aber sie beschreiben die gleiche Sprache tun. Also ist die Antwort auf beide Fragen (von deinen Übungen?) "Ja".

Im ersten Fall der regulären Ausdrücke beschreiben die Sprache jede Reihe von a ‚s und b‘ s. Im zweiten Fall erhalten Sie die Sprache, in der alle a in Tripeln vorkommen, wie die Kombination aaa. Diese erste Sprache wird auch durch den regulären Ausdruck (a|b)* (oder (a + b)* oder (a U b)* beschrieben, ich weiß nicht, welche Notation Ihr Buch verwendet), und die zweite Sprache wird auch durch den regulären Ausdruck (aaa|b)* beschrieben.

In beiden Fällen bleiben die Sprachen gleich, wenn Sie die Elemente umkehren. Wenn Sie also die regulären Ausdrücke, die sie beschreiben, umkehren, bleiben sie gleich.

Palindrome sind Wörter, die selbst bleiben die gleichen, wenn Sie sie umkehren. Aber beide Sprachen haben Elemente, die sind nicht Palindrome, wie zum Beispiel das Wort aaab, weil aaab! = baaa. Über Palindrome zu sprechen, ist hier nicht das richtige Argument.