Практическое занятие 4. Построение конечных автоматов.

Цель: освоение навыка построения конечных распознавателей, распознавания цепочек языка.

Задание 1.

Постройте конечный автомат с входным алфавитом {0,1}, который допускает в точности такое множество цепочек:

1. Число единиц четное, а число нулей – нечетное;

2. Между вхождениями единиц четное число нулей;

3. За каждым вхождением пары 11 следует 0;

4. Каждый третий символ – единица;

5. Все входные цепочки, начинающиеся с нуля и кончающиеся на единицу;

6. Все цепочки, в которых перед и после каждой единицы стоит ноль.

Рекомендуемая литература: [2], [3], конспект лекций.

Этапы выполнения.

Для каждого множества цепочек:

1. Определить множество состояний конечного автомата, выделив начальное состояние.

2. Задать функции переходов для каждой пары (состояние, входной символ).

3. Определить финальные состояния конечного автомата.

4. Оформить полученное решение в виде таблицы переходов.

5. Привести для каждого автомата примеры цепочек и продемонстрировать на них работу построенного автомата.

Задание 2.

Опишите словами множества цепочек, распознаваемых каждым из следующих автоматов:

	0	1
A	B	A	0
B	B	C	0
C	C	C	1

	0	1
A	B	C	0
B	C	B	1
C	C	C	0

	0	1
A	B	C	0
B	D	B	1
C	C	D	1
D	D	D	0

	0	1
A	B	A	0
B	D	C	0
C	C	D	1
D	D	D	0

Рекомендуемая литература: [2], [3], конспект лекций.

Этапы выполнения.

Для каждого автомата:

1. Описать словами множества цепочек, распознаваемых данным автоматом.

2. Привести для описанного языка примеры цепочек и продемонстрировать их распознавание заданным автоматом.