По праволинейной грамматике построить конечный автомат

При решении данного задания, по словесному описанию языка (Σ={a,b,c}) составим регулярное выражение (см. стр. 2). По этому регулярному выражению построим праволинейную грамматику, порождающую данный язык (см. стр. 4) и выпишем вывод четырехбуквенного слова. По получившейся грамматике составим систему регулярных уравнений и решим ее.
Длина каждого слова не меньше 2, и вторая буква всегда b.
Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний AA и BB такой, что имеется переход из AA в BB по символу cc, добавим в грамматику правило A→cBA→cB. Затем для каждой пары состояний автомата AA и BB такой, что имеется переход из AA в BB по символу cc, и BB является допускающим состоянием в автомате, добавим в грамматику правило A→cA→c.
Докажем, что если для автомата верно ⟨S,α⟩⊢∗⟨U,ε⟩⟨S,α⟩⊢∗⟨U,ε⟩, то для построенной грамматики верно S⇒∗αUS⇒∗αU. Будем доказывать индукцией по переходам в автомате.
Базой индукции будут переходы за 00 шагов.
Индукционный переход: пусть данное свойство выполняется для переходов длины k−1k−1. Докажем, что верно и для переходов за kk шагов.
Рассмотрим переход ⟨S,α⟩⊢k⟨U,ε⟩⟨S,α⟩⊢k⟨U,ε⟩, а именно его последний шаг: ⟨S,α⟩⊢k−1⟨Q,c⟩⊢⟨U,ε⟩⟨S,α⟩⊢k−1⟨Q,c⟩⊢⟨U,ε⟩.
Так как для k−1k−1 шага верно, то S⇒k−1αc−1QS⇒k−1αc−1Q, но по построению грамматики имеется правило Q→cUQ→cU, значит S⇒k−1αc−1Q⇒αc−1cU=αUS⇒k−1αc−1Q⇒αc−1cU=αU. Таким образом, доказали для kk шагов.
Докажем в обратную сторону, а именно из S⇒∗αUS⇒∗αU следует ⟨S,α⟩⊢∗⟨U,ε⟩⟨S,α⟩⊢∗⟨U,ε⟩. Доказательство также проведем по индукции. Индукция будет идти по количеству примененных подряд правил.
Базой индукции будут строки, выводимые в грамматике из начального нетерминала SS за 00 применений правил.
Индукционный переход: пусть верно для k−1k−1 применения правил. Рассмотрим произвольную строку, полученную за kk применений правил. Рассмотрим последнее применение правила. Если оно имело вид A→aBA→aB, значит в автомате возможен переход ⟨A,a⟩⊢⟨B,ε⟩⟨A,a⟩⊢⟨B,ε⟩, а если A→aA→a, то BB является допускающим в автомате. Таким образом, свойство выполняется для kk последовательно примененных правил. Эквивалентность языков автомата и грамматики доказана.
Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат. Введём специальное допускающее состояние okok. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием okok (Q=N∪okQ=N∪ok). Для правил вида A→aBA→aB определим функцию перехода в автомате как δ(A,a)=Bδ(A,a)=B. Для правил вида A→aA→a определим функцию перехода в автомате как δ(A,a)=okδ(A,a)=ok.
Докажем, что если слово выводится в грамматике, то оно допускается автоматом . Рассмотрим последовательность применений правил, дающую слово αα длины kk. Для каждого правила вида A→aBA→aB в автомате существует переход из состояния AA в состояние BB по символу aa. Таким образом, если после k−1k−1 применения правил мы можем получить строку вида αc−1Bαc−1B, то в автомате имеется соответствующая последовательность переходов ⟨S,α⟩⊢k−1⟨B,c⟩⟨S,α⟩⊢k−1⟨B,c⟩, а поскольку можно вывести αα, то хотя бы для одной строки такого вида существует правило B→cB→c, а значит в автомате есть переход ⟨B,c⟩⊢⟨ok,ε⟩⟨B,c⟩⊢⟨ok,ε⟩. Таким образом автомат допускает слово αα.
Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово αα длины kk. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово ⟨S,α⟩⊢k⟨ok,ε⟩⟨S,α⟩⊢k⟨ok,ε⟩. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из k−1k−1 шага ⟨S,α⟩⊢k−1⟨U,c⟩⟨S,α⟩⊢k−1⟨U,c⟩ существует соответствующая последовательность применений правил S⇒k−1αc−1US⇒k−1αc−1U. Для последнего перехода в автомате ⟨U,c⟩⊢⟨ok,ε⟩⟨U,c⟩⊢⟨ok,ε⟩ существует правило U⇒cU⇒c. Таким образом, существует последовательность применений правил грамматики, выводящая слово αα.
Проверка арифметического выражения на корректность
При рассмотрении различных вопросов, касающихся арифметических выражений, обычно оперируют следующими терминами. Операнд — число, переменная или выражение в скобках. Бинарная операция — операция, выполняющаяся над двумя операндами, например, сложение. Унарная операция - операция, выполняющаяся над одним операндом, знак этой операции обычно стоит непосредственно перед операндом, например, унарный минус или функция одной переменной.
Прежде чем проверять корректность того или иного выражения (не обязательно арифметического), его следует формально описать (по-другому говорят - ввести грамматику). Существует несколько способов для подобных описаний, например, синтаксические диаграммы, регулярные выражения, форма Бэкуса-Наура. Воспользуемся последним способом.
<выражение>::=<терм>|<терм>+<выражение>|<терм>-<выражение>
<терм>::=<множитель>|<множитель>*<терм>|<множитель>/<терм>
<множитель>::=(<выражение>)|<имя>|<натуральное число>
<имя>::=<буква>|<имя><буква>|<имя><цифра>
<натуральное число>::=<цифра>|<натуральное число><цифра>
<цифра>::=0|1|2|3|4|5|6|7|8|9
<буква>::=_|A|B|…|Z|a|b|…|z|
Здесь слева от метазнака ::= стоит определяемое понятие, а справа — его определение