У вас вопросы?
У нас ответы:) SamZan.net

тематического моделирования Типовой расчет 4 Конечные автоматы

Работа добавлена на сайт samzan.net: 2016-03-30

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 7.6.2025

Московский энергетический институт

 (Национальный исследовательский университет)

       Кафедра математического моделирования

Типовой расчет №4

Конечные автоматы

            

                                                                             Выполнила: Голубева Е. В.

                                                   Вариант № 6

                                                                         Учебная группа А-14-10

                                                                                 Проверил: Алексиадис Н. Ф.

Москва, 2012

  1. Построить детерминированный конечный автомат, допускающий цепочки из 0 и 1, которые содержат в себе подцепочку 01.

*

1

0

0,1

0

1

Чтобы перейти в финальное состояние , нужно, чтобы за некоторым входным символом 0 шел входной символ 1.

  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:

  1. Написать регулярное выражение для языка:

Множество слов из нулей и единиц, содержащих не более одной пары последовательных единиц.

  1. Написать регулярные выражения для следующих языков:

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

б) множество цепочек из нулей и единиц, в которых нет подцепочки 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)




1. Внеоборотные активы 3.html
2. Химия в биологии медицине и в производстве лекарственных веществ
3. Методы диагностики тревоги и тревожности младших школьников
4. Варианты учета затрат 15 4
5. Классификация органов исполнительной власти и виды правонарушений
6. Контроль характеристик термоперетворювачів опору
7. Лабораторная работа 2 Указания к работе Самолет в небе Часть 1
8. Лекции по матану III семестр переходящие в шпоры
9. тема і передумови її успіху слід виявляти у зовнішньому середовищі оперативно адаптуючи та оптимізуючи мік
10. Тема индивидуального задания ИЗ для эконом госуправл 1123 Т