Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Типовой расчет №4
Конечные автоматы
Выполнила: Голубева Е. В.
Вариант № 6
Учебная группа А-14-10
Проверил: Алексиадис Н. Ф.
Москва, 2012
*
1
0
0,1
0
1
Чтобы перейти в финальное состояние , нужно, чтобы за некоторым входным символом 0 шел входной символ 1.
а) Множество цепочек, в которых всякая подцепочка из пяти последовательных символов содержит хотя бы два 0;
Чтобы не загромождать диаграмму Мура стрелками, дополним задание автомата значаниями функции выхода для финальных состояний:
На приведенной диаграмме стрелки изображены только для перехода из финального состояния .
1
16
0,1
1
0
0
150
140
1
0
0,1
130
120
110
1
0,1
0,1
0
100
9
8
7
*
1
0,1
0,1
0,1
0
0
6
5
4
3
2
1
1
0,1
0,1
0
0
210
200
190
180
170
0,1
1
0
32
31
30
34
1
1
0
33
35
0,1
1
0,1
0
0
250
220
240
230
0
1
37
36
1
38
0,1
1
0
0
280
270
260
1
29
0,1
б) Множество цепочек, которые начинаются или оканчиваются (или и то, и другое) последовательностью 01;
Автомат, допускающий цепочки, которые начинаются ИЛИ оканчиваются последовательностью 01:
1
0
*
1
0,1
1
0
0
0
1
0
1
1
0
1
0
0
1
0
1
0,1
0,1
0
1
0
Автомат, допускающий цепочки, которые начинаются И оканчиваются последовательностью 01:
1
в) Множество цепочек, в которых число нулей делится на 5, а число единиц на 3:
Множество слов из нулей и единиц, содержащих не более одной пары последовательных единиц.
а) множество цепочек, состоящих из нулей и единиц, в которых число нулей кратно пяти:
б) множество цепочек из нулей и единиц, в которых нет подцепочки 101:
в) множество цепочек, состоящих из нулей и единиц, в которых число нулей делится на 5, а количество единиц четно:
5. Минимизировать автомат, удовлетворяющий условиям:
.
*
(0,0)
(1,0)
(1,0)
(0,1)
(1,0)
(1,0)
(0,1)
(0,1)
(0,1)
Исходный автомат:
(1,0)
Из условия имеем:
Следовательно, состояния отличимы входным словом 10.
Следовательно, состояния отличимы входным словом 0.
Таким образом, состояния - три различных состояния, поэтому в минимизированном автомате число состояний будет не меньше трех.
Минимизированный автомат с тремя состояниями:
(1,0)
*
(0,1)
(1,0)
(0,0)
(1,0)
(0,1)