Reguläre Ausdrücke

EIN Regular Expression kann rekursiv wie folgt definiert werden:

• ε ist ein regulärer Ausdruck, der die Sprache angibt, die eine leere Zeichenfolge enthält. (L (ε) = {ε})

• φ ist ein regulärer Ausdruck, der eine leere Sprache bezeichnet. (L (φ) = { })

• x ist ein regulärer Ausdruck, bei dem L = {x}

• Wenn X ist ein regulärer Ausdruck, der die Sprache bezeichnet L(X) und Y ist ein regulärer Ausdruck, der die Sprache bezeichnet L(Y), dann

  • X + Y ist ein regulärer Ausdruck, der der Sprache entspricht L(X) ∪ L(Y) wo L(X+Y) = L(X) ∪ L(Y).

  • X . Y ist ein regulärer Ausdruck, der der Sprache entspricht L(X) . L(Y) wo L(X.Y) = L(X) . L(Y)

  • R* ist ein regulärer Ausdruck, der der Sprache entspricht L(R*)wo L(R*) = (L(R))*

• Wenn wir eine der Regeln mehrmals von 1 bis 5 anwenden, handelt es sich um reguläre Ausdrücke.

Einige RE-Beispiele

Reguläre Ausdrücke	Reguläres Set
(0 + 10 *)	L = {0, 1, 10, 100, 1000, 10000,…}
(0 * 10 *)	L = {1, 01, 10, 010, 0010,…}
(0 + & epsi;) (1 + & epsi;)	L = {ε, 0, 1, 01}
(a + b) *	Satz von Zeichenfolgen von a und b beliebiger Länge, einschließlich der Nullzeichenfolge. Also L = {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb	Satz von Zeichenfolgen von a und b, die mit der Zeichenfolge abb enden. Also L = {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) *	Set bestehend aus einer geraden Anzahl von Einsen einschließlich leerer Zeichenfolge, also L = {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b	Satz von Zeichenfolgen, bestehend aus einer geraden Anzahl von a, gefolgt von einer ungeraden Anzahl von b, also L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) *	Zeichenfolgen von a und b von gerader Länge können erhalten werden, indem eine beliebige Kombination der Zeichenfolgen aa, ab, ba und bb einschließlich null verkettet wird, also L = {aa, ab, ba, bb, aaab, aaba, ………… .. }}