В.А. Кутыркин, А.Ю. Бушуев Элементы теории автоматов и формальных языков. (В.А. Кутыркин, А.Ю. - Бушуев Элементы теории автоматов и формальных языков. 2014), страница 4

6 приведенаупрощённая диаграмма его разориентации. На упрощённой диаграмме разориентацииособыми стрелками указаны источник и сток исходного орграфа.Рис.5Рис.6Определение 3.4 (контактной сети). Пусть граф Gr (V ; ) является разориентациейконечного ациклического орграфа с одним не глухим источником q V и одним стокомe V . Тогда граф Gr (V ; ) , в котором вершина q V является входом и вершина e V –выходом, называется контактной сетью. Для обозначения этой сети используетсявыражение: Gr (V ; | q, e) .►Нарис. 6показанаупрощённаядиаграммаконтактнойсети,полученнойразориентацией орграфа, упрощённая диаграмма которого приведена на рис. 5.

Надиаграмме контактной сети, показанной на рис. 6, вход и выход отмечены особыми(двойными) стрелками.3.3. Конечные мульти-орграфы. Язык конечного мульти-орграфаПусть задан алфавит Aa1,..., a kс совокупностью A его букв и словарь V конечногоформального языка V , на котором определён список бинарных отношений Aˆ (aˆ1 ,..., aˆ k ) ,индуцируемыхихматрицамию.ТогдаопределёнОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю.

