2014-02-18
392
Подстановка правил
Добавление нетерминала
Решение
1 Проверка нетерминалов на продуктивность.
В правых частях правил (5) и (6) только терминалы. Внесем в создаваемый список продуктивных нетерминалы B и, D. Затем в соответствии с правилом (3) – A (в правой части терминал и продуктивный нетерминал); в соответствии с правилом (2) – S; анализ других правил список не пополняет. Получен исчерпывающий список продуктивных нетерминалов – { B, D, A, S}. В списке отсутствует нетерминал С (непродуктивный, правило (4) для минимизации исходной грамматики исключим из множества P).
2 Проверка нетерминалов на достижимость.
Внесем на первом шаге в создаваемый список достижимых нетерминалов начальный символ грамматики S, затем на основании правила (2) дополним список нетерминалом A; правило(3) дает основания внести в список нетерминал В. Дальнейший анализ правил в соответствии с алгоритмом поиска достижимых нетерминалов список не пополняет. Получен исчерпывающий список продуктивных нетерминалов – {S,A,B}. В списке отсутствует нетерминал D (недостижимый, правило (6) для минимизации исходной грамматики исключим из множества P).
|
|
|
В результате этих преобразований получили минимальную грамматику G1[S], эквивалентную исходной.
G1[S]: VN = {S, A, B}; VT = {a, b, d}; начальный символ S;
P = { S à aS (1), S à aA (2), A à bB (3), B à d (4) }.
Не нарушая эквивалентности часть цепочки, составляющей правую часть любого правила исходной грамматики, можно обозначить новым нетерминалом (добавить нетерминал в множество VN) и дополнить множество правил P правилом, определяющим новый нетерминал.
Пример: Пусть в исходной грамматике G одно из правил имеет вид A à abВc. Обозначив bB через новый нетерминал N, заменим это правило двумя: A à aNc; N à bB.
Не нарушая эквивалентности процедуру добавления нетерминала можно применять многократно.
В множество правил P исходной грамматики, не нарушая эквивалентности, можно добавить новые правила, которые получаются в результате подстановки в любое правило, содержащее в правой части нетерминалы, их значений из других правил. При этом правила, участвовавшие в подстановках, можно исключить из множества Р.
Другими словами, в множество Р можно добавить правило
A à х, если A+à х (т.е. цепочка х выводима из А в исходной грамматике).
При построении автоматов – распознавателей грамматик к виду правил предъявляются определенные требования. Одно из них – отсутствие в правилах грамматики левосторонней рекурсии(правил вида 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};
– управляющая таблица приведена на рисунке.
Построить грамматику, которая будет порождать множество цепочек, допускаемых заданным КА.
