Лекция: S и q - грамматики

s-грамматикой будем называть такую контекстно-свободную грамматику, правые части правил, которой начинаются с терминальных символов, причем для одного и того же левого символа правые части начинаются с разных символов.

Не s-грамматика :

S ® aT — начинается с нетерминального. T ® bT.

S ® TbS

T ® bT

Aналогичная s-грамматика (распознает тоже)

:

S ® abR

S ® bRbS

R ® a

R ® bR

q-грамматикаотличается от s-грамматики наличием аннулирующего правила (в правой части есть пустой символ) a Þ e.

1. S ® aAS

2. S ® b

3. A ® cAS

4. A ® e

Из-за аннулирующих правил для q-грамматики вводится понятие следующего символа. N(A) — множество терминальных следующих (Next) за А символов.

В данном случае за А могут следовать a или b — {a,b}.

S Þ aAS Þ aAaAS Þ aAaAb

E(1) = {a} — множество выбора для первого правила.

E(2) = {b}

E(3) = {c}

E(4) = N(A) = {a,b}

Данная грамматика может быть распознана МП-автоматом, в который добавлена операция замены a. В этом случае автомат начинает работать с непустым стеком.