Wyrażenie regularne (informatyka teoretyczna)
Z Wikipedii
Zasugerowano, aby ten artykuł (lub sekcję) zintegrować z artykułem Wyrażenie regularne. |
Wyrażeniem regularnym nazywamy ciąg znaków składający się z symboli oraz liter alfabetu, który definiuje pewien język formalny. Każdy język definiowany przez wyrażenie regularne jest regularny.
Spis treści |
[edytuj] Formalna definicja
Język definiowany przez wyrażenie regularne jest definiowany indukcyjnie. Niech L(w) oznacza język definiowany przez w. Wtedy baza indukcji jest następująca:
- (zbiór pusty)
- dla dowolnego a z alfabetu
Natomiast do konstrukcji wyrażeń służą 3 symbole:
[edytuj] Przykłady
[edytuj] Przykład 1
Wyrażenie definiuje język wszystkich słów nad alfabetem {a,b}, które zawierają podsłowo baba.
[edytuj] Przykład 2
Język złożony z tych słów, które nie zawierają dwóch kolejnych jedynek i mają parzystą liczbę zer, może być definiowany następująco: