А.А. Ожиганов Теория автоматов. Учебное пособие - Санкт-Петербург: НИУ ИТМО, 2013. - 84 с. - экз.

Аннотация:

Целью данного учебного пособия является ознакомление студентов с методами синтеза цифровых автоматов. Приводятся сведения об абстрактных автоматах Мили и Мура. Рассматриваются табличный и графовый способы представления автоматов, вводится понятие реакции автомата на входное слово и определение эквивалентных автоматов. Представлены методы взаимного эквивалентного преобразования автоматов. Приводятся общие сведения о микропрограммном управлении, понятия микрокоманды, микрооперации, микропрограммы, способы представления микропрограмм в виде граф-схем алгоритмов (ГСА), формул переходов, матричных и логических схем алгоритмов. Приводятся методы разметки ГСА и правила построения по ним автоматов Мили и Мура. Рассматриваются методы канонического синтеза структурных автоматов. Приводятся примеры синтеза памяти структурного автомата на базе D -, Т -, RS - и JK триггеров.

Описание:

Пособие предназначено для студентов, специализирующихся в области информационных технологий и может быть использовано при подготовке бакалавров и магистров по направлениям 230100 «Информатика и вычислительная техника», 231000 «Программная инженерия» и инженеров по специальности 230101 «Вычислительные машины, комплексы, системы и сети».

Министерство образования Российской Федерации Нижегородский государственный университет им. Н.И. Лобачевского

Факультет вычислительной математики и кибернетики

Учебно-методическая разработка для самостоятельной работы студентов по курсу «Теория алгоритмов и математическая логика»

при изучении темы «Концепции конечного автомата и регулярного языка. Операции над регулярными языками»

Нижний Новгород 2000 г.

Методическая разработка предназначена для самостоятельной работы студентов специальности «Прикладная информатика» над материалом темы «Концепции конечного автомата и регулярного языка. Операции над регулярными языками», входящей в состав учебного курса «Теория алгоритмов и математическая логика». Вводятся понятие формального языка и действия над формальными языками, включая основные теоретико-множественные операции. Излагается концепция конечного автомата (в детерминированном и недетерминированном вариантах); регулярные языки представляют собой класс языков, распознаваемых конечными автоматами. Показывается, что операции, объединения, пересечения, дополнения, конкатенации и итерации не выводят из класса регулярных языков. Приводятся соответствующие алгоритмы синтеза конечных автоматов.

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

преподаватели кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ доцент, д.т.н. Коган Д.И. и ассистент Бабкина Т.С.

1. Понятие языка, примеры языков, операции над языками.

Алфавитом именуем произвольное непустое конечное множество символов; символы произвольного алфавита называем его буквами . В качестве примеров укажем русский алфавит (с включением или невключением в него знаков препинания), латинский алфавит, объединение указанных алфавитов, множество цифр десятичной или двоичной систем счисления. В общем виде алфавит определяем как совокупность А ={a 1 , a 2 , ..., a n }; в числе букв алфавита А может быть и специальный символ пробела (пустой буквы), этот символ обычно обозначается e (сокращение английского «empty» – пустой).

Словом в алфавите А называем произвольную конечную последовательность его букв; одна и та же буква в этой последовательности может встречаться многократно. Длиной слова α (обозначение l (α )) называем количество букв в этом слове. Специальным символом λ будем обозначать единственное слово, имеющее нулевую длину (пустое слово ); следует различать пустое слово и слово е , состоящее из одной пустой буквы; длина слова е (пробела) равна единице. В алфавите А ={a 1 , a 2 , ..., a n } можно записать n l различных слов длины l , где l =0, 1, 2, ... . Множество всех слов алфавита А будем обозначать А *. Специально отметим, что в совокупность А * входит и пустое слово. Мощность множества всех слов алфавита А счетна.

Если α и β – два произвольных слова в алфавите А , то αβ – результат приписывания справа слова β к слову α . Для любых слов α и β считаем, что

αλ= λα= α, αλβ= αβ.

Языком в алфавите А называем произвольное подмножество слов L из А * . Язык L именуем конечным , если в его составе конечное множество слов; язык L бесконечен , если в его составе бесконечное множество слов. Совокупности всех слов русского, всех слов английского языка представляют собой примеры конечных языков. Множество записей всех простых чисел в десятичной или двоичной системе счисления является бесконечным языком. Множество всех языков алфавита А имеет континуальную мощность.

Язык L в алфавите А называем универсальным , если L=А *. Язык L

называем пустым , если множество L пусто (L =).

Пусть L 1 и L 2 – языки в алфавите А . Через L 1 L 2 и L 1 ∩ L 2 будем

