Дискретная математика (Задача 7, вариант 4). Задача 7, вариант 4. Задача 7 Автомат задан набором где алфавит, множество начальных состояний, входов
![]()
|
Вариант 4 Задача 7 Автомат задан набором ![]() где ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Построить граф автомата и найти язык ![]() Детерминизировать автомат. Построить графы автоматов, представляющих языки ![]() Из построенных графов удалить ![]() Вход ![]() ![]() ![]() ![]() Решение: Граф автомата ![]() Толстой линией обозначено начальное состояние, двойной линией обозначены конечные состояния. Найдём язык, который распознаётся данным автоматом, составим таблицу возможных переходов между состояниями автомата и соответствующих последовательностей символов,
в таблице приведены последовательности символов, из которых строятся слова языка ![]() 2 – наименьшие возможные слова языка ![]() 1- 2 - возможные слова языка ![]() 3 - 5 - возможные повторяющиеся последовательности символов, последовательности могут повторяться в любом количестве и в любом порядке, 6 - возможные окончания слова, если слово заканчивается в состоянии 1, 2 - последовательности, которые также являются словами языка ![]() для языка ![]() ![]() Данный автомат недетерминированный, так как есть из одного состояния при прочтении символа есть неоднозначные переходы, например, из состояния 1 при прочтении ![]() ![]() ![]() из состояния 5 при прочтении ![]() ![]() ![]() Найдем эквивалентный детерминированный автомат. Представим все возможные переходы автомата в виде таблицы, в которой каждому состоянию соответствует строка, каждому символу алфавита соответствует столбец, на пересечении строки и столбца, соответствующего символу алфавита указываются состояния, в которые переходит автомат из данного состояния при прочтении данного символа, в последнем столбце указано, является ли данное состояние конечным, 0 – состояние не является конечным, 1 – состояние является конечным,
построим детерминированный автомат, первая строка таблицы записывается без изменений, следующими в качестве состояний записываются состояния и множества состояний, в которые переходит первое состояние, далее в качестве состояний записываются состояния и множества состояний, в которые переходят предыдущие состояния и множества состояний, и так пока все состояния и множества состояний, в которые переходят предыдущие состояния и множества состояний, не будут перечислены в таблице, получаем таблицу
Создадим обозначения для новых состояний , представленных множествами состояний, и запишем обозначения в 5-й столбец таблицы,
запишем автомат с использованием новых обозначений,
Построим граф детерминированного автомата ![]() толстой линией обозначено начальное состояние, двойной линией обозначены конечные состояния. Построим граф детерминированного автомата, представляющего язык ![]() граф детерминированного автомата, представляющего язык ![]() ![]() Построим графы автоматов, представляющих объединение языков ![]() конкатенацию языков ![]() ![]() ![]() ![]() 0 – начальное состояние, для того, чтобы не возникало неоднозначности в обозначении состояний автоматов, будем обозначать состояния автомата, представляющего язык ![]() 9 - 11 , то есть к каждому обозначению состояния автомата для ![]() прибавим 8 . Новые переходы будем обозначать цветными стрелками, ![]() при удалении ![]() переходы, если прочитаны символы ![]() ![]() Построим граф автомата, представляющего объединение языков ![]() обозначим в виде прямоугольников графы автоматов , представляющих языки ![]() ![]() ![]() ![]() Граф автомата, представляющего объединение языков ![]() ![]() Построим граф автомата, представляющего конкатенацию языков ![]() обозначим в виде прямоугольников графы автоматов , представляющих языки ![]() ![]() языков ![]() ![]() Граф автомата, представляющего конкатенацию языков ![]() ![]() Построим граф автомата, представляющего итерацию языка ![]() ![]() обозначим в виде прямоугольника граф автомата , представляющего язык ![]() ![]() ![]() Граф автомата, представляющего итерацию языка ![]() ![]() Из построенных графов автоматов, представляющих объединение языков ![]() конкатенацию языков ![]() итерацию языка ![]() удалим ![]() Граф автомата, представляющего объединение языков ![]() ![]() ![]() граф автомата, представляющего объединение языков ![]() без ![]() ![]() Граф автомата, представляющего конкатенацию языков ![]() ![]() ![]() . граф автомата, представляющего конкатенацию языков ![]() без ![]() ![]() Граф автомата, представляющего итерацию языка ![]() ![]() ![]() ![]() ![]() граф автомата, представляющего итерацию языка ![]() ![]() ![]() |