Структуры данных и модели вычислений


Автоматное задание языков - часть 4


где , если , , если . Решив систему, берем в качестве ответа значение переменной .

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


Рис. 13.2. 

Решение. Запишем систему уравнений

Заметим, что при записи системы мы упростили обозначения переменных, используя индексы.

Из четвертого уравнения получаем . Подставляя полученное выражение во все остальные уравнения, получим систему из трех уравнений:

Перепишем ее в стандартном виде:

Из третьего уравнения получаем и подставляем в остальные уравнения:

Преобразуем второе уравнение к стандартному виду

и получаем из него

Наконец, получаем ответ




Начало  Назад  Вперед