Expressions régulières

UNE Regular Expression peut être défini récursivement comme suit -

• ε est une expression régulière indique la langue contenant une chaîne vide. (L (ε) = {ε})

• φ est une expression régulière désignant une langue vide. (L (φ) = { })

• x est une expression régulière où L = {x}

• Si X est une expression régulière désignant la langue L(X) et Y est une expression régulière désignant la langue L(Y), puis

  • X + Y est une expression régulière correspondant à la langue L(X) ∪ L(Y) où L(X+Y) = L(X) ∪ L(Y).

  • X . Y est une expression régulière correspondant à la langue L(X) . L(Y) où L(X.Y) = L(X) . L(Y)

  • R* est une expression régulière correspondant à la langue L(R*)où L(R*) = (L(R))*

• Si nous appliquons l'une des règles plusieurs fois de 1 à 5, ce sont des expressions régulières.

Quelques exemples d'ER

Expressions régulières	Ensemble régulier
(0 + 10 *)	L = {0, 1, 10, 100, 1 000, 10 000,…}
(0 * 10 *)	L = {1, 01, 10, 010, 0010,…}
(0 + ε) (1 + ε)	L = {ε, 0, 1, 01}
(a + b) *	Ensemble de chaînes de a et de b de n'importe quelle longueur, y compris la chaîne nulle. Donc L = {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb	Ensemble de chaînes de a et de b se terminant par la chaîne abb. Donc L = {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) *	Ensemble composé d'un nombre pair de 1 incluant une chaîne vide, So L = {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b	Ensemble de chaînes composé d'un nombre pair de a suivi d'un nombre impair de b, donc L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) *	Une chaîne de a et de b de longueur paire peut être obtenue en concaténant toute combinaison des chaînes aa, ab, ba et bb incluant null, donc L = {aa, ab, ba, bb, aaab, aaba, ………… .. }