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, ………… .. } |