Контрольная работа по дисциплине «теория автоматов и формальных языков»

ЗАДАНИЯ:

1. Построить таблицу переходов-выходов по заданному графу автомата Мили. 

2. Построить граф автомата Мура по заданной таблице.

3. Построить и програмно реализовывать автомат Мили. 

a) Построить автомат (в виде графа), «добавляющий» в текст, содержащий произвольные символы, пробел после каждого многоточия

Подробно описать 

• множество входных сигналов, 

• множество выходных сигналов, 

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

4. Дана грамматика. Постройте примеры цепочек вывода. Опишите язык, порождаемый грамматикой. 

a) S→bS|aA, A→aA|

5. Дана грамматика. Укажите тип каждого правила грамматики по Хомскому и тип грамматики.