Kapitola 1: Lekce 1 - Bezkontextové gramatiky
Parcely a pravidla
Gramatika jazyka CGA je variantou nejednoznačné bezkontextové gramatiky. To znamená, že pro jeden vstup mohou nastat odlišné výstupy. Bezkontextová gramatika je formální gramatikou, která je specifická tvarem A→β u všech přepisovacích pravidel. Znak A představuje neterminál a β je řetězec terminálů, případně neterminálů. Neterminál může být tedy rozložen na řetězec dalších neterminálů nebo terminálů. Terminály jsou už nerozložitelné. Jazyk CGA je tedy generovaným bezkontextovou gramatikou. V CGA gramatice může být neterminálem pravidlo definované jiným pravidlem. Lze ho také nazývat proměnnou.
Bezkontextové gramatiky mohou být bez ε-pravidel, neboli nevypouštějící. Ty neobsahují pravidlo typu A → ε, pokud však L(G) – jazyk, množina všech pravidel - ε obsahuje (ε značí prázdný řetězec), tak právě jedno a pouze ve tvaru S → ε za předpokladu, že S je počáteční neterminál a nevyskytuje se na žádné pravé straně pravidel. Dalším typem jsou bezkontextové gramatiky bez jednoduchých pravidel, což je pravidlo ve tvaru A → B kde A, B N.
Příkladem může být jednoduchá bezkontextová gramatika daná přepisovacím pravidlem
S → aSb | ab (stejně jako A → β)
kde znak | odděluje více možností řetězců (w) z terminálů a neterminálů, které znamenají to samé jako zápis
S → aSb
S → ab
Znaky a, b jsou terminály, S je startovní symbol - neterminál. Tato gramatika generuje jazyk an bn, kde n>=1.
Pokud změníme pravidlo na S → aSb | ε získáme gramatiku, která generuje jazyk an bn, kde n>=0. Toto přepisovací
pravidlo obsahuje i přepis na prázdný řetězec, který původní gramatika neobsahuje.
Další lekce se zaměřuje na obecný popis CGA gramatiky a její principy.