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

         

в качестве ответа значение переменной


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

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



Рис. 13.2. 

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

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

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


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

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

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


Содержание  Назад  Вперед