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

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

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

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

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

a) [(20)^*1+2(10)^*1]^*[1^*12^*01][0(010)^* +12^*0^*12]^*

б) [1^*01+10(121)^*][021^*+(21)^*0]^*[0^*120^*1]

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

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

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

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

ρ	(2, 010); (12, 2001); (02, 22022); ( , 201); (12, 200); (20, 02012); ( , 010); (0, 212); (22, 20201); (10, 01010); (21, 2000)

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

ρ	(000, 1111); (0000, 10011); (0101, 00111); ( , 11); (01, 0010); (01110, 11101); (0, 100); (01010, 111001); (1, 1010); (00100, 0011100)

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

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

ρ	(0,1); (1,2); (21, 0111); ( , 120); (11, 120); (01, 11); (12, 220100); (221, 0100); (021, 12000); (10, 22120); (1022, 200102); (1000, 2212000)
M	011211; 10210; 22120211; 0001212; 1222; 202200; 12101202202; 02201; 12210; 002211; 1122102120; 2022121; 1002122; 0112101201

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

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

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

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

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

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

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

5 вариант.

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

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

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

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

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

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

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