Antik (1082243), страница 5
Текст из файла (страница 5)
Каждаядуга графа либо помечена символом алфавита А, либо непомечена.Источник определяет регулярный язык Q над алфавитом А,порождаемый множеством всех путей из начальных вершин вфинальные. Каждому такому пути соответствует слово, образованное символами алфавита А, являющихся пометками на дугахпути. Непомеченной (пустой) дуге соответствует пустой символ.Источник не содержит вершин, которые не достижимы из начальных, а также не содержит вершин, из которых недостижимыфинальные.В общем случае источник определяет регулярное множествослов в алфавите A×B (произведение алфавитов входного A и выходного B), при этом все вершины источника являются финальными.В источнике может быть нарушено условие однозначностиавтоматного графа, т.е.
из одной вершины могут выходить несколько дуг, помеченных одинаково, выходить непомеченные дуги, вообще не выходить дуг (только для финальных вершин), может быть более одной начальной вершины. Источник, у которогонарушено условие однозначности, называют также недетерминированным конечным автоматом.При выполнении вычислений синхронным автоматом можетсуществовать только один последовательный процесс, каждомушагу (такту) которого соответствует только одна вершина автоматного графа. В источнике можно, в общем случае, считать, что27так же существует один последовательный процесс, который влюбом такте может находиться более чем в одной вершине источника.
Источник всегда может быть преобразован(детерминизирован) в эквивалентный абстрактный автомат. Дляэтого все те вершины источника, которые в каком либо тактемогли быть использованы одновременно, сопоставляютсяединственному состоянию автомата. Это можно сделать, еслипроследить все возможные варианты развития процессов висточнике. Алгоритм детерминизации см. ниже п.п.7.3.Переход от недетерминированного автомата к соответствующему детерминированному автомату даёт увеличение числасостояний (верхняя граница 2n, где n – число состояний недетерминированного автомата), поэтому удобно использовать недетерминированные автоматы, поскольку для представления события эта модель требует меньшего числа состояния и с более понятной структурой.7.1.3. Катенация (конкатенация) языков L1 и L2 определяется как язык L1_L2 = { qd, где q слово из L1, d слово из L2 }.Катенация регулярных языков является регулярным языком.Пусть L = L1_L2, а Q1 и Q2 соответственно источники, представляющие эти языки.
Тогда источник Q, представляющий язык L,строится следующим образом: начальные вершины источника Qсовпадают с начальными вершинами источника Q1; финальныевершины источника Q совпадают с финальными вершинами источника Q2; все финальные вершины Q1 соединяются со всеминачальными вершинами Q2 (можно это сделать через одну новуювершину).Итерация (или катенативное замыкание) языка L являетсямножество L*, которому принадлежат все слова, являющиеся катенацией любого конечного числа слов из L, а также пустое слово.Итерация регулярного языка L является регулярным языком*L .
Если Q источник, представляющий язык L, то источник J,представляющий язык L*, строится следующим образом: все финальные вершины соединяются со всеми начальными вершинамидугами без меток, при этом все начальные и финальные вершины28остаются теми же. Поэтому начальные вершины становятся также и финальными, и в языке появляется пустое слово.7.1.4. Свойство быть регулярным множеством замкнуто относительно теоретико-множественных операций: объединения,пересечения, дополнения, разности, проекции, цилиндра.1) Объединение. Пусть R1 и R2 регулярные множества, тогдаобъединение R = R1∪R2 также является регулярным множеством.Если R1 и R2 представлены источниками, то источник, представляющий R, есть простое объединение этих источников такое,что множества начальных, финальных и промежуточных вершинявляются объединением соответствующих вершин исходных источников с сохранением всех дуг без изменений.Если R1 и R2 представлены инициальными автоматами с выходом B={0,1}, индикатором I={1}, то синхронная параллельнаякомпозиция этих автоматов с общим входом и объединением выходов по ИЛИ будет автоматом, представляющим искомый язык.2) Пересечение.
Если R1 и R2 регулярные множества, то пересечение этих множеств R = R1∩R2 также регулярное множество.Если R1 и R2 представлены инициальными автоматами с выходом B={0,1}, индикатором I={1}, то синхронная параллельнаякомпозиция этих автоматов с общим входом и объединением выходов по И будет автоматом, представляющим искомый язык.3) Дополнение. Если R язык над алфавитом А, то дополнениеR является языком из множества А* всех слов в алфавите А, непринадлежащих языку R. Если R регулярное множество, то Rтакже регулярное множество и может быть представлено автоматом с выходным алфавитом B={0,1}, индикатором I={1} и инверсным выходом.4) Разность двух множеств R = R1\R2 = R1∩ R 2.
Поэтому,если R1 и R2 регулярные множества, то регулярно также R= R1\R2.5) Проекция. Для каждого слова в алфавите Y×Z с символами yz∈Y×Z его Y–проекцией называются слова с символамиy∈Y, т.е. стирается «лишний» компонент. Если алфавит Y×Z былвходным алфавитом автомата, то будет нарушено условие авто-29матности графа, автомат становится недетерминированным.6) Цилиндр. Если задан язык L над алфавитом Y, то Zцилиндром языка называется язык над алфавитом Y×Z, Yпроекция которого принадлежат L. Если L регулярный язык, тоего любой цилиндр также регулярный язык.
Одним из «полезных» цилиндров является такой, в котором добавляемым компонентом является выходной алфавит автомата.7.1.6. Дефинитный (определенный) язык может быть представлен как катенация А*_D, где А – входной алфавит, D – конечное множество слов ограниченной длины. Этот язык являетсябесконечным языком из слов, заканчивающихся словами из D.Проектируя автомат, распознающий дефинитный язык,удобно сопоставить состояниям автомата все различные началараспознаваемых слов.
Переход при поступлении нового символаосуществлять в состояние, которое соответствует одному из начал, совпадающему с хвостом нового слова, если таких совпадений более одного, то выбирается самое длинное. Одно из состояний должно соответствовать пустому началу.
Будем его обозначать символом Λ.Пример 7.1.-1. Спроектировать автомат, который устанавливает на выходе 1, если на двухразрядном входе автомата в последних 3-х тактах перед появлением кода 11 (в 4-м такте) появился только один раз код 00.Введем, для удобства, следующие символы для обозначениякомбинаций сигналов на входе автомата:0011(01 или 10)(I или X)Æ OÆ IÆ XÆ HАвтомат должен распознать в последовательности символовследующие слова: OHHI, HOHI, HHOI. Этим словам соответствуют следующие различные начала: Λ, O, H, OH, HO, HH, OHH,HOH, HHO.
Для построения автомата Мили достаточно каждомуиз этих начал сопоставить свое состояние. Для построения автомата Мура надо добавить еще состояния, соответствующие сло-30вам: OHHI, HOHI, HHOI. Пусть имена состояний автомата совпадают с началами слов, им сопоставленным. Тогда автомат Муразадается следующей автоматной таблицей:сост.ΛOHOHHOHHOHHHOHHHOOHHIHOHIHHOIвых.000000000111OXIOOHOHHOHHOHHHHHOOHHOHHOHOHHOHHHOHHHHHHOHHOHHIHOOHHHOHIOHOHHHOIHHOHHHHHHOHHOHHIHOOHHHOHI7.2. Асинхронный язык.В асинхронный язык входят слова, в которых “длительность” любого из символов может быть произвольной. Точнее,если слово W принадлежит асинхронному языку, то в языке также содержатся все слова, полученные из W повторениями любыхбукв из W либо вычеркиванием из W некоторых повторений отдельных букв.Функция переходов автомата, определяющего асинхронныйязык, имеет следующую особенность: для любого состояния sвыполняется: если s:=g(z,a), то s:=g(s,a).
Автомат может перейтив другое состояние только при изменении входного символа.Назовем ядром асинхронного языка язык, в котором нет повторений символов. Асинхронный язык регулярен, если ядро этого языка – регулярное множество.В частности, если ядро – дефинитный язык, то при синтезеавтомата, распознающего асинхронный язык с таким ядром можно воспользоваться приемом из пункта 7.1.6.При реализации автоматов, распознающих асинхронный31язык, удобно использовать в кодах состояний коды входных символов, либо воспользоваться методом условной синхронизации(см.п.II.4), либо использовать то и другое.Пример 7.2.-1.
Спроектировать автомат с двухразряднымвходом (in1,in2) и одноразрядным выходом, который индицируетследующее событие: после нулей на обеих линиях по каждой излиний in1 и in2 прошло ровно по одному блоку единиц любойдлительности.Решение будем искать в виде симметричной композициидвух одинаковых автоматов см. п.7.1.4.i n1i n2syni1i2CAi1i2CA1 outРис.22. Композиция автоматовОбозначим возможные символы (сочетания значений сигналов) на входах автомата следующим образом:in1in200a10b01q11cЕсли удалить все повторения символов, то получим для одного из автоматов дефинитный язык со следующими минимальными последовательностями, приводящими к событию, котороедолжен распознать автомат:acaabqaabaqaacbaabcbaabcaabcqa(Другой автомат распознает последовательности, полученные из указанных заменой b на q, q на b.)32Так же как в примере 7.1.-1, состояниям автомата сопоставим все различные начала распознаваемых слов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
