2015-04-20
574
Определение. Грамматика называется право -линейной, если правая часть каждого правила содержит не более одного нетерминала, причем он является самым правым символом.
Правила право линейной грамматики имеют вид:
A ® w B, A ® w, w Î V*, B Î W.
Определение. Грамматика называется автоматной, если ее правила имеют вид:
A ® x B, A ® x, A ® e, x Î V, B ÎW.
Синтез конечных автоматов, распознающих язык, порождаемый грамматикой, предусматривает, что такая грамматика должна быть автоматной.
Пример. Преобразовать грамматику, заданную правилами вида:
1. S ® a A 4. A ® a b b S
2. S ® b c 5. A ® c A
3. S ® A 6. A ® e
к автоматной.
Решение. Последовательно будем вводить новые нетерминалы в
тех правилах, где необходимо обозначить цепочку нетерминалов и терминалов или одних терминалов одним символом. Новые правила примут вид:
1. S ® a A 6. S ® e
2. S ® b К1 7. A ® a K2
3. K1 ® c 8. K2 ® b K3
4. S ® a K2 9. K3 ® b S
5. S ® c A 10. A ® c A
12. A ® e
Теория автоматов
