Uživatelské nástroje

Nástroje pro tento web


pitel:tin:ukoly:2010:1

Úkol 1

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

Příklad 1

Uvažte jazyk L1 = {aibjci+j | i ≥ 0, j ≥ 0}.

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

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

  • SA
  • AaAc | B
  • BbBc | ε

}

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 i L1 jsou bezkontextové. G1 má pravidla ve tvaru „neterminál → posloupnost terminálů a neterminálů“. L1 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.

Příklad 2

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

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

Strom pro RV:

RKA ze stromu RV:
RKA

Úplně definovaný DKA:

a b c
→ε-uz({1}) = {1, 2, 3, 6, 11} = Aε-uz({4, 7, 12}) = {4, 7, 12, 13, 15} = Bε-uz({}) = ∅ = Tε-uz({}) = ∅ = T
←Bε-uz({}) = ∅ = Tε-uz({5, 8, 14}) = {2, 3, 5, 6, 8, 10, 11, 13, 14, 15} = Cε-uz({}) = ∅ = T
←Cε-uz({4, 7, 12}) = {4, 7, 12, 13, 15} = Bε-uz({14}) = {13, 14, 15} = Dε-uz({9}) = {2, 3, 6, 9, 10, 11} = E
←Dε-uz({}) = ∅ = Tε-uz({14}) = {13, 14, 15} = Dε-uz({}) = ∅ = T
Eε-uz({4, 7, 12}) = {4, 7, 12, 13, 15} = Bε-uz({}) = ∅ = Tε-uz({}) = ∅ = T
TTTT

DKA

Minimalizace:

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

2 = ≡3 = ≡

Minimální DKA

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

M2′

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.

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)*

Příklad 4

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 M1, a jehož výstupem bude automat M2 takový, že L(M2) = {even(w) | wL(M1)}.

Vstup: NKA M1 = (Q1, Σ1, δ1, q01, F1)
Výstup: M2 = (Q2, Σ2, δ2, q02, F2)

  1. Q2 ⊆ Q1
  2. Σ2 ⊆ Σ1
    1. ∀q11, q21, q31 ∈ Q1
      ∀q12, q22 ∈ Q2
      ∀a, b ∈ Σ1 ∧ ∀b ∈ Σ2:
      q22 ∈ δ2(q12, b) ⇔ (δ1(q11, a) = q21 ∧ δ1(q21, b) = q31)
    2. ∀q11, q21 ∈ Q1 ∧ q21 ∈ F1
      ∀q12, q22 ∈ Q2
      ∀a ∈ Σ1:
      q22 ∈ δ2(q12, ε) ⇔ (δ1(q11, a) = q21 ∧ δ1(q21, ε) = q21)
  3. q01 = q02
  4. F2 = F1

Příklad 5

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

Lemma

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

Řešení

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 = anb4a2n náležící L, platí |w| ≥ n.

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

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

  • x = am
  • y = an−m
  • z = b4a2n

Pro i = 2 platí: xyiz = a2n−mb4a2nL 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í.

Příklad 6

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

Ukažte, že pro ARM 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 ARM. Své tvrzení dokažte.

Předpokládejme, že {ε} je minimálním prvkem ARM. 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 ARM.

/var/www/wiki/data/pages/pitel/tin/ukoly/2010/1.txt · Poslední úprava: 30. 12. 2022, 13.43:01 autor: 127.0.0.1