Операторная кс-грамматика

Любой КС язык может быть задан операторной КС-грамматикой , а любую КС-грамматику можно преобразовать в эквивалентную ей операторную. Операторной грамматикой называется КС-грамматика без -правил, в которой правые части всех правил не содержат смежных нетерминалов. Правило назовём операторным, если в его правой части нет смежных нетерминалов.

Для преобразования произвольной грамматики в операторную предварительно получим грамматику, правые части правил которой начинаются терминалом (см. ‘Нормальная форма Грейбах’).

Алгоритм преобразования грамматики, правые части правил которой начинаются терминалом , в операторную.

1. Для каждого правила вида А,

где А – нетерминал;

 - цепочка терминалов и нетерминалов, начинающаяся с терминала;

 - цепочка нетерминалов, содержащая более одного символа;

 - цепочка терминалов и нетерминалов, возможно пустая;

выполнить следующее преобразование:

если в грамматике есть одиночное правило В, то правило А заменить на АВ, иначе ввести правило N , где N – новый нетерминал, и правило А заменить на АN .

Выполнять п.1 , пока в грамматике есть правила вида А .

В результате выполнения п.1 правила, определяющие нетерминалы исходной грамматики, будут операторными.

2. Пока в грамматике есть правила, содержащие в правой части пару смежных нетерминалов XY , выполнять замену второго нетерминала Y .

Пример.

Преобразовать заданную грамматику в операторную.

Исходная грамматика	Результат выполнения п.1	Операторная грамматика
АaBAC	АaN1	АaN1
Аe	Аe	Аe
BdBACb	Bd N1b	Bd N1b
Bb	Bb	Bb
CaBaAB	CaBa N2	CaBa N2
	N1BAC	N1Ba N1aBaN2
	N2AB	N1BeC
		N2A d N1b
		N2Ab

Регулярные языки и конечные распознаватели Правосторонние грамматики

В 1959 г. американский учёный-лингвист Н.Хомский предложил классифицировать формальные языки по типу правил порождающей грамматики. Регулярный язык – это язык, который может быть задан регулярной (правосторонней) грамматикой, которая может иметь правила двух видов: А или АВ, где А и В – нетерминалы, а  - цепочка терминалов, возможно, пустая. Другими словами, в правой части правил может быть не более одного нетерминала и, если он есть, то занимает самую крайнюу правую позицию. Очевидно, что правосторонняя грамматика является подклассом КС-грамматик.

Грамматику, которая может иметь правила двух видов: АtВ и А , где А и В – нетерминалы, а t – терминал, назовём автоматной правосторонней или правосторонней грамматикой специального вида. Любую правостороннюю грамматику можно преобразовать в автоматную правостороннюю.

Алгоритм преобразования правосторонней грамматики в автоматную правостороннюю.

1. Если имеются правила вида А ,  - непустая цепочка термина-лов, то ввести новый нетерминал Е и добавить правило Е . Затем каждое из правил вида А заменить правилом АЕ.

2. Пока в грамматике есть правила вида АВ , где  - цепочка более чем из одного терминала, выполнять выделение нетерминала следующим образом: правило АВ заменить правилами АtC и СВ , где t – первый терминал в цепочке  , С – новый нетерминал,  - цепочка  без первого терминала.

3. Устранить цепные правила.

Пример.

Привести правостороннюю грамматику к автоматному виду.

1. SaA 4. AabS

2. Sb 5. AcA

3. SA 6. A

1. В грамматике есть правило 2 вида А, поэтому введём новый нетерминал Е , добавим правило 7 и изменим правило 2 :

1. SaA 4. AabS

2. SbЕ 5. AcA

3. SA 6. A

7. Е

2. Выполним выделение нетерминала в правиле 4, обозначив цепочку bS ннетерминал В :

1. SaA 4.2. ВbS

2. SbЕ 5. AcA

3. SA 6. A

4.1. AaВ 7. Е

3. Устраним цепное правило 3 :

1. SaA 4.1. AaВ

2. SbЕ 4.2. ВbS

3.1. SaB 5. AcA

3.1. ScA 6. A

3.1. S 7. E

Автоматная правосторонняя грамматика получена.