Бушуевнаборизkорграфов20Gr (V ; Aˆ ) (Gr (V ; aˆ1 ),..., Gr (V ; aˆ k )) , называемый конечным мульти-орграфом. В этоммульти-орграфе V – словарь его вершин и R(V , Aˆ ) {uajсовокупность его ориентированных рёбер-дуг. Если aˆ jAˆ и uv : ( j 1, k | (u, v) aˆ j } –ajvR(V , Aˆ ) , тоu V – начало и v V конец этого ребра и, кроме того, вершина v V является aˆ j -смежной с вершиной u V . Следовательно, в отличие от обычного орграфа, вершинамульти-орграфа может иметь несколько типов смежности с другой вершиной или сама ссобой. Для наглядного представления мульти-орграфа, как и для обычного орграфа,используется его диаграмма. Для иллюстрации, на рис.7 показан пример диаграммыконечного мульти-орграфа. Как и для обычного орграфа, в мульти-орграфе Gr (V ; Aˆ )определяется путь с началом в вершине u0 V и концом в вершине u m V в виде набораего дугдлиной |b1(u0u1, u1b2u 2 ,..., umbmu m ) , где b1,..., bm1A .

Этот путь| m связывает вершину u0 V с вершиной u m V .В мульти-орграфе Gr (V ; Aˆ ) могут выделяться непустые совокупности V 0V1V иV начальных и заключительных его вершин, соответственно. В этом случае длятакого мульти-орграфа используется обозначение Gr (V ; Aˆ | V 0 , V1 ) , вершины v 0 V 0 иv1 V1 называются начальной и заключительной, соответственно. Кроме того, дляобозначения совокупности путей, связывающих его начальные и заключительныевершины, используется выражение(V0 ,V1 ) .Определение 3.5 (языка мульти-орграфа). Для совокупности путейорграфаGr (V ; Aˆ | V 0 ,V1 )универсальный(u0b1V1отображение: (V 0 , V1 )A*вA -язык A* следующим образом. Если u 0 V0 , u m V1 иu1, u1b2Формальный A -язык { (если V 0определеномульти-(V0 ,V1 )u 2 ,..., um):bm1(V 0 , V1 ) , тоum)(V 0 , V1 )}Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев) b1...bmA* .A* , дополненный пустым словом,, называется языком мульти-орграфа Grиспользуется обозначение Lng (Gr ) . Если((V0 ,V1 )Gr (V ; Aˆ ) и для него, то Lng (Gr ).►21Рис.7Рис.8Пример 3.2 (мульти-орграфа и его языка). На рис. 7 и рис. 8 показаны диаграммыорграфов Gr (V ; aˆ ) и Gr (V ; bˆ) , соответственно. Из этих орграфов образован мульти-орграфGr Gr (V ; aˆ , bˆ | 1 , 3, 4 ) ,диаграммакоторогоприведенанарис.

9.Входныеизаключительные вершины этого мульти-орграфа отмечены на диаграмме особыми(двойными) стрелками.Из анализа диаграммы мульти-орграфа Gr следует, что его язык Lng (Gr ) имеетвид:Lng (Gr ) {ab m a : mгде{j:j} {ab m ab : m0} , bmb...b для m} {bb} {b}иbm разРис.9Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев0a, b ,– пустое слово.►22Замечание 3.1 (об искусственных языках). Формальные языки, порождённые конечнымимульти-орграфами, относятся к типу искусственных языков, используемых в языкахпрограммирования.

Среди формальных языков искусственные языки образуют болееузкий класс. Основное требование к языкам этого узкого класса состоит в том, чтобы онибыли разрешимы, т.е. распознаваемы с помощью соответствующих алгоритмов. Такоетребование обусловлено тем, что тексты практических программ достаточно велики и,фактически, недоступны для проверки на их на корректность (синтаксическуюправильность) человеком.

Следовательно, анализ корректности текстов таких программдолжен осуществляться автоматически с помощью тех или иных алгоритмов,реализуемых на современных компьютерах.Следует отметить, что среди искусственных языков языки, порождённые мультиорграфами и названные регулярными, являются самыми простыми и используются длясоздания простейших конструкций языков программирования. Распознавания такихязыков происходит с помощью соответствующих автоматов, о которых будет рассказано впоследующих разделах.►4. Детерминированные и недетерминированные автоматыПусть A и B – два квази-алфавита, т.е. два неупорядоченных «алфавита», и V – словарь(конечного) формального языка V .

Кроме того, заданы отображениякотором квази-алфавитыVи( A, B,V , , ) определяет (конечный) автомат Мили, вB . Тогда пятерка:A V:A VA и B называются его алфавитами входа и выхода,соответственно, язык V – совокупностью его состояний, отображения:A VVиB – его функциями перехода по состояниям и выхода, соответственно. В этом:A Vслучае автомат Мили называют (конечным) детерминированным автоматом. Если жефункцияне определена для некоторых пар из совокупности A V или на некоторыхпарах этой совокупности – многозначна, то такой автоматназывается (конечным)недетерминированным автоматом.Автомат Мили:VB , что( a, v )называется автоматом Мура, если есть такое отображение( (a, v)) для любых aЕсли в автомате МилиAиv V.всего одно состояние, т.е.

| V | 1 , то автоматдискретным преобразователем.Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуевназывается23Автомат Мили, в котором алфавит входа состоит из единственной буквы,называется автономным автоматом Мили.Автомат Мили, в котором выделено одно состояние, с которого он всегданачинает работу, называется инициальным автоматом.Если алфавит выхода автомата (детерминированного или нет) состоит изединственной буквы, то такой автомат называется автоматом без выхода.В автомате Милифункциииможно рассматривать как бинарныемногосортные алгебраические бинарные операции с сигнатуройСледовательно, в этом случае для aи, соответственно.A и v V можно использовать обозначения:( a , v ) a v;(1)( a, v ) a v.Кроме того, для обозначения автомата Милиможно использовать выражение( A, B,V , , ) .В рамках обозначений (1) работу автомата Мили( A, B,V , , ) можно описатьследующим образом.

Эта работа осуществляется потактово. Если в начальный тактработы автоматнаходился в состоянии v(0) V и на его вход поступила буква b(0)то он переходит в состояние v(1)b(1) a(0) v(0) . Если автоматпоступила буква b(0)A,a(0) v(0) и на его выходе появляется буквана такте t находился в состоянии v(t ) V и на его входA , то он переходит в состояние v(t 1) a(t ) v(t ) и на его выходепоявляется буква b(t +1)= a(t)• v(t) . Такая потактовая работа автоматаописываетсяуравнениями:v (t 1) b(t) v (t);(2)b(t +1) b (t ) v (t ).Уравнения (2) называются каноническими уравнениями автоматаесли автомат.

Таким образом,в начале работы находился в состоянии v(0) V и на его входпоследовательно поступали буквы b(0), b(1),..., b(t 1)A , то он переходит в состояниеv(t ) V и на его выходе последовательно появляются буквы c(1),..., c(t ) B . Поэтомуфункции:AVи(операциии) можно расширить до отображений:AVV иB , полагая, что для слова x b(0)b(1)...b(t 1) A и состояния v v(0) Vсправедливы равенства:( x , v) x v v(t ) и( x , v) x v c(1)...c(t ) .

Такое определениеможно описать следующим индуктивным образом.Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев24Определение 4.1. В автомате Милисостояния v V и пустого слова( , v), по определению, полагается, что. Если для слова xv( x , v) x v и( A, B,V , , ) ( A, B,V , , ) для любого егоv v и( , v)и состояния v V уже определены значенияA( x , v) x v , то, по определению, для буквы a A полагается, что:( x a , v) ( x a) v( a,( x a , v) ( x a) v( x, v)) a ( x v);( x, v )Для определённых в (3) отображений:A(a,V( x, v)) ( x v) (a ( x v)).V и:A►(3)B (операцийVи)справедлив следующий результат, легко выводимый из соотношений (3).Теорема 4.1.

Для любого состояния v V автомата Милии слов x, y( A, B,V , , ) ( A, B,V , , )A справедливы равенства:(xy , v) ( xy) v( y,(xy , v) ( xy) v( x, v )( x, v))( y,y ( x v);( x, v)) ( x v) ( y ( x v)).►4.1. Способы задания конечных автоматов МилиДля использования в компьютерной практике автоматов необходимо предложить способыих задания, которые были бы удобны для их теоретического анализа и реализации накомпьютере.