Espressioni regolari
UN Regular Expression può essere definito ricorsivamente come segue:
ε è un'espressione regolare indica la lingua contenente una stringa vuota. (L (ε) = {ε})
φ è un'espressione regolare che denota una lingua vuota. (L (φ) = { })
x è un'espressione regolare dove L = {x}
Se X è un'espressione regolare che denota la lingua L(X) e Y è un'espressione regolare che denota la lingua L(Y), poi
X + Y è un'espressione regolare corrispondente alla lingua L(X) ∪ L(Y) dove L(X+Y) = L(X) ∪ L(Y).
X . Y è un'espressione regolare corrispondente alla lingua L(X) . L(Y) dove L(X.Y) = L(X) . L(Y)
R* è un'espressione regolare corrispondente alla lingua L(R*)dove L(R*) = (L(R))*
Se applichiamo una delle regole più volte da 1 a 5, si tratta di espressioni regolari.
Alcuni esempi di RE
| Espressioni regolari | Set regolare |
|---|---|
| (0 + 10 *) | L = {0, 1, 10, 100, 1000, 10000,…} |
| (0 * 10 *) | L = {1, 01, 10, 010, 0010,…} |
| (0 + ε) (1 + ε) | L = {ε, 0, 1, 01} |
| (a + b) * | Insieme di stringhe di a e b di qualsiasi lunghezza inclusa la stringa nulla. Quindi L = {ε, a, b, aa, ab, bb, ba, aaa …….} |
| (a + b) * abb | Insieme di stringhe di a e b che terminano con la stringa abb. Quindi L = {abb, aabb, babb, aaabb, ababb, ………… ..} |
| (11) * | Insieme composto da un numero pari di 1 inclusa una stringa vuota, quindi L = {ε, 11, 1111, 111111, ……….} |
| (aa) * (bb) * b | Insieme di stringhe composto da un numero pari di a seguito da un numero dispari di b, quindi L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..} |
| (aa + ab + ba + bb) * | Le stringhe di a e b di lunghezza pari possono essere ottenute concatenando qualsiasi combinazione delle stringhe aa, ab, ba e bb compreso null, quindi L = {aa, ab, ba, bb, aaab, aaba, ………… .. } |