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. В этом случае автомат начинает работать с непустым стеком.

	S	A	Ñ
a	1 AS ®	4 ­ > <	¾
b	2 ­®	4 ­ > <	¾
c	¾	3 AS ®	¾
┤	¾	¾	+