Pok-2-wyk-Slajd13
Wyrażenia regularne
Do opisu języków regularnych służą wyrażenia regularne.
1. Zbiór pusty jest wyrażeniem regularnym opisującym język regularny będący zbiorem pustym.
2. Epsilon jest wyrażeniem regularnym opisującym język regularny zawierający tylko symbol pusty.
3. Symbol a należący do alfabetu A jest wyrażeniem regularnym opisującym język regularny zawierający pojedynczy element a.
4. Jeżeli r1 i r2 są wyrażeniami regularnymi opisującymi odpowiednio języki regularne L1 i L2 to:
a) r1|r2 jest wyrażeniem regularnym opisującym język regularny będący sumą L1 i L2
b) r1r2 jest wyrażeniem regularnym opisującym język regularny będący złączeniem L1 i L2
c) r1* oraz r2* są wyrażeniami regularnymi opisującymi języki regularne będące domknięciami zwrotnymi L1 i L2
Aby pominąć nawiasy okrągłe wprowadzono następujące priorytety operatorów. Najwyższy priorytet posiada domknięcie zwrotne (czyli gwiazdka Kleene’go). Następnie jest złożenie. Najniższy priorytet posiada suma.
