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

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

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

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

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

a) [(212)^*20 +10(12)^*]^*[ 002^*(10)^*+2(20)^*11][00(11)^*]^*

б) [1(220)^*10+(100)^*12][00110^*]^*[(02)^*11+1(21)^*0(02)^*]

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

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

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

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

ρ	(1, 101); (2, 2001); (01, 00200); ( , 120); (02, 20); (20, 0122); ( , 100); (0, 110); (21, 2001); (10, 0102); (22, 0221)

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

ρ	(000, 0101); (001, 01011); (01, 00101011); ( , 1); (111, 00000); (011, 01111); (11, 01000); (0, 01001); (100, 0010); (0100, 110000)

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

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

ρ	(0202, 212121); (1, 20); ( , 21200212); (01, 10); ( , 02); (21, 0202); (01201,10111); (02101, 210220020); (0, 1021)
M	201; 12; 21220; 02222; 221; 02000; 102102; 0010; 210011; 0121012; 100; 20022; 20010; 01202; 211010

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

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

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

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

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

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

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

10 вариант.

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

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

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

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

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

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

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