Синтез цифровых автоматов. Захаров Н.Г - 4 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

3
ОГЛАВЛЕНИЕ
Введение .......................................................................…….................................….... 5
1. Основы теории формальных грамматик ....................................................…... 6
1.1. Основные понятия теории автоматов ................................................ …............ 6
1.2. Основные понятия теории формальных грамматик ..........................……........ 8
1.3. Классификация языков по Хомскому...................................................……....... 11
1.4. Распознающие устройства и автоматы.................................................……....... 13
1.4.1. Концепция порождения и распознавания ...........................................……... 14
1.4.2. Распознающие, порождающие и преобразующие формальные грамматики.. 16
1.5. Автоматы и формальные языки .....................................................……............. 18
1.5.1. Понятие об информации и ее преобразованиях ............................................ 18
1.5.2. Преобразование алфавитной информации ....................................……......... 20
1.5.3. Способы задания автоматов ..............................................................……...... 21
Контрольные вопросы ...................................................................................……….. 25
2. Машины Тьюринга ...............................................................……......................... 25
2.1. Основные понятия .........................................................................……............... 25
2.2. Машины Тьюринга с двумя выходами ..........................................……............. 27
2.3. Машины Тьюринга и линейно-ограниченные автоматы .................................. 29
2.4. Автоматы с магазинной памятью и бесконтекстные языки ..............….......... 30
2.4.1. Автоматы с магазинной памятью ........................................…….................... 30
2.4.2. Бесконтекстные (контекстно-свободные) языки .......................................... 32
Контрольные вопросы ..............................................................……........................... 33
3. Абстрактный конечный автомат .....................................................……........... 33
3.1. Абстрактная теория автоматов ......................................................…….............. 33
3.1.1. Модель дискретного преобразователя Глушкова В.М ................................. 33
3.1.2. Понятие об абстрактном автомате и индуцируемом им отображении ....... 34
3.2. Представление событий в автоматах........................................……................... 36
3.2.1. Автоматные отображения и события ........................................…….............. 36
3.2.2. Представление событий в автоматах ...........................................……........... 38
3.2.3. Регулярные языки и конечные автоматы ....................................…......……. 39
3.3. Алгоритм синтеза конечных автоматов .............................……........................ 40
3.3.1. Основной алгоритм синтеза конечных автоматов .................……............... 40
3.3.2. Усовершенствованный основной алгоритм синтеза конечных автоматов.. 45
3.4. Автоматы Мили и Мура .......................................................……........................ 49
3.4.1. Автомат Мили ..................................……......................................................... 49
3.4.2. Автомат Мура ....................................................................……....................... 52
3.4.3. Получение неполностью определенных (частичных) автоматов ................ 53
3.5. Синтез автоматов по индуцируемым ими отображениям ................................ 53
3.5.1. Общий метод решения задачи ..................................................……............... 53
3.5.2. Синтез автомата Мили ................................................................……............. 55
3.5.3. Синтез автомата Мура………………………………………………………... 57
Контрольные вопросы……………………………………………………………….. 58
4. Структурный конечный автомат ........................................................................ 58
4.1. Основные понятия структурной теории автоматов ..................…..................... 58
4.2. Композиция автоматов и структурные схемы .........................…...................... 61
4.3. Условия корректности и правильности построения схем ........……................ 63
4.4. Канонический метод структурного синтеза автомата ..................……............ 67

Страницы