обозначать объединение и пересечение этих языков соответственно. Слово α принадлежит объединению двух языков, если оно принадлежит по меньшей мере одному из них; слово α принадлежит пересечению двух языков, если оно принадлежит как одному, так и другому языку. Пусть L – язык в алфавите А ; через L с будем обозначать дополнение этого языка. Язык L с образуют слова алфавита А , не входящие в состав языка L : L с =А *\L . Операции объединения, пересечения и дополнения – основные теоретико-множественные операции.

Пусть L 1 и L 2 – языки в алфавите А . Через L 1 \L 2 будем обозначать

разность языков L 1 и L 2 . Слово α из А * считается принадлежащим L 1 \L 2 тогда и только тогда, когда оно принадлежит языку L 1 , но не принадлежит языку L 2 . Очевидно, что операция разности представима через основные теоретико-

множественные операции: L 1 \L 2 =L 1 ∩ (L 2 )с .

Дополнительно введем несколько специальных операций над языками. Пусть L 1 и L 2 – языки в алфавите А . Через L 1 { L 2 обозначим язык,

определяемый следующим образом: слово α принадлежит языку L 1 { L 2 тогда и только тогда, когда это слово можно разбить на две последовательные части

(т.е. представить в виде α = α 1 α 2 ) так, что первая часть является словом языка L 1 , а вторая часть – словом языка L 2 . Операция { называется конкатенацией (сцепкой) языков. Знак { нередко будет опускаться, тогда конкатенация языков L 1 и L 2 записывается L 1 L 2 . Язык L 1 L 2 получается приписыванием к словам языка L 1 слов языка L 2 в качестве окончаний. Отметим, что если к произвольному слову γ приписать в качестве окончания пустое слово, то результатом будет слово γ . Если языки L 1 и L 2 конечны, причем в составе первого языка m слов, а в составе второго n слов, то язык L 1 L 2 состоит максимум из mn слов. Если один из языков L 1 , L 2 пуст, то L 1 L 2 – также пустой язык.

Введем операцию возведения языка в степень. Полагаем:

L 0 ={λ };

L1 = L;

L2 = LL; Ln +1 = Ln L, n=2, 3, ...;

таким образом, понятие степени L i языка L определено для любого i =0, 1, 2, 3,

L* =U Li .

i= 0

Введенную операцию именуем итерацией . Отметим, что пустое слово принадлежит итерации любого языка. Непустое слово α принадлежит итерации языка L тогда и только тогда, когда это слово можно разбить на некоторое количество последовательных частей (подслов) так, что каждая часть принадлежит языку L . Если язык L состоит из всех однобуквенных слов алфавита А , то итерацией этого языка является универсальный язык А *. Отметим, что для любого языка L имеет место (L *)*=L *.

На множестве языков иногда рассматривают и следующую одноместную операцию ()+ :

(L )+ =U L i .

i= 1

Языки L * и L + отличаются один от другого разве что пустым словом. Слово λ всегда принадлежит языку L *. Языку L + оно принадлежит тогда и только тогда, когда принадлежит языку L .

2. Концепции конечного автомата и регулярного языка.

В кибернетике автоматами называют технически или программно реализованные модули, предназначенные для переработки поступающей информации. Конечный автомат – это модуль, имеющий конечное число возможных состояний и функционирующий в дискретном времени. В данном пособии конечные автоматы изучаются как абстрактные алгоритмические устройства, предназначенные для обработки слов фиксированного входного алфавита. Считаем, что обработку произвольного слова α во входном алфавите А автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние; состояние, в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины l автомат работает l тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.

Формально конечный автомат К определяем как совокупность

К={ Q, A, q0 , g, F},

где Q ={q 0 , q 1 , q 2 , ..., q m } – множество состояний автомата; А ={а 1 , а 2 , ..., а n } – входной алфавит; q 0 – специально выделенное состояние автомата, именуемое начальным состоянием; g – функция переходов конечного автомата,

представляющая собой отображение типа Q xА → Q (если g (q i ,а j )=q k , то автомат из состояния q i под воздействием буквы а j должен перейти в состояние q k ); F – специально выделенное подмножество состояний автомата, которые мы условно будем именовать «хорошими», F Q .

состояние, в котором оказывается автомат К через t тактов работы над этим словом (здесь t =0, 1, 2, ..., р ):

qα (0) =q0 ;

q α (1) = g (q α (0), a i 1 )

q α (2) = g (q α (1), a i 2 )

q α (p ) = g (q α (p − 1), a i p )

Будем говорить, что слово α принимается автоматом К , если q α (р ) F .

Введем в рассмотрение язык L (К ): слово α принадлежит языку L (К ), если данное слово принимается автоматом К . Язык L (К ) именуем языком, распознаваемым данным конечным автоматом. Язык L назовем регулярным , если для него можно построить распознающий конечный автомат.

Конечный автомат удобно задавать диаграммой его переходов . Диаграмма представляет собой ориентированный граф, вершины которого одноименны состояниям автомата; дуга из вершины q i , в вершину q k с надписанной над ней буквой а j проводится тогда и только тогда, когда g (q i ,а j )=q k . В случае, когда переход из q i в q k осуществляется под воздействием любой из букв некоторого подмножества S , S А , все буквы этого подмножества подписываются над соответствующей дугой (вместо перечня всех букв допускается сокращенная запись «x S » или просто «S »). Если произвольное состояние q i входит в F , то данный факт на диаграмме отмечается жирным кружком, выделяющим вершину q i .

Очевидно, что любой конечный автомат полностью определяется своей диаграммой переходов. Далее под задачей построения конечного автомата, обладающего теми или иными свойствами, будет пониматься задача построения диаграммы его переходов.

На рис. 2.1 показана диаграмма автомата K 1 , работающего над словами алфавита A ={a,b,c }. Автомат имеет два состояния, q 0 и q 1 , причем «хорошим» является только состояние q 1 . Начав работу в состоянии q 0 , автомат под воздействием букв a, b из этого состояния не выходит; под воздействием буквы с реализуется переход в состояние q 1 ; любая далее поступающая буква оставляет автомат в том же состоянии. Таким образом, автомат K 1 распознает язык L 1 , состоящий из слов, имеющих в своем составе букву с . Данный язык является регулярным.

q0 q1

Приведем еще несколько примеров регулярных языков в том же алфавите: L 2 - множество слов, в которых буква а встречается четное число раз; L 3 - множество слов, начинающихся и заканчивающихся одинаковой буквой; L 4

Множество слов, содержащих подслово α =abbc ; L 5 - множество слов, при чтении которых слева направо разность между числом встреченных букв a и b никогда не превосходит 2. Диаграммы конечных автоматов K 2 - K 5 , распознающих языки L 2 – L 5 соответственно, представлены на рисунках 2.2 – 2.5. Информацию об обработанной части входного слова автомат “помнит” своим состоянием. Так, например, автомат K 5 , обработав некоторую часть входного слова, оказывается в состоянии q x , если в прочитанной им части входного слова число встреченных букв а превышает число встреченных букв b на x ; здесь x {-2, -1, 0, 1, 2}; автомат оказывается в состоянии q плох , если в некоторый момент работы автомата абсолютная величина разности между числом обработанных букв а и числом обработанных букв b превысила 2.

Состояние конечного автомата назовем поглощающим , если любая входная буква не выводит автомат из этого состояния. Поглощающее состояние назовем положительно поглощающим , если оно принадлежит F, и отрицательно поглощающим в противном случае. В автоматах K 1 и K 4 полижительно поглощающими являются состояния q 1 и q 4 соответственно, в автомате K 5 отрицательно поглощающим является состояние q плох .

Можно считать, что каждый автомат имеет не более одного положительно поглощающего и не более одного отрицательно поглощающего состояния (если положительно или отрицательно поглощающих состояний несколько, то они легко могут быть заменены одним). Обычно в диаграмме переходов отрицательно поглощающее состояние не изображается; если из некоторого состояния по некоторой букве переход не указан, то предполагается, что он ведет в отрицательно поглощающее состояние. Представленный на рисунке 2.6 конечный автомат распознает в алфавите А язык, состоящий из слов, в которые буква с входит ровно один раз. Этот автомат имеет 3 состояния, отрицательно поглощающее состояние q плох (в него автомат переходит из состояния q 1 по букве с ) в диаграмме не указано.

q0 q1

Введем алфавит B ={0, 1, 2, …, 9}, каждое слово в этом алфавите трактуем как целое неотрицательное число. Пусть L (p ) обозначает множество слов – записей в десятичной системе счисления всех целых неотрицательных чисел, кратных натуральной константе p ; будем считать, что языку L (p )

дополнительно принадлежит также пустое слово λ . Покажем, что L (p ) – регулярный язык. Распознающий L (p ) конечный автомат К (p ) можно построить следующим образом. Состояниями автомата считаем q 0 , q 1 , q 2 , q p –1 ; из произвольного состояния q i по цифре х , х {0, 1, 2, ... ,9}, автомат переходит в

Приводятся начальные сведения об абстрактных автоматах Мили и Мура. Даются возможные способы представления автоматов: теоретико-множественное, графовое, табличное и матричное, понятия реакции автомата и эквивалентных автоматов. Приводятся методы взаимного эквивалентного преобразования автоматов. Приводятся общие сведения о микропрограммном управлении, понятия микрокоманды, микрооперации, микропрограммы, способы представления микропрограмм в виде граф-схем алгоритмов (ГСА), формул переводов, матричных и логическим схем алгоритмов. Приводятся методы разметки ГСА и правила построения по ним автоматов Мили и Мура. Дается понятие совмещенного автомата и способы его представления. Рассматриваются методы канонического синтеза структурных автоматов. Приводятся примеры синтеза памяти структурного автомата на базе RS-, Т- и D-триггеров.

Основные понятия и определения.
Простейший преобразователь информации (рис. 1.1,а) отображает некоторое множество элементов информации X, поступающее на вход, в некоторое множество на выходе Y. Если множества X и Y являются конечными и дискретными, то есть преобразование осуществляется в дискретные моменты времени, то такие преобразователи информации называются конечными преобразователями. Элементы множеств X и Y в этом случае предварительно кодируют двоичными кодами и строят преобразование одного множества в другое.

Результат преобразования F: X → Y зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и от того, что происходило раньше, то есть от предыстории преобразования. Например, один и тот же вход - извинение соседа после того, как он вам наступил на ногу в переполненном автобусе - вызовет у вас одну реакцию в первый раз и совсем другую - в пятый раз.

Содержание
Титульная страница Выходные данные
Лекция 1. Основные понятия теории абстрактных автоматов
Лекция 2. Эквивалентные автоматы
Лекция 3. Способы описания работы дискретных устройств
Лекция 4. Построение абстрактных автоматов по граф-схеме микропрограммы
Лекция 5. Синтез структурного автомата
Лекция 6. Память структурного автомата
Лекция 7. Пример синтеза структурного автомата на триггерах
Лекция 8. Графический метод синтеза структурного автомата на триггерах.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в теорию автоматов, Князьков В.С., Волченская Т.В., 2016 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.

З А 79 Теория автоматов : методические указания к практическим занятиям для специальности 230101 / Т.З. Аралбаев, <...> В методических указаниях рассмотрены следующие вопросы: способы представления логических функций (ЛФ ); алгебраическое преобразование ЛФ ; методы минимизации Квайна и Мак-Класски, с помощью карт Карно ; формы задания конечных автоматов ; синтез комбинационных схем в базисе “И-НЕ ” (“ИЛИ-НЕ ”) на логических элементах серии К155 и К561. <...> Методические указания предназначены для организации практических занятий по курсу “Теория автоматов ” для студентов 2-го курса по специальности 230101 “Вычислительные машины, комплексы, системы и сети”. <...> Минимизация логических функций по картам Карно ……………………….. <...> 41 3 Введение Настоящие методические указания содержат материал для проведения практических занятий по одному из основных разделов дисциплины “Теория автоматов ” – “Логические основы цифровых автоматов ”. <...> 1.1 Табличная форма представления ЛФ Логическая функция наиболее наглядно представляется посредством таблицы истинности (ТИ) и карты Карно . <...> Таблица истинности - это таблица , в которой каждому двоичному набору значений аргументов xi (i = 1, n) ставится в соответствие значение функции Y = f (x1, x2,..., xi ,..., xn) на данном наборе. <...> Карта Карно представляет собой прямоугольную таблицу, содержащую n 2 клеток, причем каждая клетка находится на пересечении i - ой строки и j ого столбца, ai и аj являются составными элементами двоичного набора n – местной ЛФ. <...> 1) любая пара клеток, являющихся соседними по вертикали или горизонтали, а также любая пара клеток, расположенных симметрично карте по вертикали или горизонтали, соответствуют двоичным наборам , отличающимся значением лишь одной переменной (т.е. отличается в одном разряде); <...> 2) в клетках карты Карно указываются значения функции на соответствующем наборе; <...> 3) двоичные наборы аргументов, которыми отмечены строки, а также двоичные наборы аргументов, которыми отмечены столбцы <...>

Теория_автоматов.pdf

УДК 004.3(076.5) ББК 32.97я73 А 79 Рецензент: доктор технических наук, профессор А.М. Пищухин Аралбаев, Т.З А 79 Теория автоматов: методические указания к практическим занятиям для специальности 230101 / Т.З. Аралбаев, И.В. Жукалина. - Оренбург: ГОУ ОГУ, 2009. – 41 с. В методических указаниях рассмотрены следующие вопросы: способы представления логических функций (ЛФ); алгебраическое преобразование ЛФ; методы минимизации Квайна и Мак-Класски, с помощью карт Карно; формы задания конечных автоматов; синтез комбинационных схем в базисе “И-НЕ” (“ИЛИ-НЕ”) на логических элементах серии К155 и К561. Методические указания предназначены для организации практических занятий по курсу “Теория автоматов” для студентов 2-го курса по специальности 230101 “Вычислительные машины, комплексы, системы и сети”. ББК 32.97я73 © Аралбаев Т.З., 2009 © Жукалина И.В., 2009 © ГОУ ОГУ, 2009 2

Стр.2

Содержание Введение......................................................................................................................4 1 Практическое занятие №1. Способы представления логических функций……………………………….… 5 1.1 Табличная форма представления ЛФ ………………………………………….5 1.2 Аналитическая форма представления ЛФ …………………………………….8 2 Практическое занятие №2. Алгебраическое преобразования формул логических функций………….…..12 2.1 Законы булевой алгебры………………………………………………………12 2.2 Аксиомы и теоремы булевой алгебры………………………………………..12 3 Практическое занятие №3. Метод минимизации Квайна и Мак-Класски………….……………………….15 3.1 Нахождение всех простых импликант………………………………………..15 3.2 Построение таблицы покрытий матрицы Квайна……………………………16 3.3 Поиск минимального покрытия функции…………………………………….16 3.4 Получение минимальной формы ЛФ…………………………………………16 4 Практическое занятие №4. Минимизация логических функций по картам Карно ………………………..20 4.1 Построение минимальных ДНФ ……………………………………………...21 4.2 Построение минимальных КНФ ……………………………………………...22 4.3 Минимизация не полностью определенных ЛФ……………………………..23 5 Практическое занятие №5 Формы задания конечных автоматов…………………………………….……..25 6 Практическое занятие №6 Синтез комбинационных схем в базисе «И-НЕ» («ИЛИ-НЕ»)……….………30 7 Практическое занятие №7. Синтез комбинационных схем в базисе логических элементов серии К155 и К561………………………………………………………………………….……35 Список использованных источников......................................................................40 Приложение………………………………………………………………………...41 3

Стр.3

Введение Настоящие методические указания содержат материал для проведения практических занятий по одному из основных разделов дисциплины “Теория автоматов” – “Логические основы цифровых автоматов”. Целью занятий является практическое закрепление знаний о формах представления и методах преобразования логических функций, а также методике синтеза комбинационных схем. Каждое практическое занятие включает в себя постановку цели занятия, краткий теоретический материал по теме, характерные примеры, контрольные вопросы и упражнения для самостоятельной работы. До проведения занятия студент должен уяснить его цель и ответить на контрольные вопросы. Для самостоятельной подготовки к занятиям студентам рекомендуется литература, представленная в списке использованных источников. Во время занятия разбираются примеры и выполняются упражнения по вариантам. Контроль знаний проводится по результатам ответов на контрольные вопросы и выполнения упражнений. 4

Стр.4

1 Практическое занятие №1. Формы представления логических функций Существует несколько форм представления логических функций (ЛФ), используемых на различных этапах проектирования комбинационных схем, в частности: словесная, табличная, аналитическая, геометрическая, кубическая. Целью практического занятия является изучение табличной и аналитической форм представления ЛФ и алгоритмов перехода от табличного описания ЛФ к аналитическому описанию. 1.1 Табличная форма представления ЛФ Логическая функция наиболее наглядно представляется посредством таблицы истинности (ТИ) и карты Карно. Таблица истинности - это таблица, в которой каждому двоичному набору значений аргументов xi (i = 1, n) ставится в соответствие значение функции Y = f (x1, x2,..., xi ,..., xn) на данном наборе. В таблице 1.1 в качестве примера представлена ТИ функции для трех аргументов. Функция Y принимает значение 1 или 0 на каждом наборе. Если значение функции не определено, то в соответствующей позиции ТИ ставится прочерк. Таблица 1.1 – Таблица истинности логической функции N Х1 Х2 Х3 Y 0 0 0 0 1 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 1 7 1 1 1 1 Иногда используют списочную форму представления ТИ, в которой приводится список единичных и нулевых наборов. Так, рассматриваемая в примере функция в списочной форме может быть представлена в виде: Y = F Х Х Х) = ∨ (0 , 1, 3, 6 , 7) Y = ∧ (2 , 4 , 5) (0 1 , 2 , 3 1 5