35. Автоматы и формальные языки. Классификация формальных языков и автоматов. Концепция порождения и распознавания
жүктеу/скачать 280.89 Kb.
|
- Бұл бет үшін навигация:
- 36. Определение абстрактного автомата и методы их задания. Эквивалентность автоматов.
- 37. Автоматы Мили и Мура
- 38. Гонки. Противогоночное кодирование
- 39. Сложность логической схемы. Способы эффективного кодирования
- 40. Абстрактный синтез конечных автоматов. Минимизация и детерминация конечных автоматов.
- 41. Структурный автомат. Канонический метод структурного синтеза автоматов. Этапы синтеза.
- 42. Память структурного автомата. Элементы памяти. Триггеры
35. Автоматы и формальные языки. Классификация формальных языков и автоматов. Концепция порождения и распознавания.Автоматом называется формальная система имеющая входной и выходной каналы данных и находящийся в каждый дискретный момент времени в одном из конечного числа состояний. Концепция порождения и распознавания. Автомат-распознаватель – это автомат, который он рассматривает как устройство, которое может отличать конечные последовательности входных данных с помощью своих состояний (концепция распознавания, компиляторы). Порождающий автомат - это абстракция автомата, при которой он рассматривается как устройство, порождающее последовательность сообщений на выходе при переходе из одного состояния в другое(АЦП). Автомат-преобразователь - это абстрактный автомат, при котором он рассматривается как устройство преобразующее последовательность входных сообщений в последовательность выходных сообщений, при этом автомат изменяет свое состояние. (переводчики, трансформаторы, поисковые системы). Формальный язык – под формальным языком L(A) понимается произвольное подмножество множества универсум от этого алфавита. L(A) Í A*. Знак – элемент конечного множества различимых элементов. Алфавит – упорядоченное множество знаков (конечное). Порядок важен. С помощью порядка задается лексикографический порядок. Символ – знак вместе с сопоставленным ему смыслом. Строка (цепочка) – последовательность знаков некоторого алфавита, которая рассматривается как нечто целое (характеризуется длиной). Множество A* - множество всех конечных строк в алфавите A. Формальной грамматикой G называется алгебраическая система G = < Vт, Vn, P, S> , где Vт - алфавит терминальных знаков (основных), Vn - алфавит нетерминальных знаков (вспомогательных), (изначально предполагается, что Vт Ç Vn =Æ); P - множество продукций (где правило вывода имеет вид P = {a®b, a, bÎ (Vт È Vn)*}, S - аксиома грамматики (начальный символ), S Î Vn, нетерминальный всегда. Формальным языком L, порожденным формальной грамматикой G , L(G), называется всевозможные строки в терминальном алфавите, которые могут быть выведены из аксиомы грамматики: L(G)={ a/a Î Vт* , SÞ a} Две грамматики почти эквивалентны, если порожденные ими языки различаются не более чем пустой строкой.
1) Грамматика типа 0 (произвольная), имеет особенность, что на всю продукцию(правила вывода) этой грамматики не накладывается никаких ограничений, каждая грамматика типа 0 может быть реализована в виде Машины Тьюринга. 2.) Грамматика типа 1 (неукорачивающая). Если каждое правило из множества Р имеет следующий вид: a ® b, a, bÎ (VтÈ Vn)+ ; и длина |a|<= |b |, выводится слово не короче предыдущего. Грамматика G называется контекстно- зависимой, если каждое правило имеет вид: а) a ® b; a = mАw, b = mJw, ; A Î Vn. ; JÎ (VтÈ Vn)+ ; m, w Î (VтÈ Vn)* -левые и правые контексты; Грамматику типа 1 можно определить как контекстно зависимую и неукорачивающую (стек, автомат с линейной ограниченной памятью ). 3) Грамматика типа 2 (контекстно-свободная), продукции которой имеют вид : (Магазинный автомат) А® b , AÎ Vn , b Î (VтÈ Vn)* Грамматика называется укорачивающая если , существует правило: А® b , AÎ Vn , b Î (VтÈ Vn)+ 4) Грамматика типа 3 (регулярная) : это грамматика, продукции которой имеют вид : (РФ, КА) а) А® t | tB – правосторонняя; б) А® t| Bt – левосторонняя; где t Î Vт ; A ,B Î Vn Регулярная грамматика соответствует конечному автомату. A Î Vn, a Î Vт; A®t; A®tB - левосторонний вывод, A®Bt - правосторонний вывод. Формальные языки классифицируются по типу грамматики, которая их порождает, то есть язык, порожденный грамматикой типа 0, называется языком типа 0. Язык, порожденный грамматикой типа 1, называется языком типа 1. Язык, порожденный грамматикой типа 2, называется языком типа 2. Язык, порожденный грамматикой типа 3, называется языком типа 3. Конечный автомат — абстрактный автомат, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Конечные автоматы подразделяются на детерминированные и недетерминированные. Детерминированный конечный автомат Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором нет дуг с меткой ε(предложение, не содержащее ни одного символа), и из любого состояния по любому символу возможен переход в точности в одно состояние. Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат (два конечных автомата называют эквивалентными, если их языки совпадают). Конечный автомат является детерминированным, если для любого состояния q и любого символа a in  ,  содержит не более одного элемента.
Конечный автомат является недетерминированным, если не является детерминированным. 36. Определение абстрактного автомата и методы их задания. Эквивалентность автоматов.Абстрактный автомат— математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного языка, на выходе оно выдаёт символы (в общем случае) другого языка. 
Математической моделью дискретного управляющего устройства является абстрактный автомат, который задается множеством из шести Элементов: S = {A, Z, W, гдеА = {а1 ,..., аm ,..., аM} - множество состояний (алфавит1 состояний);
Автомат, заданный функцией выходов, называется автоматом первого рода; автомат, заданный сдвинутой функцией выходов,— автоматом второго рода. Автомат называется конечным, если конечны множества А, Z, W . Абстрактный автомат называется конечным, если конечны множества его внутренних состояний, а также множества значений входных и выходных сигналов. Конечный автомат в графическом представлении это направленный граф, имеющий один начальный и один или несколько конечных узлов. Абстрактный автомат работает как преобразователь слов входного алфавита в слова в выходном алфавите. Детерминированный конечный автомат(ДКА)- это такой конечный автомат, ни один узел которого не имеет одинаково помеченных дуг, соединяющих его с другими узлами автомата. НКА- это автомат, в кот есть хотя бы один узел с исходящими из него дугами, помеченными одинаковыми символами. Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами: Существуют переходы, помеченные пустой цепочкой ε. Из одного состояния выходит несколько переходов, помеченных одним и тем же символом. В дальнейшем будут рассматриваться только конечные автоматы, наибольшее распространение получили автоматы Мили и Мура. Конечным детерминированным автоматом типа Мили называется совокупность пяти объектов (Отображения δ и λ получили названия, соответственно функции переходов и функции выходов автомата A).Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата. Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов: а) А а | aB – правосторонняя; б) А а | Bа – левосторонняя; где a V ; A ,B W Регулярные языки – это языки, порожденные регулярными грамматиками. Регулярная грамматика соответствует конечному автомату. Теорема 3.3. Для любого непустого языка L порождаемого регулярной грамматикой G3, существует КА К, возможно недетерминированный, представляющий ( порождающий и распознающий) язык L. Конечным автоматом называется формальная система К которая задается 5-ю объектами К= Алгоритм Мили: (построение классов эквивалентности): Шаг1: Разбиваем множество состояний Q некоторого автомата K= Автоматом Мура называется конечный автомат, у которого функции выхода не зависят от входного знака (зависит только от состояния автомата).K= Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС). Основное преимущество использования автомата Мили заключается в возможности реакции автомата в течение текущего такта, что обусловлено зависимостью текущей выходной комбинации от текущей входной комбинации Наличие минимальной выходной задержки, связанной с переключением выходного регистра, отсутствие нестабильности переходного процесса на выходе автомата, отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата, простота описания на языках описания аппаратуры HDL делает автомат Мура практически незаменимым. Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании (например, для решения задачи об "Умном муравье" [1]). Табличный способ задания автомата Мили Автомат Мили может быть задан таблицей переходов и таблицей выходов. В таблице переходов АА Мили на пересечении столбца  и строки  записывается состояние  , которое есть функция  от и
В таблице выходов на пересечении столбца и строки записывается выходной сигнал, который есть функция  от и .
Пример: Задание автомата Мили табличным способом (автомат имеет два входных сигнала, два выходных сигнала и три состояния).
[править]Графический способ задания автомата Мили На рисунке приведен граф автомата Мили на 3 состояния, имеющий 2 входных сигнала и 2 выходных сигнала (см. предыдущий пример). 
[править]Табличный способ задания автомата Мура В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала. Поэтому достаточно для задания автомата Мура в таблице переходов добавить одну строку.
Графический способ задания автомата Мура На рисунке приведен граф автомата Мура на 5 состояний, имеющий 2 входных сигнала и 2 выходных сигнала.
Состоянию автомата сопоставляется совокупное состояние автоматов, называемых элементами памяти. Каждый из таких автоматов может находиться в одном из двух состояний, обозначаемые как 1 и 0. Тогда каждому состоянию автомата будет сопоставлен двоичный вектор состояний элементов памяти, и это сопоставление называют кодированием состояний. Таким образом, структурный автомат представляется в виде композиции комбинационной (логической) схемы и элементов памяти, связанных со схемой, как показано на рис. Входными переменными схемы являются входные переменные автомата - сигналы x1,x2, …,xn, и переменныеt1,n2,…,tk, определяющие текущее состояние автомата, выходные переменные реализуются на выходахy1,y2,…,ym. Выходы схемыv1,v2,…,vk определяют переход автомата в следующее состояние. Все переменные, приведенные на рис. – двоичные, то есть принимают значение из множества {0,1}. Переход от абстрактного автомата к структурному осуществляется через процедуру кодирования входов, выходов и состояний абстрактного автомата. Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания, или гонки. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное законом функционирования. Гонки в автомате связаны с разбросом во временных параметрах сигналов, проходящих через логические и запоминающие элементы, и имеют место в любой реальной логической схеме. Для обеспечения заданного закона функционирования автомата необходимо исключить возможность появления критических гонок.
При соседнем кодировании состояний автомата условие отсутствия гонок (и состязаний вообще) всегда выполнено. Требования к графу автомата: 1. В графе автомата не существует циклов с нечетным числом вершин. 2. Два соседних состояния второго порядка (путь между ними состоит из двух ребер, независимо от направления) не должны иметь более двух состояний, лежащих между ними.
Две пары (α, β) и (γ, δ) бинарных кодов наз. развязными, если существует координата №j такая, что αi = βi, γi = δi и αi ≠ γi. В автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых двух переходов (am, as) и (ak, al) (таких, что as ≠ al), происходящих под действием одного и того же входного сигнала, соответствующие пары кодов состояний развязаны. Качество кодирования: k = W/p, где W = число состояний элементов памяти на всех переходах p = число переходов (без учета петель) При соседнем кодировании K=1. Если I – длина кода, то 1 ≤ k ≤ I (так как 1 ≤ Wms ≤ I и в сумме для расчета W всего p слагаемых).
Анализ канонического метода структурного синтеза автомата показывает, что различные варианты кодирования состояний автомата приводят к различным выражениям функций возбуждения памяти и функций выходов, в результате чего сложность комбинационной схемы существенно зависит от выбранного кодирования. Среди множества существующих алгоритмов кодирования рассмотрим лишь два наиболее часто встречаемых: 1) алгоритм кодирования для D-триггеров; 2) эвристический алгоритм кодирования. Алгоритм кодирования для D-триггеров. Согласно рассматриваемому алгоритму при кодировании необходимо выполнить следующее: 1. Каждому состоянию автомата аm (m = 1,2,...,M) ставится в соответствие целое число Nm, равное числу переходов в состояние аm (Nm равно числу появлений аm в поле таблицы переходов или числу дуг, входящих в аm при графическом способе задания автомата). 2. Числа N1, N2, ..., Nm упорядочиваются по убыванию. 3. Состояние аs с наибольшим Ns кодируется кодом: , где R-количество элементов памяти. 4. Следующие R состояний согласно списка пункта 2 кодируются кодами, содержащими только одну 1: 00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00. 5. Для оставшихся состояний опять в порядке списка п.2. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния. В результате получается такое кодирование, при котором чем больше имеется переходов в некоторое состояние, тем меньше единиц в его коде. Т.к. для D-триггеров функции возбуждения однозначно определяются кодом состояния перехода, то очевидно, что выражения для функций возбуждения будут проще. Этот метод особенно эффективен при отсутствии минимизации функций возбуждения, что имеет место в реальных автоматах с большим количеством внутренних состояний и входных переменных. Эвристический алгоритм кодирования. Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе T, RS, JK-триггеров. Для данных типов триггеров (в отличие от D-триггеров!) на каждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата. Коэффициент эффективности кодирования: Рассмотренный алгоритм кодирования является машино-ориентированным, существуют программы, реализующие этот алгоритм. Необходимо отметить в заключении, что использование алгоритма кодирования для D-триггеров или эвристического алгоритма для других типов триггеров обеспечивает наиболее простую с точки зрения реализации схему, но при этом возможны гонки. Для радикального устранения последних используют аппаратные методы — триггеры с двойной памятью: триггеры, управляемые фронтом и т.д. 40. Абстрактный синтез конечных автоматов. Минимизация и детерминация конечных автоматов.Конечным автоматом называется формальная система К которая задается 5-ю объектами К= 1). КА - это модель дискретного преобразователя данных. 2). КА функционирует во времени. 3). Возможно различное соединение автоматов. Эквивалентным преобразованием называется переход от автомата K к автомату K' который неотличим от исходного. Постановка задачи минимизации : среди автоматов неотличимых от автомата K найти автомат Ko с наименьшим числом состояний. Абстрактный синтез автоматов- это представление автомата в отдельных блоков функционирующих как одно целое. Например Микропроцессор можно представить как устройство состоящее из отдельных блоков, таких как: АЛУ, очередь комманд, регистровый файл и т.д. это и есть абстрак. синтез, но если Микропроц. представлять как схему из логических элементов то это уже структурный синтез.(не путать!) Теорема : Для любого автомата K существует эквивалентный ему минимальный автомат Ko с точностью до изоморфизма , имеющий L состояний , если множество состояний Q разбивается на L классов эквивалентности. Теорема : ( детерминация КА). Для любого недетерминированного КАвтомата K=< A,Q,B,,> существует эквивалентный ему детерминированный К автомат K1=< A,Q,B,1,1> имеющий не более чем 2n состояний ( n=|Q| , |Q1|=2|Q| =2n). Замечание: 1). Заключительными состояниями детерминированного автомата являются все те состояния , подмножества состояний исходных автоматов, которых содержат заключительные состояния исходного автомата. 2). Может случиться так , что после перехода от источника к автомату- преобразователю он становится недетерминированным по входному знаку. Эта недетерминированность никак не связана с внутренней структурой автомата.
Каждое состояние абстракт автомата am (m=0,1,…M) кодируется в структурном автомате набором состояний элементов памяти: R≥]log2M[ ,где R-количество ЭП, ][- ближайшее целое сверху округление. Каждый входной сигнал абстрактного автомата af (f=0,1,…F) кодируется набором состояний входных сигналов автомата, т.к. каждый из каналов может принимать два значения, то: L≥]log2F[. Число выходных сигналов N: N≥]log2G[ , где G- число выходных сигналов абстрактного автомата. На этапе структурного синтеза предварительно выбираются элементарные автоматы, из которых путем их композиции строится структурная схема полученного на этапе абстрактного синтеза автомата Мили, Мура или С-автомата. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна. В настоящее время для решения основной задачи структурного синтеза применяется так называемый канонический метод структурного синтеза, при котором используются элементарные автоматы некоторого специального вида: 1) автоматы с памятью, имеющие более одного состояния (элементов памяти), 2) автоматы без памяти- с одним состоянием (комбинационных или логических элементов) Теорема о структурной полноте: Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую -либо функционально полную систему логических элементов, является структурно полной. Тогда задача структурного синтеза произвольных автоматов сводится к задаче синтеза комбинационных схем. Результатом канонического метода структурного синтеза является система синтеза логических уравнений, выражающая зависимость выходных сигналов автомата и сигналов, подаваемых на входы запоминающих элементов, от сигналов приходящих на вход всего автомата в целом, и сигналов, снимаемых с выхода элементов памяти. Эти уравнения называются каноническими. Для правильной работы схем, очевидно нельзя разрешать, чтобы сигналы на входе запоминающих элементов непосредственно участвовали в образовании выходных сигналов.В связи с этим запоминающими элементами должны быть автоматы Мура. Таким образом, структурно полная система автоматов должна содержать хотя бы один автомат Мура. В то же время для синтеза любых автоматов с минимальным числом элементов памяти необходимо в качестве таких элементов выбрать автоматы Мура, имеющие полную систему переходов в полную систему выходов- так называемые полные автоматы. Канонический метод структурного синтеза предполагает представление структурной схемы в виде 2 частей: памяти и двух комбинационной системы В Канонический метод структурного синтеза автоматов. Комбинационная схема (КС) может иметь несколько выходов. При каноническом методе предполагается, что каждая выходная функция реализуется своей схемой, совокупность которых и даёт требуемую КС. Поэтому синтез сложной КС с n выходами заменяется синтезом n схем с одним выходом. Согласно каноническому методу синтез КС включает в себя ряд этапов.
Необходимо отметить, что подлежащая реализации булева функция F(X1,X2,...,Xm) может быть задана не на всех возможных наборах аргументов X1, X2, ..., Xm. На тех наборах, где функция неопределенна, её доопределяют так, чтобы в результате минимизации получить более простую МДНФ или МКНФ. При этом упростится и сама КС. Кроме того, довольно часто с целью получения ещё более простого представления функции МДНФ, полученная в п.2, представляется в так называемой скобочной форме, т.е. выносятся за скобки общие части импликант МДНФ. 42. Память структурного автомата. Элементы памяти. ТриггерыВ качестве элементов памяти цифровых автоматов обычно используют – триггеры. Триггер – это устройство, имеющее два устойчивых состояния(0,1), в которые он переходит под действием определённых входных сигналов. Обычно в триггерах выделяют два вида входных сигналов (и соответственно входов): информационные и синхросигналы. Информационные сигналы определяют новое состояние триггера и присутствуют в любых триггерах. Синхросигнал не является обязательным и вводится в триггерах с целью фиксации момента перехода триггера в новое состояние, задаваемое информационными входами. Обычно, при синтезе Цифровой Автомат(ЦА) используются триггеры с синхровходом. На синхровход триггера поступают тактирующие импульсы задающего генератора, синхронизирующего работу ЦА. Период следования импульсов соответствует одному такту автоматного времени ЦА. Триггер имеет два выхода прямой и инверсный. Состояние триггера определяется по прямому выходу. RS-триггер. Вход S(set) называется входом установки в единицу, вход R (reset) – входом установки в нуль.
На основании таблицы можно получить функцию возбуждения памяти автомата при синтезе на базе RS-триггеров. Например, если автомат переходит из состояния ai= 010 в состояние aj=110, то для обеспечения такого перехода функции возбуждения должны быть: для первого триггера при переходе из 0 в 1 R1 =0, S1 = 1; для второго триггера при переходе из 1 в 1 R2 =0, S2 = X; для третьего триггера при переходе из 0 в 0 R3 =X, S3= 0.
Таблица функций выходов и условное обозначение:
для первого триггера при переходе из 0 в 1 T1 = 1, для второго триггера при переходе из 1 в 1 T2 = 0, для третьего триггера при переходе из 0 в 0 T3 =0 . D-триггер.(элемент задержки).Имеет один информационный вход D и два выхода прямой и инверсный, и осуществляет задержку поступившего на его вход сигнала на один такт. Таблица функций выходов и условное обозначение:
для первого триггера при переходе из 0 в 1 D1 = 1, для второго триггера при переходе из 1 в 1 D2 = 1, для третьего триггера при переходе из 0 в 0 D3 =0 . JK-триггер. Имеет два информационных входа J и K и два выхода прямой и инверсный. Вход J – вход установки в 1, вход K – вход установки в 0, т.е. эти входы аналогичны соответствующим входам RS-триггера: J – соответствует S, K – соответствует R. Однако, в отличие от RS-триггера, входная комбинация J = 1, K= 1 не является запрещённой. Таблица функций выходов и условное обозначение:
для первого триггера при переходе из 0 в 1 J1 = 1, K1 = a2; для второго триггера при переходе из 1 в 1 J2 = a4, K2 = 0; для третьего триггера при переходе из 0 в 0 J3 = 0, K3 = a1. жүктеу/скачать 280.89 Kb. Достарыңызбен бөлісу:
|
, 
, а1}, 
А x Z в А (аs = 
А);
, где S, X и Y — конечные непустые множества, а δ и λ — отображения вида:
и 
со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:
где S, X, Y и δ — соответствуют определению автомата типа Мили, а μ является отображением вида: μ : S → Y,с зависимостью состояний и выходных сигналов во времени уравнением:
.Особенностью автомата Мура является то, что символ y(t) в выходном канале существует все время пока автомат находится в состоянии s(t).Автоматом Мура называется конечный автомат, у которого функции выхода не зависят от входного знака (зависит только от состояния автомата).
.
след за этапом абстрактного синтеза автоматов следует этап структурного синтеза, целью которого является построение схемы, реализующей автомат из элементов заданного типа. Если абстрактный автомат был лишь математической моделью, проектируемого устройства, то в структурном автомате учитывается структура входных и 
качестве элементов памяти используются триггеры. Триггер – это устройство, имеющее два устойчивых состояния(0,1), в которые он переходит под действием определённых входных сигналов. Обычно в триггерах выделяют два вида входных сигналов (и соответственно входов): информационные и синхросигналы. Информационные сигналы определяют новое состояние триггера и присутствуют в любых триггерах. Синхросигнал не является обязательным и вводится в триггерах с целью фиксации момента перехода триггера в новое состояние, задаваемое информационными входами. В соответствии с теоремой Глушкова задача синтеза структурного автоматата состоит в построении комбинационной части.