Составьте программу, выполняющую минимизацию заданного инициального автомата Мили.
Программа должна считывать из стандартного потока ввода количество состояний автомата n, размер входного алфавита m (0<m≤26), номер начального состояния q0 (0≤q0<n), матрицу переходов Δ и матрицу выходов Φ. Матрицы переходов и выходов имеют размеры n×m. При этом элементами матрицы переходов являются номера состояний, а элементами матрицы выходов – выходные сигналы. Каждый выходной сигнал представляет собой не содержащую пробелов строку.
Будем считать, что входными сигналами автомата являются m первых строчных букв латинского алфавита. При этом первый столбец матриц Δ и Φ соответствует букве “a”, второй столбец – букве “b”, и т.д.
Программа должна выводить в стандартный поток вывода описание диаграммы минимизированного автомата на языке DOT. При этом каждое состояние на диаграмме должно быть представлено кружком с каноническим порядковым номером состояния внутри, а каждая дуга должна иметь метку вида “x(y)”, где x и y – это входной и выходной сигналы, соответственно.
Составьте программу, выполняющую детерминизацию заданного недетерминированного распознающего автомата.
Программа должна считывать со стандартного потока ввода количество состояний N, количество переходов M, затем M описаний переходов, массив принимающих состояний, а также номер начального состояния.
Каждый из M переходов описывается следующим образом: сначала идёт номер исходного состояния, затем – номер целевого состояния, а за ними следует символ, которым помечен переход. Состояния нумеруются с нуля. Символ задаётся в виде строки, причём λ-переход помечается строкой “lambda”.
Элемент SFinal_iS массива принимающих состояний содержит 1, если i-тое состояние принимающее, и 0 – в противном случае.
Описанние детерминированного автомата на языке DOT должно выводиться в стандартный поток вывода. При этом непринимающие состояния детерминированного автомата должны иметь форму круга (атрибут “shape = circle”), а принимающее – форму двойного круга (атрибут “shape = doublecircle”). Состояния детерминированного автомата должны быть помечены отсортированной по возрастанию последовательностью номеров соответствующих им состояний недетерминированного автомата, взятой в квадратные скобки. Кроме того, если из одного состояния в другое имеется сразу несколько переходов, то все эти переходы должны изображаться одной дугой, помеченной списком символов, соответствующих этим переходам. Символы в списке должны разделяться запятыми и располагаться в порядке их первого появления во входных данных.