Pravidelná gramatika

Regulární gramatika  je formální gramatika typu 3 v Chomského hierarchii , regulární gramatiky definují přesně všechny regulární jazyky , a jsou proto ekvivalentní stavovým automatům a regulárním výrazům . Regulární gramatiky jsou podmnožinou bezkontextových gramatik .

Nastavení sady pravidel

Regulární gramatika může být specifikována sadou pravidel jako levá nebo pravá regulární gramatika.

Pravá regulární gramatika nebo pravá lineární gramatika - všechna pravidla mohou být v jedné z následujících forem:

1. A → a
2. A → aB
3. A →ε

levá běžná gramatika nebo levá lineární gramatika - všechna pravidla mohou být v jedné z následujících forem:

1. A → a
2. A → Ba
3. A →ε

kde

• velká písmena ( A , B ) označují neterminály z množiny N
• malá písmena ( a , b ) označují koncovky z množiny Σ
• ε je prázdný řetězec, tedy řetězec délky 0

Třídy pravých a levých regulárních gramatik jsou ekvivalentní – každá samostatně postačí k definování všech regulárních jazyků. Jakákoli běžná gramatika může být převedena zleva doprava a naopak.

Alternativní názvy jsou způsobeny skutečností, že jsou podtřídami obecnější třídy lineárních gramatik .

Příklad

Správná regulární gramatika G daná vztahem N = {S, A}, Σ = {a, b, c}, P se skládá z následujících pravidel:

a S je startovací symbol. Tato gramatika popisuje stejný jazyk jako regulární výraz a*bc*.

Limited

Podstatné je, že pravidla musí být buď pouze levá-běžná, nebo pouze pravá-běžná. Kombinace obojího není povolena. Například bezkontextový řetězcový jazyk tvaru , kde není regulární, ale je dán gramatikou G , kde N = {S, A}, Σ = {a, b}, P se skládá z

a S je startovací symbol. Tato gramatika obsahuje pravidla levá-regulární i pravá-regulární, a proto není regulární.

Viz také

• Regulární výrazy - v teorii formálních jazyků
• Předponová gramatika

Literatura

• Robin Hunter. Základní koncepty kompilátorů = The Essence of Compilers. - M .: "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
• Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teorie a implementace programovacích jazyků  - M.: MZ-Press, 2006, 2. vyd. — ISBN 5-94073-094-9