IB102 - úkol 7
Odevzdání: 8.11.2010
Vypracoval(a): UCO: Skupina:
1. [2 body] Rozhodnete, zda pro všechny jazyky L, K platí nasledující implikace. Svá rozhodnutí zduvodnete.
(á) L* je regulární =>- L je regularní
(b) (L \ K)R je regularní, K je regularní a K C L =>- L je regularní
IB102 - úkol 7
Odevzdání: 8.11.2010
Vypracoval(a): UCO: Skupina:
2. [2 body] Definujme T jako trídu všech jazyku, jejichž prefixová ekvivalence nm index nejvýše 4. Platí tedy, že jazyk L patrí do trídy T práve tehdy, když index ~L < 4. Odpovezte na následující otazky a šve odpovedi zduvodnete.
(á) Je trída T uzavrena na sjednocení?
(b) Je trída T uzavrena na průnik?
(c) BONUS [+1 bod] Je trída T uzavrena na iteraci?
(d) BONUS [+1 bod] Je trída T uzavrena na pozitivní iteraci?