- •1.Начальные языки описания цифровых автоматов. Язык регулярных
- •Начальные языки описания цифровых автоматов
- •2.Начальные языки описания цифровых автоматов. Граф - схемы
- •3.Начальные языки описания цифровых автоматов. Логические схемы
- •Логические схемы алгоритмов
- •4. Начальные языки описания цифровых автоматов. Матричные схемы
- •3.4. Матричные схемы алгоритмов
- •5. Начальные языки описания цифровых автоматов. Объединение гса
- •6. Автоматные языки описания цифровых автоматов. Таблицы переходов и
- •Тпв графа Мили
- •Тпв графа Мура
- •7. Автоматные языки описания цифровых автоматов. Графы переходов
- •10. Абстрактный автомат. Соединение двух автоматов: параллельное
- •20. Машина Тьюринга (мт)
- •Пример с использованием автомата с магазинной памятью
- •Виды автоматов с магазинной памятью
Теоретические вопросы по курсу «Теория автоматов»
1.Начальные языки описания цифровых автоматов. Язык регулярных
выражений алгебры событий
Начальные языки описания цифровых автоматов
В зависимости от способов задания функций переходов и выходов (d и l) в настоящее время выделяют два класса языков – начальные языки и автоматные языки. В начальных языках автомат описывается на поведенческом уровне, т.е. функции переходов и выходов обычно в явном виде не заданы. Поведение автомата описывается в терминах входных и выходных последовательностей, реализуемых операторов (отображений) или управляющих последовательностей сигналов, воздействующих на операционный автомат.
В автоматных языках поведение автомата задается путем явного задания функций переходов и выходов. Среди начальных языков следует выделить язык регулярных выражений алгебры событий, язык абстрактных схем алгоритмов и язык граф-схем аргоитмов. Но вначале пополним наши знания о видах, свойствах и характеристиках цифровых автоматов.
2.Начальные языки описания цифровых автоматов. Граф - схемы
алгоритмов (ГСА) цифровых автоматов.
4.2.1. Определение ГСА ГСА - это ориентированный связный граф, содержащий вершины четырех типов: Начальная вершина входов не имеет, начальная и операторная вершина имеют по одному выходу, условная вершина имеет два выхода (1,0), конечная вершина выходов не имеет. Граф должен удовлетворять следующим условиям: 1) Содержит конечное число вершин, каждая из которых принадлежит одному из перечисленных выше типов; 2) Имеет одну начальную и одну конечную вершину; 3) Входы и выходы вершин, соединяются друг с другом с помощью дуг, направленных от выхода ко входу; 4) Каждый выход соединен, только с одним входом; 5) Любой вход соединяется с одним выходом; 6) Для любой вершины графа существует, по крайне мере, один путь из этой вершины в конечную вершину; 7) Один из выходов условной вершины может соединятся с её входом, что недопустимо для операторной вершины; 8) Каждой условной вершине записывается один из элементов множества; x = (xl) l = {1,L}, называют его множеством логических условий, разрешается в различных, условных вершинах, записаны одинаковые элементы множества х; 9) В каждой операторной вершине записывается оператор или микрокоманда yt подмножество множества y = (yn) n = {1,N}, называют его подмножеством микроопераций. yt = (yt1,…,ytu,…,ytU), u = {1,U}; При U = 0 yt = 0; Разрешается запись в различных операторных вершинах одинаковых подмножеств множества микроопераций.
3.Начальные языки описания цифровых автоматов. Логические схемы
алгоритмов цифровых автоматов.
Логические схемы алгоритмов
В ряде случаев вместо ГСА используются логические схемы алгоритмов , представляющие алгоритм функционирования цифрового автомата в виде конечной строки. Эта строка содержит символы операторов, символы логических условий, а также верхние и нижние стрелки, которым приписаны натуральные числа (например, должны удовлетворять следующим условиям:
в строке может быть записан только один начальный оператор один конечный оператор
перед оператором и после оператора стрелок не должно быть;
вслед за каждым логическим условием всегда стоит верхняя стрелка;
не должно существовать двух нижних стрелок с одинаковыми цифрами;
для каждой верхней стрелки должна быть одна нижняя стрелка.
Рис. 12.33 (см. скан)
Рис. 12.84
для каждой нижней стрелки должна быть хотя бы одна верхняя стрелка
В ЛСА, как и в ГСА, операторы обозначают буквами с индексом, а логические условия — буквами х с индексом.
Рассмотрим ЛСА конкретного цифрового автомата: Эта ЛСА имеет начальный оператор конечный оператор четыре оператора три логических условия Эквивалентная ГСА представлена рис. 12.34. Алгоритмперехода от ЛСА к ГСА очевиден. Соответствующая ГСА имеет начальную и одну конечную вершины, а число ее операторных вершин равно числу операторов в Выход начальной вершины ГСА соединяется дугой со входом вершины, соответствующей в ЛСА ближайшему справа от оператору или логическому условию. Аналогичным образом в ГСА проводятся дуги из операторных вершин. Единичный выход условной вершины соединяется со входом вершины, расположенной в ЛСА справа от Если после логического условия в ЛСА стоит верхняя стрелка то нулевой выход условной вершины соединяется со входом вершины, соответствующей в ЛСА оператору или логическому условию, перед которым стоит стрелка Для реализации безусловного перехода достаточно вместо условия использовать константу читаются слева направо и используются в тех случаях, когда нужна компактная вапись алгоритма (например, при машинной обработке). Следует отметить, что возможен переход от ГСА к ЛСА, однако он более сложен и используется редко.
http://stu.scask.ru/book_pta.php?id=78