Regulární výrazy – příklady k procvičení
Příklad 1
K následujícím jazykům zapište ekvivalentní regulární výrazy.
1. L1 = {w ∈ {a, b, c}∗
| w obsahuje podslovo bab};
2. L2 = {w ∈ {0, 1}∗
| w začíná 1 ∧ #0(w) = 3k + 1, k ∈ N0};
3. L3 = {w ∈ {a, b}∗
| w začíná a končí stejným symbolem};
4. L4 = {w ∈ {a, b, c}∗
| #a(w) + #b(w) = 4k, k ∈ N0}.
Příklad 2
K následujícím konečným automatům nalezněte ekvivalentní regulární výrazy.
1. M1 = ({q0, q1, q2}, {a, b, c}, δ, q0, {q2}), kde δ je dána:
q0 q1 q2
a a, c
b, c cb
δ a b c
→ q0 q1 q0 q0
q1 q2 q1 q2
← q2 – – q2
2. M2 = ({q0, q1, q2}, {a, b, c}, δ, q0, {q2}), kde δ je dána:
q0 q1
q2
a, b
b
c a
b
δ a b c
→ q0 q1 q1 q2
q1 q2 q1 –
← q2 – q2 –
1
3. M3 = ({q0, q1, q2}, {a, b}, δ, q0, {q0}), kde δ je dána:
q0 q1
q2
a
b a
a, b
b
δ a b
↔ q0 q1 q2
q1 q2 –
q2 q2 q2
Příklad 3
Mějme regulární přechodové grafy G1, G2, G3 o dvou stavech q0, q1, kde q0 je počáteční stav a q1
koncový stav. Hrany všech tří grafů jsou ohodnoceny ze stavu q0 do stavu q1 těmito regulárními
výrazy:
1. E1 = a.c + (b∗
.(c.d).a∗
)
2. E2 = b.c + (a.(c + d)∗
.b.(a + c))
3. E3 = (0.1∗
+ 1.0.1)∗
0∗
1∗
Úkol: Ke každému regulárnímu výrazu sestrojte ekvivalentní nedeterministický konečný automat
s ε-kroky.
2