3 задачи по автоматам и булевым функциям

3 задачи по дискретной математике (часть условий на фотографии):

Задание 1: а) Вычислить таблицу значений функции F. б) Найти минимальные ДНФ F и W. в) Выяснить полноту системы {f, w}. Если система не полна, дополнить систему функцией g до полной системы. *Запрещается дополнять систему константами, отрицанием и базовыми функциями двух переменных. Не допускается дополнение функцией, образующей с F или W полную подсистему, кроме случаев, когда иное невозможно. г) Из функциональных элементов, реализующих функции полной системы {f, w} или {f, w ,g}, построить функциональные элементы, реализующие базовые функции (И, ИЛИ, НЕ, 0, 1)

Задание 2: Автомат задан набором ({a,b}, {q1,q2,q3,q4,q5}, Qs, Qf ), где {a,b} - алфавит, Qs - множество начальных состояний (входов), Qf - множество конечных состояний (выходов), и списком дуг с метками, определяющих допустимые переходы. Запись (i, j, a, b)означает, что дуга (i, j), идущая из состояния qi, в состояние gj, имеет две метки - a и b.

1) Построить грвф автомата и найти язык L, допускаемый автоматом.

2) Детерминизировать автомат

3) Построить графы автоматов, представляющих языки (прикрепленное фото)

4) Их построенных графов удалить лямбда-переходы

Задание 3: Конечный автомат задан кортежем ({0,1}, {1,0}, {q1,q2,q3,q4,q5,q6}, q1, f, g), где {0,1} - входной алфавит, {0,1} - выходной алфавит, Q = {q1,q2,q3,q4,q5,q6} - множество состояний конечного автомата с выходом, q1 - начальное состояние автомата, f и g - функция переходов и функция выходов конечного автомата (фото), где f(0, qi) = qai, f(1,qi) = qbi, g(0,qi) = ci, g(1,qi) = di. Т.е. из вершины qi, i = 1,2,3,4,5,6 по символу 0 переходим в вершину с номером ai, по символу 1 - в вершину с номером bi, при переходе из вершины qi, i = 1,2,3,4,5,6 по символу 0 получаем выходной символ Ci, а по символу 1 - выходной символ di.

Представить конечный автомат с выходом графом, минимизировать, задать минимальный автомат графом.