На этой странице вы найдете исправленные упражнения по оптимизации автоматов, решимость и минимизация.

Определение

Упражнение 1

Определите следующие автоматы:

исправлены упражнения по оптимизации автоматов, детерминации и минимизации.

Упражнение 2

Рассмотрим алфавит A, составленный из букв алфавита французского языка, и язык L = {w ∈ A* / w оканчивается на man}. найти автомат детерминистский, который порождает L.

Пусть x представляет все буквы, которые не являются {a,m,n}. Автомат должен распознавать слова [az; А-Я]*человек. Построим индетерминированный автомат по алгоритму Томпсон (здесь мы замечаем, что переходы эпсилонов бесполезны). Автомат такой:

исправлены упражнения по оптимизации автоматов, детерминации и минимизации

После определения получаем следующий автомат:

исправлены упражнения по оптимизации автоматов, детерминации и минимизации

Упражнение 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_RURU