Wyrażenie regularne (regex,
regexp)
Alternatywna forma opisu językow regularnych
Poniższe zapisy reprezentują wyrażenie regularne:
1.
Ø – zbiór pusty , L(Ø)= Ø
2.
ε – łańcuch pusty , L(ε) = {ε}
3.
a – symbol , L(a) = {a}
Jeżeli E jest wyrażeniem regularnym to:
4.
L(E*)=( L(E) )*
5.
L( (E) ) = L(E)
Jeżeli E
1
i E
2
są wyrażeniami regularnymi to:
6.
L(E
1
+E
2
) = L(E
1
) υ L(E
2
)
7.
L(E
1
E
2
) = L(E
1
)L(E
2
)
podstawa
krok
indukcyjny
DAS a wyrażenia regularne
Przekształcenia DAS na wyrażenie regularne
Usuwanie stanu s:
jeżeli stan s ma k poprzedników q
1
,q
2
,…,q
k
oraz m następników p
1
,p
2
,…,p
m
(różnych od
s) to po usunięciu stanu s rekompensując
połączenie ij dokładamy etykiety Q
i
S*P
j
gdzie Q
i
wyrażenie regularne od q
i
do s, S
wyrażenie regularne dla pętli w s, P
j
wyrażenie regularne od s do p
j
DAS a wyrażenia regularne
1.Etykietujemy łuki przejść grafu DAS poprzez wyrażenie regularne
2. Dla każdego stanu niekceptacyjnego q : usuwamy stan q
zgodnie z powyższym postępowaniem.
3. Dla każdego stanu akceptacyjnego:
a) Jeżeli stan akcetpujący≠ stanu początkowego: redukujemy
automat do postaci dwustanowej:
R
S
T
U
Z reprezentcają:
(R+SU*T)*SU*
b) Jeżeli stan akceptujący = stan początkowy, redukujemy
automat do postaci jednostanowej:
R
Z reprezentacją:
R*
DAS a wyrażenia regularne
4. Wyrażenie regularne reprezentujące
cały automat jest sumą wyrażeń z pkt.
3.
Przykład
0+1
A
1(0+1)
0+1
C
D
Po wyeliminowaniu B:
0,1
1
0,
1
0,
1
A
B
C
D
Finalnie:
(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)
Przekształcanie wyrażeń
regularnych na automaty
Przekształcamy do ε-NDAS o dokładnie jednym stanie
akceptującym, bez krawędzi wychodzących ze stanów:
akceptującego lub początkowego.
ε
a
ε
Ø
a
R
S
ε
ε
ε
ε
ε
R
S
R+S
RS
ε
ε
ε
R
ε
ε
R*
Konwersja DAS na wyrażenie regularne (jeżeli poleceniem byłoby
przekształcenie ENAS na wyrażenie regularne, to najpierw
przekształcamy ENAS na DAS i późnie dopiero DAS na wyrażenie
regularne.
Przykład: przekształćmy poniższy DAS na wyrażenie regularne.
q
0
q
1
q
2
q
3
1
1
0
0
0
0
1
1
pażysta liczba
1,
pażysta liczba
0
niepażysta liczba 1,
pażysta liczba 0
niepażysta liczba 1,
niepażysta liczba 0
pażysta liczba 1,
niepażysta liczba 0
Eliminujemy stany niekońcowe, zacznijmy np. od q
2
q
0
q
1
q
3
1
1
0
0
01
10
11
00
Eliminujemy stany niekońcowe, teraz q
3
q
0
q
1
1+
[01
+(1
1)*
+0
]
00+[01+(11)*+10]
1+
[0+
(11
)*+
10
]
[0+(11)*+0]
Szukane wyrażenie będzie zatem suma wyrażeń:
1)akceptowującego z pominięciem q
0
(nie możemy q
0
wyeliminować ponieważ jest to stan początkowy)
2) po eliminacji q
1
1) Pominięcie q
0
(ściślej stan q
0
pozostaje dalej, jednak interesuje
nas wyrażenie akceptowalne poprzez stan q
1
)
q
0
q
1
1+
[01
+(1
1)*
+0
]
00+[01+(11)*+10]
1+
[0+
(11
)*+
10
]
[0+(11)*+0]
Wyrażeniem jest:
//(pamiętamy wzór (R+SU*T)*SU*)
{ {00+[01+(11)*+10]} + {1+[01+(11)*+0]} {[0+(11)*+0]}* {1+[0+(11)*+10]} }
{1+[01+(11)*+0]} {[0+(11)*+0]}*
2) Eliminacja q
1
{00+[01+(11)*+10]}+{1+[01+(11)*+0]} {[0+(11)*+0]}*
{1+[0+(11)*+10]}
Wyrażeniem jest:
{00+[01+(11)*+10]}+{1+[01+(11)*+0]} {[0+(11)*+0]}* {1+[0+(11)*+10]}
Zatem finalnie, poszukiwanym wyrażeniem jest suma wyrażeń z
1) i 2) czyli:
{ {00+[01+(11)*+10]} + {1+[01+(11)*+0]} {[0+(11)*+0]}* {1+[0+(11)*+10]} }
{1+[01+(11)*+0]} {[0+(11)*+0]}* +
+ {00+[01+(11)*+10]}+{1+[01+(11)*+0]} {[0+(11)*+0]}* {1+[0+(11)*+10]}
Oczywiście powyższe wyrażenie można dalej jeszcze uprościć.
q
0