index předchozí 1 2 3 4 5 6 7 8 9 10 11 12 následující

Cvičení čtvrté

Reg. gramatiky a výrazy <=> KA, epsilon kroky, Kleeneho věta

1) Zkonstruujte ekvivalentní konečný automat k následující gramatice:

   S => aA | bC | a | epsilon
   A => bB | aA | b | c
   B => aB | bC | aC | cA | c
   C => a | b | aA | bB

   S => aX | bY | c
   X => bX | bS
   Y => bS | cZ | epsilon
   Z => aS | b | c | epsilon

2) Zkonstruujte ekvivalentní gramatiku k automatu:

3) K danému automatu s epsilon kroky zkonstruujte ekvivalentní automat bez epsilon kroků.

stav pod a pod b pod c pod epsilon

=> 1 {1,2} - - 2

2 5 {3,5} - -

3 - 6 - -

4 - 4 - {1,5}

5 5 - 3 6

<= 6 - - {3,6} 2

4) K danému regulárnímu výrazu zkonstruujte ekvivalentní KA

(ab)^* (aa+bb) (a+ab)^*
((a+b(a+c))^*+(b+c))^* (DÚ)
(((a+b)^*+c)^*+d)^* (DÚ)

5) K danému KA zkonstruujte ekvivalentní regulární výraz

6) Pomocí regulárních výrazů popište násl. jazyky:

L={w náleží {a,b}^* | w končí na ab }
L={w náleží {a,b}^* | #_a(w) = 2k, k>=0 }
L={w náleží {a,b}^* | w začíná a končí stejným symbolem }
L={w náleží {a,b}^* | |w| = 2k, k>=0 }

7) Ukažte, jaký je vztah mezi R a nejmenší třídou

M₁, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, zřetězení a průniku.
M₂, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, průniku a komplementu.
M₃, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, průniku a mocnině.

8) Najděte konečné jazyky L₁, L₂, ...
tak, že jazyk sjednocení_i=1,2,... L_i není regulární jazyk.

9) Najděte regulární jazyky L₁, L₂, ...
tak, že jazyk průnik_i=1,2,... L_i není regulární jazyk.

stav	pod a	pod b	pod c	pod epsilon
=> 1	{1,2}	-	-	2
2	5	{3,5}	-	-
3	-	6	-	-
4	-	4	-	{1,5}
5	5	-	3	6
<= 6	-	-	{3,6}	2