Задачи для семинарских занятий по теме - Конечные автоматы без выхода (1107933)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Задачи по теме “Конечные автоматы без выхода”1. Построить диаграммы Мура для конечных автоматов (КА) в алфавите A ={0, 1}, которые допускают следующие множества:1) {0, 10};2) все слова длины 3;3) все слова, которые начинаются словом 01;4) все слова, которые оканчиваются словом 00;5) все слова, которые содержат слово 110;6) все слова, имеющие четную длину;7) все слова, кроме слова 011;6) все слова, имеющие длину, не меньшую двух.2. Доказать конечную автоматность следующих множеств, построив диаграммуМура КА, допускающего это множество:1) произвольное конечное множество слов в алфавите A;2) любое множество вида A∗ \ X, где X – произвольное конечное множество словв алфавите A;3) множество всех слов в алфавите A = {0, 1}, которые имеют четную длину,начинаются буквой 0 и в которых буквы 0 и 1 чередуются;4) множество всех слов в алфавите A = {0, 1}, которые составлены из “блоков”010 и 001.3.

Определить, какие множества допускают следующие недетерминированные конечные автоматы (НКА) (предварительно построить для НКА диаграммы Мура):1) Q = {q1 , q2 }, f (0, q1 ) = {q1 , q2 }, f (1, q1 ) = {q2 }, f (0, q2 ) = {q2 }, f (1, q2 ) = {q1 , q2 },F = {q2 }.2) Q = {q1 , q2 }, f (0, q1 ) = {q1 , q2 }, f (1, q1 ) = {q2 }, f (0, q2 ) = {q2 }, f (1, q2 ) = {q1 , q2 },F = {q1 }.3) Q = {q1 , q2 , q3 }, f (0, q1 ) = {q2 }, f (1, q1 ) = {q1 , q2 }, f (0, q2 ) = {q3 }, f (1, q2 ) = {q3 },f (0, q3 ) = {q3 }, f (1, q3 ) = {q2 , q3 }, F = {q3 }.4) Q = {q1 , q2 , q3 }, f (0, q1 ) = {q1 , q2 }, f (1, q1 ) = {q1 }, f (0, q2 ) = {q2 }, f (1, q2 ) ={q2 , q3 }, f (0, q3 ) = {q1 , q3 }, f (1, q3 ) = {q1 , q3 }, F = {q3 }.4.

Для заданных НКА методом детерминизации построить эквивалентный детерминированный КА (т.е. допускающий то же множество слов):1) задача 3 1);2) задача 3 2);3) Q = {q1 , q2 }, f (0, q1 ) = {q1 }, f (1, q1 ) = {q1 , q2 }, f (0, q2 ) = {q1 , q2 }, f (1, q2 ) = {q1 },F = {q2 }.4) задача 3 3).5. Начиная с множеств {0} и {1}, при помощи операций объединения, произведения и итерации построить множества всех слов в алфавите A = {0, 1}, которые1) содержат подслово 0001;2) имеют нечетную длину;3) начинаются и оканчиваются на 1;4) не содержат подслово 01.16. Построить регулярное выражение, определяющее следующие множества слов валфавите = {0, 1}:1) любое конечное множество слов;2) дополнение (до множества {0, 1}∗ ) к любому конечному множеству слов;3) множество всех слов, являющихся конкатенацией слов 01 и 110;4) множество всех слов, содержащих или подслово 00 или подслово 101;5) множество всех слов, кроме слов 001, 110, 0111;6) множество всех слов с длиной, кратной трем;7) множество всех слов четной длины, содержащих подслово 111;8) множество всех слов нечетной длины, не содержащих подслово 100.7.

Для КА A и B построить НКА, который допускает множество D(A) · D(B):1) автомат A: Q = {q1 , q2 , q3 }, f (0, q1 ) = q2 , f (1, q1 ) = q1 , f (0, q2 ) = q2 , f (1, q2 ) = q3 ,f (0, q3 ) = q1 , f (1, q3 ) = q3 , F = {q1 , q3 },автомат B: Q = {q1 , q2 }, f (0, q1 ) = q1 , f (1, q1 ) = q2 , f (0, q2 ) = q2 , f (1, q2 ) = q2 ,F = {q2 };2) автомат A: Q = {q1 , q2 }, f (0, q1 ) = q1 , f (1, q1 ) = q2 , f (0, q2 ) = q1 , f (1, q2 ) = q2 ,F = {q2 };автомат B: Q = {q1 , q2 , q3 }, f (0, q1 ) = q2 , f (1, q1 ) = q3 , f (0, q2 ) = q2 , f (1, q2 ) = q2 ,f (0, q3 ) = q3 , f (1, q3 ) = q1 , F = {q2 , q3 }.8.

Для КА A построить НКА C, для которого D(C) = D(A)∗ :1) автомат A из задачи 7 1);2) автомат B из задачи 7 2).9. Пусть X – конечно-автоматное множество в алфавите A = {0, 1}, а α, β —произвольные слова в алфавите A. Доказать, что в результате одновременной замены буквы 0 словом α, а буквы 1 словом β во всех словах множества X образуетсяконечно-автоматное множество.10.

Пусть X — конечно-автоматное множество, Rev(X) — множество всех слов,обратным к словам из X (т.е. слов, прочитанных в обратном порядке). Доказать, чтомножество Rev(X) также конечно-автоматно.2.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций