Strona wykładowcy

Zbiór zadań

Zajęcia 2 ("zastępcze", odbyły się we wtorek 1.03.2011 o godz. 14:15):

1. Zadania 1.3 a) i c)
   (zbiór długości ścieżek łączących dwa wierzchołki w grafie skierowanym jest semi-liniowy)

2. L(M∩N)≠LM∩LN
   

   Podaliśmy przykład: L={ε,a}, M={ε}, N={a}
   Wtedy: L(M∩N)=∅, a LM∩LN={a}

   Uwaga: L(M∩N)⊆LM∩LN

3. Automat deterministyczny rozpoznający język (0+1)*01 (na wykładzie pokazałem niedeterministyczny)

4. Wyrażenie definiujące język "w słowie istnieje blok 010"

   (0+1)*010(0+1)*

   Pokazać automat (niedeterministyczny a potem deterministyczny) dla tego języka.

5. Zadanie 2.1.1. (L*M*)*=(L∪M)*

   (⊇)
   Z monotoniczności ()*: L∪M ⊆ L*M*  →  (L∪M)* ⊆ (L*M*)*

   (⊆)
   L*M* ⊆ (L∪M)*(L∪M)* ⊆ (L∪M)*
   Znowu z monotoniczności * i z faktu, że A**=A* wynika:
   (L*M*)* ⊆ (L∪M)** = (L∪M)*

6. Zadanie 2.3.7 b): Klasa języków regularnych jest zamknięta na operację pierwiastka kwadratowego języków, tzn.
   L∈Reg → √L={w:ww∈L}∈Reg.