Gramatika

  • Čtveřice , kde:
    • - konečná množina neterminálů
    • též - konečná množina terminálů
    • - množina přepisovacích pravidel
    • - počáteční symbol (neterminál) gramatiky (též větný/startovací symbol)
  • Je to formalismus pro generování jazyka
Pozor!

je uspořádaná čtveřice , není to množina !

Cílem gramatiky je, aby generovala nějaký jazyk

Lze zapsat také:

  • Výčtem:
  • Matematicky:

Jedné gramatice je vždy přiřazen pouze jeden jazyk, ale jeden jazyk může mít nekonečně mnoho (ekvivalentních) gramatik.

Příklad gramatiky

Gramatika kde

Definice pojmů

Derivace

  • Postup, při kterém se na řetězec uplatní konečný počet (žádné, jedno nebo více) přepsání

  • Posloupnost "přepisů" (větných forem) dle pravidel

    = Derivace řetězce z řetězce , která má délku v gramatice (tj. existuje posloupnost řetězců)
    = Tranzitivní uzávěr (derivuje po nenulovém počtu kroků)
    = Tranzitivní a reflexivní uzávěr (derivuje po libovolném počtu kroků)

  • Přímá derivace - pouze 1 krok derivace

  • Může být levá či pravá či jiná derivace

Větná forma

  • Řetězec nazveme větnou formou v gramatice , jestliže
    (tedy ze startovního symbolu se lze přepsat do takového řetězce , který je tvořen libovolným počtem symbolů terminálů i neterminálů)
  • Větná forma v , která neobsahuje žádné symboly se nazývá věta generovaná gramatikou

Jazyk generovaný gramatikou

  • = jazyk generovaný gramatikou
  • Je to množina všech vět generovaných gramatikou
Poznámka

I prázdný řetězec je věta generovaná gramatikou , pokud

Ekvivalence gramatik

  • Gramatiky a jsou ekvivalentní, když generují stejný jazyk
  • tedy

Klasifikace gramatik

Viz 01 Klasifikace gramatik a jazyků

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25