7. Таблицей переходов заданы автоматы-распознаватели и . Определить, являются ли эти автоматы эквивалентными друг другу. Если автоматы эквивалентны, то указать классы эквивалентности.

	0	1		0	1
1s	14	17	2s	28	28
13	17	1f	23	27	26
14	15	19	24	23	2f
15	13	16	25	29	26
16	1s	19	26	2s	24
17	19	18	27	25	2f
18	1s	13	28	25	29
19	15	1f	29	23	2f
1f	19	14	2f	27	28

8. Построить детерминированный автомат эквивалентный автомату , функция переходов которого задана таблицей:

	0	1
s	3	4
2	s,4	2
3	4	2,4
4	f	s
f	s	3

9. По заданному регулярному выражению построить автомат с один начальным и одним финальным состояниями.

a) [1(02) ^*2+2^*1100]^*[ 02(21) ^*][0(21)^*1^*0+(10)^*1(20)^*2]^*

б) [1(20)^*+0(12)^*01][(100)^*212+2(11)^*0]^*[ 0^*2]

ВПИ-Лабораторная работа №1-2. 7 вариант.

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

	0	1
s	2	f
2	s	3
3	f	2
f	2	3

11. По заданной системе определяющих соотношений ρ построить детерминированный всюдуопределенный автомат A(ρ).

ρ	(02, 210); (0, 12); (11, 01012); ( , 121); (22, 100); (101, 220); (1010, 12121); (20, 0221); (11102, 01011212); (120, 200210); (002002, 121011210101)

12. Определить является ли ρ системой определяющих соотношений для автомата .

ρ	(0010, 0100011); (011, 011010); (01, 000100); (101, 1101); (010100, 00001100); (1, 01); (111, 00100); (1110, 010111); ( , 0110101); (001, 1110)

	0	1
s	3	7
2	2	8
3	5	7
4	7	8
5	s	3
6	2	s
7	4	6
8	6	5

13. Определить является ли система определяющей для автомата , заданного диаграммой.

ρ	(0210212, 201110220); (11102, 1221010); (011001211, 22002121110); (1, 2222); ( , 22); (2101010012, 11101220102); (222, 122101); (012201, 101101020); (012101, 0120110)
M	21001021010; 02100; 201200; 011011; 210201122; 0102; 002111201; 201011; 01121; 00202; 222101202; 0012; 201201; 210101200; 0101012

ВПИ-Лабораторная работа №1-2. 7 вариант.

14. Минимизировать автомат-преобразователь , функции переходов и выходов которого заданы таблицей:

	0	1
a0	a2/0	a9/0
a1	a4/1	a2/0
a2	a5/1	a8/0
a3	a7/0	a6/1
a4	a10/0	a9/0
a5	a0/1	a10/0
a6	a8/0	a5/0
a7	a4/1	a10/0
a8	a5/0	a6/1
a9	a9/0	a10/1
a10	a1/1	a3/0

15. Для заданного таблицей автомата Мили построить эквивалентный ему автомат Мура

	0	1
a0	a2/0	a4/0
a1	a3/1	a5/1
a2	a0/0	a1/1
a3	a5/0	a0/1
a4	a1/1	a3/0
a5	a3/0	a4/0

ВПИ-Лабораторная работа №1-2. 7 вариант.

ВПИ-Лабораторная работа №1-2.

8 вариант.

1. Построить вывод слов (сверху вниз) и (снизу вверх) в грамматике :

2. Определить какие из слов принадлежат языку, задаваемого порождающей грамматикой :

3. Построить праволинейную грамматику, эквивалентную данному автомату:

4. Построить автомат, эквивалентный грамматике :

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

6. Автомат-распознаватель задан таблицей переходов. Определить, является ли пустым язык , порожденный этим автоматом. Если язык не пустой, то указать хоть одно слово, принадлежащее языку .

	0	1	2
s	5	10	7
3	7	9	3
4	s	f	8
5	3	8	5
6	7	9	3
7	10	7	s
8	4	s	f
9	6	4	s
10	5	s	10
f	6	8	9