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

Задачи по теме “Конечные автоматы без выхода”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.