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

UptoLike

ВУЗ: 

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

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

Рубрика: 

25
Таблица 2
Входы
Состояния
000 001 010 011 100
q
0
q
0
q
1
q
2
q
3
q
0
q
1
q
0
q
1
q
2
q
3
q
1
q
2
q
0
q
1
q
2
q
3
q
2
q
3
q
0
q
1
q
2
q
3
q
3
Контрольные вопросы
1. Основные понятия теории автоматов.
2. Основные понятия теории формальных грамматик.
3. Классификация языков по Хомскому.
4. Концепция порождения и распознавания.
5. Распознающие и порождающие формальные грамматики.
6. Таблицы переходов и выходов.
7. Граф автомата.
8. Матрицы переходов и выходов.
9. Понятие об информации и ее преобразованиях.
10. Преобразование алфавитной информации.
11. Способы задания автоматов.
2. МАШИНЫ ТЬЮРИНГА
2.1. Основные понятия
Машины Тьюринга представляют собой абстрактные устройства самого обще-
го типа и являются обобщением автоматов, рассмотренных ранее. Машины Тьюринга
наиболее близки к реальным ЭВМ, т. к. они представляют собой хорошую математи-
ческую модель вычислительной машины. Как показали многочисленные теоретиче-
ские исследования, классам языков, соответствующим четырем типам грамматики по
классификации Хомского, можно поставить во взаимно-однозначное соответствие че-
тыре типа распознающих устройств. Простейшим из них является класс так называе-
мых конечных автоматов, которые допускают (распознают) все языки, порождаемые
автоматными (регулярными) грамматиками, и только их.
Введем понятие детерминированного конечного автомата.
Детерминированным конечным автоматом называют следующую пятерку:
А = (X, Q, δ, q
0
, F),
где X = {x
1
, ..., x
m
} – входной алфавит (конечное множество входных сигналов);
Q = {q
0
, q
1
, ..., q
n-1
} – алфавит состояний автомата (конечное множество символов);
δ – функция переходов;
q
0
∈ Q – начальное состояние автомата;
F ⊆ Q – множество состояний, называемых заключительными.
На содержательном уровне функционирование конечного автомата можно
представить следующим образом. Имеется бесконечная лента с ячейками, в каждой

Страницы