Структуры данных и модели вычислений
в качестве ответа значение переменной
где , если , , если . Решив систему, берем в качестве ответа значение переменной .
Задача. Построить регулярное выражение в алфавите , задающее язык, порождаемый автоматом , где , , и переходная функция задана таблицей
Рис. 13.2.
Решение. Запишем систему уравнений Заметим, что при записи системы мы упростили обозначения переменных, используя индексы.
Из четвертого уравнения получаем . Подставляя полученное выражение во все остальные уравнения, получим систему из трех уравнений: Перепишем ее в стандартном виде:
Из третьего уравнения получаем и подставляем в остальные уравнения:
Преобразуем второе уравнение к стандартному виду
и получаем из него
Наконец, получаем ответ
