Důkaz:
Tvrzení
:
Třída regulárních jazyků je uzavřena
vůči
doplňku
.
Uzávěrové vlastnosti
:
Doplněk
•
Nechť
L
je
regul
á
r
ní jazyk
•
Pak
exist
uje
úplný
D
K
A
M
:
L
(
M
) =
L
•
Můžeme sestrojit úplný
D
K
A
M
’
:
L
(
M
’
) =
L
užitím předchozího algoritmu
•
Každý KA definuje regulární jazyk, tedy
L
je
regulární jazyk
17/26