Регуларна граматика

У рачунарству, десно-линеарна граматика (или граматика типа 3, десна регуларна граматика) је формална граматика (Н, Σ, П, С) којој су сва правила из скупа П облика:

1. А → а - где је А незавршни симбол из Н и а је завршни симбол из Σ
2. А → аБ - где су А и Б из Н и а је из Σ
3. А → ε - где је А из Н и ε је празна ниска, тј. ниска дужине 0.

У лево-линеарној граматици (која се још зове лева регуларна граматика), су сва правила облика:

1. А → а - где је А незавршни симбол из Н и а је завршни симбол из Σ
2. А → Ба - где су А и Б из Н и а је из Σ
3. А → ε - где је А из Н и ε је празна ниска.

Пример десно-линеарне граматике Г са Н = {С, А}, Σ = {а, б, ц}, П се састоји од следећих правила:

С → аС

С → бА

А → ε

А → цА

и С је почетни симбол. Ова граматика описује исти језик као и регуларни израз а*бц*.

Регуларна граматика је лево-линеарна или десно-линеарна регуларна граматика.

Неки уџбеници не допуштају употребу празних правила (ε-правила) и претпостављају да празна ниска није присутна у језицима.

Проширена регуларна граматика

Проширена десно-линеарна граматика је она у којој су сва правила облика:

1. А → а - где је А незавршни симбол из Н и а је завршни симбол из Σ
2. А → wБ - где су А и Б из Н и w је из Σ^*
3. А → ε - где је А из Н и ε је празна ниска.

Неки аутори овај тип граматике зову десно-линеарна граматика, а тип изнад строго десно-линеарна граматика. Проширена лево-линеарна граматика је она у којој су сва правила облика:

1. А → а - где је А незавршни симбол из Н и а је завршни симбол из Σ
2. А → Бw - где су А и Б из Н и w је из Σ^*
3. А → ε - где је А из Н и ε је празна ниска.

Неки аутори овај тип граматике зову лево-линеарна граматика, а тип изнад строго лево-линеарна граматика.

Изражајна моћ

(Строго) лево-линеарна граматика генерише тачно онај језик који прихвата недерминистички коначни аутомат, јер постоји директна 1-1 веза између правила ове граматике и аутомата. Дакле, сви регуларни језици су генерисани лево-линеарним граматикама. Десно-линеарне граматике описују језике који су настали обртањем свих ових језика, и то су, такође, регуларни језици.

Свака строго десно-линеарна граматика је поширена десно-линеарна, док свака проширена десно-линеарна граматика може постати стога тако што јој се додају незавршни симболи и тада резултат генерише исти језик. Дакле, и проширене десно-линеарна граматике генеришу регуларне језике. Аналогно, исто важи за проширене лево-линеарне граматике.

Уколико ε-правила нису дозвољена, могуће је генерисати само регуларне језике који не садрже празну ниску.

Мешање левих и десних регуларних правила

Свака линеарна граматика се може лако записати у облику у коме се користи само комбинација десних и левих регуларних правила. Регуларне граматике могу садржати или лево-линеарна или десно-линеарна правила, али не и оба истовремено. Оне генеришу само мањи подскуп језика зван регуларни језици.

На пример, грамтика Г са Н = {С, А}, Σ = {а, б}, где је С почетни симбол, и правилима П облика:

С → аА

А → Сб

С → ε

генерише $\{a^{i}b^{i}:i\geq 0\}$, и овај језик није регуларан.

Види још

• Формалана граматика
• Хијерархија Чомског