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ů.

DefiniceEditovat

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é gramatikyEditovat

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é gramatikyEditovat

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ánkyEditovat