IB 102 — úkol 6, příklad 1 — řešení
Odevzdání: 29.10. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Nechť K je libovolný konečný jazyk nad abecedou E = {a}, L je libovolný regulární jazyk nad abecedou E = {a} a N je libovolný neregulární jazyk nad abecedou E = {a}. Rozhodněte a zdůvodněte, zda následující tvrzení platí:
(a) K je neregulární =>- co-(K) je regulární.
(b) (co-(Ä" Pi N) \ L) Pi N není regulární.
Řešení:
(a) Tvrzení platí.
Důkaz: Dle zadání je jazyk K konečný. Každý konečný jazyk je zároveň regulární. Předpoklad implikace ("K je neregulární") je tedy nepravdivý, celá implikace je tím pádem platí.
(b) Tvrzení neplatí.
Důkaz: Pro důkaz najdeme protipříklad, tj. jazyky K, L, N, pro něž tvrzení neplatí. Uvažme následující jazyky:
K = 0 L = {a}*
N = {ď I i = 2n, n E N}.
Pak K HN = 0, tedy co-(K fl N)) = {a}*, a tudíž co-(K H N)) \ L = 0 a konečně (co-(K H N) \ L) H N = 0. Prázdný jazyk 0 je ovšem regulární, nalezli jsme tedy protipříklad a tvrzení v obecnosti neplatí.