На этой странице вы найдете исправленные упражнения по оптимизации автоматов, решимость и минимизация.
Определение
Упражнение 1
Определите следующие автоматы:
Упражнение 2
Рассмотрим алфавит A, составленный из букв алфавита французского языка, и язык L = {w ∈ A* / w оканчивается на man}. найти автомат детерминистский, который порождает L.
Упражнение 3
Пусть L будет языком, принятым автоматом A ниже:
Найти грамматика регулярная порождающая L. Найдите регулярное выражение обозначающий L. Найдите детерминированный автомат, принимающий L.
Вот грамматические произведения, полученные непосредственно из автомата: P → aP, P → aQ, Q → bP, Q → R, R → bR, R → cQ, R → bP, R → эпсилон. Нетерминалы (следовательно, узлы автомата) грамматики — {P,Q,R}, начальный символ — P.
Обозначая через Xп, ИКСд, ИКСр языков, принятых из состояний P, Q и R соответственно, система уравнений для этих языков такова:
Внимание, рекурсия нетерминала даст звезду, а раздача с нетерминалом вызовет конкатенацию!
Определяем автомат:
Упражнение 4
Рассмотрим регулярную грамматику G = (Γ,Σ,S,Π) с Γ = {S,P,R},Σ= {a,b} и Π = {S → P,P → baR,P → aS, R → bb,R → аР}. Найдите регулярное выражение для этого языка. Постройте автомат A, принимающий язык, определенный грамматикой G. Явно задайте A в виде (Q, Σ, q0, F, ∆). Найдите детерминированный автомат, принимающий этот язык.
Мы используем те же буквы S, P и R для языков, принятых из состояний S, P и R. Эти языки удовлетворяют системе уравнений:
Первое уравнение дает S = P, подставив выражения для S и R во второе уравнение, мы получим P = aP + ba(aP + bb), что эквивалентно P = (a + baa)P + babb. Здесь P действует как начальное состояние, потому что между S и P существует только один переход эпилона.
Решаем это последнее уравнение: P = (a+baa)∗babb, следовательно, L(A) = S = P = (a+baa)∗babb.
Начиная с автомата Томпсона, чтобы прийти к:
Определив автомат A, получим B (для большего удобства иногда полезно поставить мусорное состояние, берущее взаимодействия без узлов прибытия):
Упражнение 5
Построить детерминированный конечный автомат соответствующий каждому автомату ниже, и вычислить регулярное выражение для принятого языка, используя соответствующую грамматику:
Упражнение 6
Слепой бармен играет с покупателем в следующую игру: перед ним стоит поднос, на котором в форме квадрата стоят четыре стакана. Каждый из этих стаканов может быть возвращен или не возвращен без ведома бармена. Цель последнего — расположить так, чтобы все стаканы были повернуты в одну сторону. Для этого он может каждый ход выбирать одно из следующих трех действий: $
- перевернуть один из стаканов
- перевернуть два соседних стакана
- повернуть два противоположных стекла
но, чтобы усложнить задачу, покупатель может повернуть поднос на любое количество четвертей оборота между каждым действием бармена. Игра останавливается, как только достигается одна из двух выигрышных позиций.
Покажите, что мы можем ограничить число различных конфигураций четырьмя, а затем представить возможные действия в игре недетерминированным автоматом.
Определите этот автомат и выведите выигрышную стратегию для бара.
Возможны только четыре конфигурации:
- все четыре стекла направлены в одном направлении (конфигурация q0)
-три стекла в одном направлении и четвертое в другом направлении (конфигурация q1)
- два соседних стекла направлены в одну сторону, а два других - в другую (конфигурация q2)
- два противоположных стекла направлены в одну сторону, а два других - в другую (конфигурация q3).
Обозначим буквой:
-имеет изменение ориентации одного из четырех стекол
-b изменение ориентации двух соседних стекол
-c изменение ориентации двух противоположных линз.
Тогда игра может быть представлена следующим недетерминированным автоматом:
Его определение приводит к следующему автомату:
Мы видим, что распознанное слово cbcacbc приводит к выигрышной позиции для бармена.
Минимизация
Упражнение 7
Рассмотрим следующий автомат A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}):
Приведите таблицу, описывающую ∆. Принимается ли слово баабаб автоматом А (проверьте, развернув написанную ранее грамматику)? Назовите минимальный детерминированный конечный автомат, который распознает тот же язык, что и A.
∆ = {(1, а, 2), (1, Ь, 1), (1, Ь, 3), (2, а, 1), (2, а, 3), (3, Ь, 1) }
баабаб не принимается автоматом. К автомату можно добавить сток, обозначаемый #, чтобы сделать его комплектным. Тогда дерево чтения выглядит следующим образом:
Ни один лист не соответствует конечному состоянию, обратите внимание, что все листы попадают в колодец.
Детерминированный автомат:
Состояния {1} и {1,3} имеют одинаковые правила. Таким образом, находим минимальный автомат:
Упражнение 8
Среди следующих регулярных выражений и автоматов укажите, какие автоматы и регулярные выражения представляют один и тот же язык:
Мы хотим сравнить четыре языка. Мы вычисляем минимальный автомат каждого языка. Тогда достаточно сравнить эти автоматы. Действительно, минимальный автомат — это канонический объект, зависящий только от языка, поэтому два языка равны, если они имеют один и тот же минимальный автомат (по модулю переименования состояний).
1 – Рациональное выражение (ab∗a + b(a + b))∗. Мы начнем с создания автомата, используя метод на ваш выбор:
Теперь мы хотим построить минимальный автомат языка. Для этого необходимо сначала определить, а затем минимизировать вышеуказанный автомат. К счастью, у нас уже есть детерминированный автомат, поэтому мы можем перейти непосредственно к алгоритму минимизации, который дает нам следующий результат:
2 – Регулярное выражение (ab + b(a + b))∗. Начнем с построения автомата по методу Глушкова:
Точно так же автомат уже детерминирован. После минимизации имеем следующий автомат:
3 – Чтобы минимизировать A3, мы должны сначала определить его. Вот результат алгоритма определения:
И после минимизации:
4 – Автомат уже детерминирован, после минимизации получаем:
Теперь, когда мы построили минимальный автомат для каждого из четырех языков, мы можем их сравнить. Заметим, что по модулю переименования состояний языки A3 и (ab + b(a + b))∗ имеют один и тот же минимальный автомат и поэтому равны. То же верно и для языков A4 и (ab∗a + b(a + b))∗.
Упражнение 9
Пусть Σ = {a,b}, рассмотрим два следующих языка: L — язык, образованный всеми словами Σ∗, содержащими aba; M — язык, определяемый регулярным выражением (b + aa∗ bb)∗ (ε + aa∗ + aa∗ b).
Укажите недетерминированный автомат, распознающий L. Определите минимальный автомат A, распознающий L.
Приведите недетерминированный автомат с ε -переходами, распознающий M. Определите минимальный автомат B, распознающий M.
Сравнивая два полученных автомата A и B, делаем вывод, что L = комплементарный(M). С точки зрения автомата, дополнение автомата A сводится к превращению входящих состояний в конечные состояния и наоборот.
После определения языка или грамматики L обучаем автомат по методу Глушкова:
Затем определяем его:
Мы переименовываем состояния по порядку в A, B, C, D, E, F, чтобы избежать двусмысленности. Затем минимизируем:
Аналогично для автомата, распознающего M:
Мы детерминируем его (заметим, что мы формируем состояние мусора):
Мы переименовываем состояния по порядку на K, L, M, N, чтобы избежать двусмысленности. Автомат уже минимальный.
Заметим, что единственное различие между детерминированными автоматами A и B состоит в том, что конечные состояния одного нефинальны в другом. Из чего мы можем сделать вывод, что их языки дополняют друг друга.
RU 
FR 
EN 
ES