Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:msz:gramatiky

Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky

Základní pojmy

  • Abeceda Σ
    • Neprázdná množina, jejíž prvky nazýváme symboly.
  • Řetezec / slovo / věta w
    • Konečná posloupnost symbolů abecedy.
    • Alternativní definice:
      1. Prázdný řetezec je řetezec.
      2. Je-li w řetězec a a symbol abecedy pak wa je řetezec.
      3. Řetězce jsou vše, co lze získat jen a pouze aplikací předchozích pravidel
  • Prázdný řetezec ε
    • Řetezec neobsahující žádný symbol
  • Konkatenace xy (někdy x.y)
    • Připojení řetezce za jiný řetezec
    • Konkatenace je asociativní
    • Prázdný řetezec je neutrální prvek vzhledem ke konkatenaci
  • Iterace Σ*
    • Množina všech řetězců nad abecedou Σ.
    • Volný monoid nad abecedou Σ generovaný operací konkatenace.
  • Pozitivní iterace Σ
    • Iterace bez prázdného řetezce
  • Formální jazyk L
    • Jakákoli podmnožina LΣ*.
  • Konkatenace jazyků
    • Rozumíme binární operaci L₁ . L₂ = {xy | xL₁ ∧ yL₂}
  • Iterace jazyka
    • L⁰ = {ε}
    • Lⁿ = L . Lⁿ⁻¹, n ≥ 1
    • L* = ∪ Lⁿ, n ≥ 0
    • L⁺ = ∪ Lⁿ, n ≥ 1

Gramatika

Gramatika G = (N, Σ, P, S)

  • N – konečná množina nonterminálních symbolů (nonterminálů)
  • Σ – konečná množina terminálních symbolů (terminálů)
  • P – je konečná množina přepisovacích pravidel
  • Spočáteční nonterminál SN
  • Přepisovací pravidlo
    • Podmnožina kartézského součinu (NΣ)*N(NΣ)* × (NΣ)*
    • (a, b) ∈ P zapisujeme ve tvaru ab, kde a je levá strana a b je pravá strana pravidla.
  • Přímá derivace ⇒
    • Binární relace mezi řetezci u a v která platí pokud můžeme řetezce zapsat jako u = gad, v = gbd a (a, b) ∈ P, tj. pokud lze řetězec v vytvořit z retězce u aplikací jednoho přepisovacího pravidla.
  • Derivace ⇒⁺
    • Tranzitivní uzávěr relace přímé derivace, tj. pokud lze vytvořit řetězec v z řetězce u postupnou aplikací několika přepisovacích pravidel.
  • Derivace ⇒*
    • Tranzitivní a reflexivní uzávěr relace přímé derivace, tj. pokud lze vytvořit řetězec v z řeťazca u postupnou aplikací několika přepisovacích pravidel nebo pokud jsou řetězce stejné.
  • Větná forma
    • Řetězec terminálů a nonterminálů, které jsou derivací počátečního nontermínálu
  • Věta
    • Větná forma obsahující pouze terminály
  • Jazyk generovaný gramatikou
    • Množina všech vět, které patří do gramatiky L(G) = {w | S* wwΣ*}

Chomského hierarchie klasifikace gramatik

Klasifikace je definována podle tvaru přepisovacích pravidel příslušných gramatik

Platí: L₃ ⊂ L₂ ⊂ L₁ ⊂ L

Typ 0 – obecné (neomezené) gramatiky

Unrestricted grammar

  • Rekurzivně vyčíslitelné jazyky
  • Turingovy stroje
  • Tvar pravidel: αβ
    • α ∈ (NΣ)*N(NΣ)*
    • β ∈ (NΣ)*

Typ 1 – kontextové gramatiky

Context-sensitive grammar

  • Kontextové jazyky
  • Lineárně omezené Turingovy stroje
  • αAβαγβ, nebo Sε pokud εL a S se nevyskytuje na pravé straně žádného pravidla
    • AN
    • α, β ∈ (NΣ)*
    • γ ∈ (NΣ)⁺
    • Nesmí dojít ke zkrácení větné formy

Typ 2 – bezkontextové gramatiky

Context-free grammar

  • Bezkontextové jazyky
  • Zásobníkové automaty
  • Aγ
    • AN
    • γ ∈ (NΣ)*

Typ 3 – pravé/levé linární gramatiky

Regular grammar

  • Regulární jazyky
  • Konečné automaty
  • Pravá lineární: AxB nebo Ax
  • Levá lineární: ABx nebo Ax
    • A, BN
    • x ∈ Σ*

Speciální podtypy gramatik

Pravé/levé regulární gramatiky

Stejné jako 3, ale xΣ (bez *).

Lineární gramatiky

Podmnožina gramatik typu 2

  • AxBy nebo Ax
    • A, BN
    • x, yΣ*

Deterministické bezkontextové gramatiky

Podmnožina typu 2, jazyky příjamné deterministickým zásobníkovým automatem.

Rekurzivní gramatiky

Podmnožina typu 0. Přijímají je úplné TS (TS, které pro každý vstup rozhodnou – nikdy necyklí).

Všechny kontextové jazyk jsou rekurzivní, ale ne všechny rekurzivní jazyky jsou kontextové.

/var/www/wiki/data/pages/pitel/msz/gramatiky.txt · Poslední úprava: 03. 07. 2012, 13.53:31 (upraveno mimo DokuWiki)