Redukovaná gramatika

Redukovaná gramatika je taková gramatika, která je bez nedosažitelných neterminálů a kde každý neterminál má konečný rozvoj, tj. každý neterminál A gramatiky lze přepsat na řetězec terminálních symbolů.

Definice

Gramatika G je redukovaná, pokud každý neterminální symbol A vyhovuje podmínkám

  • ,
  • existuje-li , že .

kde jsou libovolné řetězce.


Gramatiku G nazveme nejednoznačnou, pokud existuje řetězec , pro který existují dva různé způsoby odvození. Jinak nazveme gramatiku jednoznačnou.


Příklad redukované gramatiky

Mějme gramatiku definovanou množinami


,


potom řetězec je větou jazyka L(G), protože platí


a tedy .


Z toho je vidět, že jazyk generovaný danou gramatikou je .


Zároveň vidíme, že gramatika je redukovaná, protože všechna přepisovací pravidla jsou typu . Gramatika je jednoznačná, protože existuje pouze jeden způsob jak vygenerovat x.

Příklad neredukované gramatiky

Nechť je gramatika definovaná množinami


,


G je nejednoznačná, protože větu 0101 lze odvodit dvěma různými způsoby


G je neredukovaná, protože obsahuje pravidlo . Pokud toto pravidlo aplikujeme, nelze již vygenerovat terminální řetězec. Když toto pravidlo z gramatiky odebereme, dostaneme redukovanou gramatiku.

Související články