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

Uvažte jazyk L₁ = {aⁱb^j | 0 < i ≤ j ∧ i + j = 2k, k ∈ ℕ}.

Sestavte gramatiku G₁ takovou, že L(G₁) = L₁.

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

P = {

• S → aXbY
• X → aXb | ε
• Y → bbY | ε

}

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

G₁ je typu 2, tedy bezkontextová, protože obsahuje pravidla ve tvaru A → γ, A ∈ N, γ ∈ (N ∪ Σ). Jazyk L₁ 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.

L₁ 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.

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

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

Podle algoritmů 3.4, 3.5 a 3.7 z opory.

Strom RV:

RKA:

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

Úplně definovaný DKA:

Minimalizace:

≡³ = ≡⁴ = ≡

¹⁾

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

Uvažte NKA M₃ nad abecedou Σ = {a, b} z obrázku 1:

Ř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.

• X = aY + aZ
• Y = aY + bZ + ε
• Z = bX

• X = aY + abX = abX + aY
• Y = aY + bbX + ε

• X = (ab)*aY
• Y = a*(bbX + ε)

• X = (ab)*a(a*(bbX + ε))
• X = (ab)*aa*(bbX + ε)
• X = (ab)*a⁺(bbX + ε)
• X = (ab)*a⁺bbX + (ab)*a⁺
• X = ((ab)*a⁺bb)*(ab)*a⁺
• X = (ab + a⁺bb)*a⁺

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

• Φ(ε) = ε
• Φ(a₁) = a₁, kde a₁ ∈ Σ
• Φ(a₁a₂u) = a₁a₂ • Φ(u), kde a₁, a₂ ∈ Σ, u ∈ Σ*

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

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

Vstup: NKA M₁ = (Q, Σ, δ, q₀, F)
Výstup: NKA M₂ = (Q′, Σ′, δ′, q₀′, F′)

• Q′ = {(q₀, n) | q₀ ∈ Q; n ∈ {0, 1, 2}}
• Σ′ = Σ ∪ {•}
• q₀′ = (q₀, 0)
• F′ = {(q, n) | q ∈ F; n ∈ {0, 1}}
• δ′ = ∀a ∈ Σ; ∀q₁, q₂ ∈ Q:
  • δ(q₁, a) = q₂ →
    • δ′((q₁, 0), a) = {(q₂, 1)} ∪ δ′((q₁, 0)
    • δ′((q₁, 1), a) = {(q₂, 2)} ∪ δ′((q₁, 1)
    • δ′((q₁, 2), •) = {(q₁, 0)} ∪ δ′((q₁, 2), •)

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: ∀w ∈ L: |w| ≥ p ⇒ ∃x, y, z ∈ Σ*: w = xyz ∧ 0 < |y| ≤ p ∧ ∀i ≥ 0: xyⁱz ∈ L.

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

• aa…aacbb…bb: #_a(w) ≠ #_b(w)
• aa…aacbb…bb: #_a(w) ≠ #_b(w)
• c ∈ y: #_c(w) ≠ 1

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

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

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

1. Ukážeme, že A*A* ⊆ A*
   • Ukážeme, že ∀w ∈ A*A*: w ∈ A*
   • Uvažme livobolné w ∈ A*A*
   • Dle definice ., w = w₁ . w₂ pro w₁ ∈ A* a w₂ ∈ A*
   • Dle definice *, w₁ = w₁¹ . w₂¹ . … . w_n¹ pro n ≥ 0, w_i¹ ∈ A pro 1 ≤ i ≤ n a podobně w₂ = w₁² . w₂² . … . w_m² pro m ≥ 0, w_i² ∈ A pro 1 ≤ i ≤ m
   • Z definic . a *, w₁¹ . … . w_n¹ . w₁² . … . w_m² ∈ A*
2. Ukážeme, že A* ⊆ A*A*
   • Ukážeme, že ∀w ∈ A*: w ∈ A*A*
   • Uvažme livobolné w ∈ A*
   • Víme, že ε ∈ A*
   • w . ε ∈ A*A* dle definice . jazyků ∧ w . ε = w z definice . řetězců a tedy w ∈ A*A*

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

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