2015-06-28
262
При построении автоматов – распознавателей грамматик к виду правил предъявляются определенные требования. Одно из них – отсутствие в правилах грамматики левосторонней рекурсии(правил вида A à Ax). Для устранения левосторонней рекурсии применяется приведенная ниже процедура.
Пусть в исходной грамматике есть следующее правило:
A à Ax1| Ax2|...|Axk| y1 | y2 |....| ys (здесь знак "|" означает "или", т.е. в этом правиле объединено несколько правил с одинаковыми левыми частями; xi, yi – цепочки терминалов и нетерминалов, причем цепочки yi не начинаются с А). Для определенности в исходной грамматике не содержится нетерминала В. Тогда возможна эквивалентная замена такого составного правила двумя другими, не содержащих левосторонней рекурсии:
A à y1|y2 |....| ys | y1B | y2B |....| ysB
B à x1 | x2 |....| xk | x1B | x2B |....| xkB
Пример: Пусть в исходной грамматике имеется правило с левосторонней рекурсией A à Abc | b. Устраним левостороннюю рекурсию.
Введем обозначения: х1= bc; y1= b. После замены получим:
A à b | bB;
B à bc | bcB.
6.4 Задачи к главе 6
Грамматика задана множеством правил Р (начальный символ грамматики – левая часть первого правила). В каждом из вариантов определить тип грамматики, выполнить проверку на достижимость и продуктивность, если возможно, упростить грамматику, выполнив эквивалентные преобразования. Выполнить полное описание новой грамматики. В новой грамматике получить 2 цепочки длиной не менее 5 символов, построив для них право– и левосторонний выводы.
1 P = { S à bA 2 P = { S à abC 3 P = { Z à S
S à bC S à acC S à aA
C à cb S à adC S à Z
A à A C à bB A à qA
B à a }. A à cA B à q
B à d }. A à a }.
4 P = {A à dQ 5 P = { A à aB 6 P = { F à fdS
A à S A à Z F à faS
Q à Qde B à Z F à Z
Q à d Z à ab Z à a
S à A }. Z à bA Z à F
D à d }. Z à fbS
S à d }.
7 P = { D à Dbc 8 P = { A à bB 9 P= { S à aQ
D à b A à C S à A
D à aS B à cB Q à B
S à bc B à a B à a
S à A }. D à abD }. B à b
B à c }.
10 P = { S à lA 11 P = { N à A 12 P = { S à C
S à B N à aB S à A
A à Ala B à aN A à aaA
A à l A à bc A à bbA
B à S }. A à bA A à ccA
C à abc }. C à aS }.
7 Распознаватели для грамматик
Построение конечных автоматов для распознания регулярных множеств, особенно таких, для распознания которых необходимо построение МП –автоматов, процесс творческий и плохо поддающийся формализации. Такие задачи значительно упрощаются и формализуются, если удается построить грамматики, порождающие такие множества. Рассмотрим ряд частных случаев построения автоматов-распознавателей для грамматик второго и третьего типов.
7.1 Построение КА–распознавателей для автоматных
грамматик
Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий:
1 Начальный символ грамматики – начальное состояние КА.
2 Терминальные символы грамматики – алфавит КА (без символа конец цепочки – " –| ").
3 Нетерминальные символы грамматики – множество состояний КА.
4 Если в таблице переходов КА есть переход из состояния А в состояние В при воздействии входного символа х – ввести правило следующего вида: А à xB.
5 Если D – допускающее состояние КА, то ввести правило следующего вида: D à e, где e – пустая цепочка(для отвергающих состояний правил нет).
6 Закончить составление правил, когда будут обработаны все непустые клетки управляющей таблицы ("error" – пустая клетка).
Пример: Задан КА
– входной алфавит V={a,b, --|};
– множество состояний автомата S={A,B,C};
– начальное состояние A;
– множество допускающих состояний S1={A,C};
– управляющая таблица приведена на рисунке.
Построить грамматику, которая будет порождать множество цепочек, допускаемых заданным КА.
