Obsah

Úkol 1

Bc. Jan Kaláb <[email protected]>

Příklad 1

Uvažte jazyk L1 = {aibj | 0 < iji + j = 2k, k ∈ ℕ}.

Sestavte gramatiku G1 takovou, že L(G1) = L1.

G1 = ({a, b}, {S, X, Y}, S, P)

P = {

}

Jakého typu (dle Chomského hierarchie jazyků) je G1 a jakého typu je L1? Mohou se tyto typy obecně lišit? Svoje tvrzení zdůvodněte.

G1 je typu 2, tedy bezkontextová, protože obsahuje pravidla ve tvaru Aγ, AN, γ ∈ (NΣ). Jazyk L1 navíc potřebuje „počítat“, takže jistě nepůjde popsat omezenějším typem, než 2, protože ono „počítání“ potřebuje zásobník.

L1 je tedy podle definice 2.16 z opory (nebo 1.10 ze slajdů) také typu 2, tedy bezkontextový.

Obecně mohou. Tento jazyk by jistě bylo možno popsat i gramatikou typu 0, ale stále by to byl stejný (typu 2) jazyk. Je ale zvykem, že se typ jazyka i gramatiky shoduje.

Příklad 2

Uvažte regulární výraz r2 = (ab + ε)* a* c.

Převeďte r2 algoritmicky na redukovaný deterministický konečný automat M2 (tj. RV → RKA → DKA → redukovaný DKA), přijímající jazyk popsaný výrazem r2.

Podle algoritmů 3.4, 3.5 a 3.7 z opory.

Strom RV:
Strom RV

RKA:
RKA

Nejsou zde žádné nedosažitelné stavy.

Úplně definovaný DKA:

ε-uz a b c
→I {1} {1, 2, 3, 6, 7, 8, 9, 10, 12} {4, 11} II T {13} III
II {4, 11} {4, 10, 11, 12} {11} IV {5} V {13} III
III→ {13} {13} T T T
IV {11} {10, 11, 12} {11} IV T {13} III
V {5} {2, 3, 5, 6, 7, 8, 9, 10, 12} {4, 11} II T {13} III
T {T} T

Úplně definovaný DKA

Minimalizace:

0 a b c
A→ III→ T B T B T B
→B →I II B T B III A
V II T III
II IV V III
IV IV T III
T T B T B T B
1 a b c
A→ III→ T T T T T T
→B →I II B T C III A
V II T III
IV IV T III
II IV B V B III A
T T T T T T T T
2 a b c
A→ III→ T T T T T T
→B →I II C T T III A
V II T III
IV IV B T T III A
C II IV B V B III A
T T T T T T T T
3 a b c
A→ III→ T T T T T T
→B →I II C T T III A
V II T III
C II IV D V B III A
D IV IV D T T III A
T T T T T T T T

3 = ≡4 = ≡

Redukovaný DKA1)

Převeďte automat M2 na redukovaný deterministický konečný automat M2 přijímající komplement jazyka (nad abecedou {a, b, c}) popsaného výrazem r2.

Redukovaný DKA přijímající komplement jazyka

Příklad 3

Uvažte NKA M3 nad abecedou Σ = {a, b} z obrázku 1:
Obrázek 1: NKA M3
Řešením rovnic nad regulárními výrazy sestavte k tomuto automatu ekvivalentní regulární výraz.

Stavy jsem si označil X, Y, Z ve směru z leva.

Příklad 4

Nechť M1 = {Q, Σ, δ, q0, F} je nedeterministický konečný automat. Mějme funkci Φ: Σ* → (Σ ∪ {•})*, kde • ∉ Σ, definovanou následujícím předpisem

Například: Φ(aa) = aa•, Φ(abcde) = abcde

Navrhněte a formálně popište algoritmus, který má na vstupu automat M1, a jehož výstupem bude (nedet.) konečný automat M2 takový, že L(M2) = {Φ(w) | wL(M1)}.

Vstup: NKA M1 = (Q, Σ, δ, q0, F)
Výstup: NKA M2 = (Q′, Σ′, δ′, q0′, F′)

Příklad 5

Mějme jazyk L = {w | w ∈ {a, b, c}* ∧ #a(w) = #b(w) ∧ #c(w) = 1}, kde #x(w) je počet symbolů x ve slově w. Je jazyk L regulární? Dokažte nebo vyvraťte.

Předpokládejme, že L je regulární. Pak musí platit: ∃p > 0: ∀wL: |w| ≥ p ⇒ ∃x, y, z ∈ Σ*: w = xyz ∧ 0 < |y| ≤ p ∧ ∀i ≥ 0: xyizL.

Uvažujme slova w ve tvaru apcbp. |w| ≥ p. Pak lze při i ≠ 1 zvolit y následujícími způsoby:

Nelze tedy najít takové rozdělení xyz, které by uspokojilo podmínky pumping lemmatu, jazyk tedy není regulární.

Příklad 6

Uvažujme algebru regulárních množin (ARM) nad abecedou Σ.

Ukažte, že pro ARM platí následující vztah: A*A* = A*, kde A je libovolná regulární množina. Nepoužívejte fakt, že ARM je Kleeneho algebrou.

  1. Ukážeme, že A*A* ⊆ A*
    • Ukážeme, že ∀wA*A*: wA*
    • Uvažme livobolné wA*A*
    • Dle definice ., w = w1 . w2 pro w1A* a w2A*
    • Dle definice *, w1 = w1¹ . w2¹ . … . wn¹ pro n ≥ 0, wi¹ ∈ A pro 1 ≤ in a podobně w2 = w1² . w2² . … . wm² pro m ≥ 0, wi² ∈ A pro 1 ≤ im
    • Z definic . a *, w1¹ . … . wn¹ . w1² . … . wm² ∈ A*
  2. Ukážeme, že A* ⊆ A*A*
    • Ukážeme, že ∀wA*: wA*A*
    • Uvažme livobolné wA*
    • Víme, že εA*
    • w . εA*A* dle definice . jazyků ∧ w . ε = w z definice . řetězců a tedy wA*A*

Určete, zdali je ⊆ totální uspořádání v ARM. Tedy že pro libovolné dvě regulární množiny A a B platí vždy alespoň jedna z nerovností AB nebo BA. Své tvrzení dokažte.

Uvažme regulární množiny A = {a} a B = {b}. Neplatí pro ně ani jedna z nerovností AB nebo BA, ⊆ tedy není totální uspořádání v ARM.

1)
Sink stav je pro přehlednost vynechán