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

Uvažte jazyk L₁ = {aⁱb^jc^i+j | i ≥ 0, j ≥ 0}.

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

G₁ = ({a, b, c}, {S, A, B}, S, P)
P = {

• S → A
• A → aAc | B
• B → bBc | ε

}

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₁ i L₁ jsou bezkontextové. G₁ má pravidla ve tvaru „neterminál → posloupnost terminálů a neterminálů“. L₁ lze reprezentovat zásobníkovým automatem (ale ne konečným automatem).

Obecně se lišit mohou. Chomského hierarchie jazyků a gramatik má strukturu „vrstev“ – bezkontextové gramatiky lze popsat i jako kontextové či obecné, ale ne jako regulární. To samé platí i pro jazyky. Důsledkem je, že bezkontextový jazyk jistě půjde popsat kontextovou gramatikou.

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

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

Strom pro RV:

RKA ze stromu RV:

Úplně definovaný DKA:

Minimalizace:

≡² = ≡³ = ≡

Převeďte automat M₂ na minimální 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.

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

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

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

• X = aa*bZ + aa*bX + ε
• X = aa*ba*bX + aa*bX + ε
• X = (aa*ba*b + aa*b)X + ε
• X = (aa*ba*b + aa*b)*ε

(a⁺ba*b + a⁺b)*

Mějme operaci even : Σ* → Σ*, která z daného slova w ∈ Σ* vybere pouze znaky na sudých pozicích. Například: even(abcda) = bd, even(aabbcc) = abc.

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

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

1. Q₂ ⊆ Q₁
2. Σ₂ ⊆ Σ₁
3. 1. ∀q₁¹, q₂¹, q₃¹ ∈ Q₁
      ∀q₁², q₂² ∈ Q₂
      ∀a, b ∈ Σ₁ ∧ ∀b ∈ Σ₂:
      q₂² ∈ δ₂(q₁², b) ⇔ (δ₁(q₁¹, a) = q₂¹ ∧ δ₁(q₂¹, b) = q₃¹)
   2. ∀q₁¹, q₂¹ ∈ Q₁ ∧ q₂¹ ∈ F₁
      ∀q₁², q₂² ∈ Q₂
      ∀a ∈ Σ₁:
      q₂² ∈ δ₂(q₁², ε) ⇔ (δ₁(q₁¹, a) = q₂¹ ∧ δ₁(q₂¹, ε) = q₂¹)
4. q₀¹ = q₀²
5. F₂ = F₁

Mějme jazyk L = {aⁱb^ja²ⁱ | 0 ≤ i, 0 ≤ j ≤ 5}. Je jazyk L regulární? Dokažte nebo vyvraťte.

Nechť L je regulární jazyk. Pak existuje n ∈ N takové, že libovolné slovo w ∈ L délky alespoň n lze psát ve tvaru w = xyz, kde |xy| ≤ n, y ≠ ε a xyⁱz ∈ L pro každé i ∈ N₀.

Budeme provádět důkaz sporem. Předpokládejme, že L je regulární.

Z uvedené pumping lemmy a z předpokladu plyne, že musí existovat konstanta n.

Uvažujme libovolnou hodnotu n.

Pro w = aⁿb⁴a²ⁿ náležící L, platí |w| ≥ n.

Uvažujme libovolný výběr x, y, z takový, že w = xyz ∧ |xy| ≤ n ∧ y ≠ ε.

Uvažujme například rozdělení:

• x = a^m
• y = a^n−m
• z = b⁴a²ⁿ

Pro i = 2 platí: xyⁱz = a^2n−mb⁴a²ⁿ ∉ L protože, 2n − m ≠ 2n.

Obdobně lze dokázat pro libovolná jiná rozdělení w = xyz se stejnou pumpovací konstantou i = 2.

Dochází ke sporu, protože w po pumpování nenáleží do jazyka L a tedy L 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í teorém Kleeneho algebry: a(ba)* = (ab)*a.

Výše uvedený konečný automat je minimální konečný automat který přijímá i zamítá stejné řetězce jako regulární výraz na levé i pravé straně teorému. Proto je teorém platný.

Vzhledem k uspořádání definovaném v Kleeneho algebře určete, zdali je {ε} minimálním prvkem A_RM. Své tvrzení dokažte.

Předpokládejme, že {ε} je minimálním prvkem A_RM. Pak by vzhledem k uspořádání definovaném v Kleeneho algebře muselo platit: {ε} ∪ {a} = {a}. Ovšem {ε} ∪ {a} = {ε, a}. Dochází tedy ke sporu, tedy {ε} není minimálním prvkem A_RM.