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

Кутыркин, А.Ю. Бушуев11(11-ый шаг) xx;ak(12-ый шаг) m : m 1 ;(13-ый шаг) если z 0 перейти к 4-ому шагу;(14-ый шаг) вывод слова xA и завершение алгоритма.►a, b – алфавит из примера 2.2 и N BB ( y ) 14 – номер слова y B ,Пример 2.4. Если Bто, согласно алгоритму примера 2.3, получаем: y bbb , что соответствует примеру 1.2.►Упражнение 2.2.

Пусть B0, 1– алфавит размера 2 , где 0 и 1 – специальные«жирные» знаки, отличные от натуральных чисел нуля 0 и единицы 1. Для словаформального языка L {1x : x B } написать формулу вычисления номера этого словаBв натуральном словаре Dc ( L) , используя номера букв алфавита B , составляющих этослово ( L – язык двоичного представлении натуральных чисел из совокупности).BЗатем, создать алгоритм вычисления слова по его номеру в натуральном словаре Dc ( L).►УпражнениеL {ax:aДля2.3.A, aa1, xзаданногословаформальногоA -языкаA } написать формулу вычисления номера этого слова вAнатуральном словаре Dc ( L) , используя номера букв алфавита A , составляющих этослово ( L – язык k -ичного представлении натуральных чисел из совокупности). Затем,Aсоздать алгоритм вычисления слова по его номеру в натуральном словаре Dc ( L) .►Упражнение 2.4.

Пусть в алфавите A заданы два непустых слов x и y , имеющие номераm и n , соответственно, в натуральном словаре Dc A ( A ) . Используя длины | x | и | y |этих слов, найти номер слова xУпражнение 2.5. Пусть B/{m / n : m,n},гдеy в натуральном словаре Dc A ( A ) .►, ,/– алфавит для языка рациональных дробей( )Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуеви.Длязаданной12неотрицательной (отрицательной) рациональной дроби x m / nBN ( x) в натуральном словаре Dc B (//вычислить её номер/ ) .►Определение 2.1. Два натуральных числа m и n , одно из которых ненулевое, называютсявзаимно простыми, если НОД (m, n) 1 . Ненулевое натуральное число называетсяпростым, если оно не является единицей и делится нацело только на себя само иединицу.►Пример 2.5. Алгоритм Евклида для вычисления наибольшего общего делителя НОД (k , n)двух натуральных чисел k и n , одно из которых ненулевое, имеет следующийпоследовательно пошаговый вид:(1-ый шаг) x1 : min(k , n) (вычисление минимального из двух чисел);(2-ой шаг) x2 : max(k , n) (вычисление максимального из двух чисел);(3-ий шаг) x3 : min(k , n) ;(4-ый шаг) если x10 , то переходим к 9-ому шагу;(5-ый шаг) x1 : min( x2x3 , x3 ) ;(6-ой шаг) x2 : max( x2x3 , x3 ) ;(7-ой шаг) x3 : x1 ;(8-ой шаг) переход к 4-ому шагу;(9-ый шаг) вывод " НОД (k , n) " x2 и завершение алгоритма.►Упражнение 2.6.

Используя алгоритм Евклида найти НОД (90,36) .►Замечание 2.3.а) Согласно результату упражнения 2.5, язык рациональных дробей допускает построениеBего в виде словаря Dc (/) .Однако, этот словарь не является словарём рациональныхчисел, поскольку каждое рациональное число представляется бесконечным словарёмрациональных дробей, в частности, словарь дробей0/ n:nопределяет однорациональное число («нулевое»). Для того чтобы избежать такой неоднозначности впредставлениирациональныхчисел,вкачествеОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю.

Бушуевединственногопредставителя13рационального числа следует выбирать только несократимые рациональные дроби. В этомслучае совокупность рациональных чисел{m / n: НОД (m, n) 1} ,/гдепредставима в виде совокупностикаждоерациональноечислопредставленоединственной несократимой дробью. Алгоритм Евклида, приведённый в примере 2.5,Bпозволяет выделить из натурального словаря Dc (/)натуральный словарь Dc B ( )рациональных чисел. При таком выделении необходимо при развёртывании словаряDc B (/)в словарь Dc B ( ) отбирать только несократимые рациональные дроби. Такимобразом, для языка рациональных чисел возможно построение его словаря.б) В математике рациональноё число m /1отождествляется с целым числом mчастности, при таком отождествлениивысказывание.В.

Таким образом, справедливо0 /1 0.►Для непустого формальногоA -языка Lмогут создаваться словари, неAобязательно являющиеся натуральными. В этом случае для такого словаря, как правило,может использоваться обозначение Dc ( L) или Dcn ( L) , где nномера слова xL в таком словаре будет использоваться символ N Dc ( L ) ( x) .Пусть k , mВведёмдваL U V{uслову x u i. Кроме того, для, Uu1,..., u kсловаряи VDc1 ( L)v1,..., v mи– два словаря формальных языков.Dc2 ( L)дляформальногоязыкаv : u U , v V } прямого произведения языков U и V . Для этого каждомуvjL , где i 1,..., k и j 1,..., m , в словаре Dc1 ( L) присвоим одномерныйномерN Dc1 ( L)( x) (i 1) m j .(2).В словаре Dc2 ( L) этому слову x L присвоим одномерный номерN Dc2 ( L)Если для слова x u i( x) ( j 1) m i .vj(3).L ввести символ c ij , то вместо словарей Dc1 ( L) и Dc2 ( L)для перечисления без повторов слов языка L можно использовать представление языка Lв виде матрицы C из k строк и m столбцов:Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев14c11...c1mCk,(cij ) m........(4)c1k ...cmkгде для так называемых немых индексов i и j указаны их пробеги ( i 1,..., k и j 1,..., m )и (i, j ) – двумерный номер слова x u iL , согласно матрице C . В этом случаеvjформула (2) отражает перечисление одномерных номеров компонент матрицы (4) построкам, когда после последней компоненты строки матрицы счёт продолжается сначальной компоненты следующей строки, если таковая имеется.

Формула (3) отражаетаналогичный счёт одномерных номеров компонент матрицы (4) по столбцам.Формула (2) может использоваться и в том случае, когда, как и ранее, словарьUu1,..., u kможетVконечен, но словарь Vиспользоваться,когдабесконечен. Аналогично, формула (3)vj : jсловарьUбесконечен,ui : iнословарьv1,..., v m конечен.Упражнение 2.7. Пусть задан номер nсловаuvLвсловареN Dc1 ( L)(u v) ( n N Dc( Dc2 ( L) )Dc1 ( L)2 ( L)(u v) ) неизвестногоформальногоязыкаL U V.Предполагается, что этот номер вычислен согласно формуле (2) ((3)). Такжепредполагается, что словари UVи Vu1,..., u kvj : j(Uиui : iv1,..., v m ) заданы.

Требуется написать алгоритм для вычисления номеров слов u и vв словарях U и V , соответственно.►ПустьX– словарь для непустого формального языкаxn : nРассмотрим формальный язык Lвести обозначения xixjXXX2xix j : i, jXA .. Если для i, jcij , то для перечисления без повторов слов языка L можноиспользовать представление языка L в виде матрицы C из бесконечного числа строк истолбцов:c11...c1m ...C.............c1k ...cmk ...(cij ) ,..............Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев(5)15где так называемые немые индексы i и j последовательно пробегают ряд натуральныхчисел.Упражнение 2.8. Для номеров i, jязыка LxiX2xsпоказать, что можно создать такой словарь Dc ( L), в котором формула для вычисления номера словаxt : s, tcij из матрицы (5) имеет вид: N Dc ( L ) (cij ) ((ixjj 2) (ij 1)) /2j .►3.

Элементы теории конечных графовДля наглядного представления конечных автоматов используются их диаграммы. Вобщем случае такие диаграммы порождены соответствующими графами, основныепонятия для которых изложены в настоящем разделе.3.1. Ориентированные графы. Деревья. Логические сетиПусть Vv1 ,..., vs– словарь конечного формального языка V и на нём определенобинарное отношениеV V V 2 , индуцирующее матрицу Mtrкомпонентами, для которой, если 1 i, js , то: m ji1, (vi , v j );0, (vi , v j ).(m ji ) ss с булевымиТогда пара (V , ) определяет конечный орграф Gr (V ; ) , в котором словарь V задаётсписок его вершин и бинарное отношениеR(V , ) {(u, v) V 2 : (u, v)V 2 определяет совокупность его дуг} .

В этом орграфе матрицаMtr(m ji ) ssназываетсяматрицей смежности вершин, поскольку полагается, что вершина v j V смежна(связана дугой) с вершиной viV , если m ji 1 . В этом случае говорят, что вершинаvi V является началом и вершина v j V концом дуги (vi , v j ) R(V , ) , которая исходитиз вершины viV и входит в вершину v j V .

Для наглядного представления орграфаиспользуют его рисунок в виде диаграммы орграфа, на которой вершины изображаются,как правило, кружочками, помеченными соответствующими словами языка V , и дуги –Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев16стрелками, связывающими соответствующие вершины. В упрощённой диаграмме орграфавершины-кружочки остаются пустыми.Рис.1Рис.2Пример 3.1. На рис. 1 (рис. 2) показана (упрощённая) диаграмма графа Gr (V ; ) сословарём вершин Vv1 , v2 , v3 , v4 , v5 , v6 и матрицей смежности0 1 1 0 0 00 0 0 1 0 0Mtr(m ji )66000010000100010011000.►000Если в вершину v V орграфа Gr (V ; ) входит ровно k дуг, то говорят, что еёпозитивная валентность val (v) k .

Если из вершины v V орграфа Gr (V ; ) исходитровноmдуг, то говорят, что её негативная валентностьval (v) m . Числоval (v) val (v) val (v) называется валентностью вершины v V . Если val (v) 0 , товершинуv Vназываютисточником,еслиval (v) 0–стоком,еслижеval (v) val (v) 0 – глухим источником.Список((u0 , u1 ), (u1, u 2 ),..., (uk 1, u k ))изkпоследовательных дуг орграфаGr (V ; ) называется его путём с началом в вершине u 0 V и окончанием в вершинеОглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев17u k V . Этот же путь будет обозначаться и списком вершин(u0 , u1, u 2 ,..., uk 1, u k ) , вкотором каждая непосредственно следующая вершина смежна с предыдущей. Числоk || || называется длиной этого пути. Если u0u k , то этот такой путь называетсяконтуром или циклом, в котором любая вершина может считаться начальной иликонечной. Если же в этом цикле все вершины u1, u 2 ,..., uk 1, u k попарно различны, тотакой цикл называется простым.

В частности, если k0 , то такой простой циклназывается петлёй. Путь, не являющийся циклом, при проходе которого нетповторяющихся вершин, называется простым путём, в противном случае – составнымпутём, в котором, в качестве его составляющей, обязательно содержится цикл.Определение 3.1 (ациклического орграфа). Орграф, в котором нет циклов, называетсяациклическим.►Орграф, диаграмма которого показана на рис.

1 не является ациклическим,поскольку содержит петлю. Кроме того, на этой диаграмме путь (u1, u 2 , u 4 , u 3 , u 2 , u 5 )является составным, т.к. содержит цикл (u 2 , u 4 , u 3 , u 2 ) .Определение 3.2 (дерева). Конечный ациклический орграф с одним источником, вкотором любая вершина, не являющаяся источником, имеет единичную позитивнуювалентность, называется деревом. Источник дерева называется его корнем, стоки –листьями.►Теорема 3.1. Если орграф является деревом, то для его двух различных вершин – либо нетсоединяющего их пути, либо такой путь единственен.►На рис. 3 показана упрощённая диаграмма орграфа-дерева.Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев18Рис.3Рис.4Определение 3.3 (логической сети). Пусть Gr (V ; ) – такой конечный ациклическийорграф с n не глухими источниками и одним стоком, в котором любые два путисоединяющиеся источники с его вершиной, не являющейся источником, имеютодинаковую длину. Тогда такой орграф называется логической сетью.►На рис. 4 показана упрощённая диаграмма логической сети с тремя источниками,которые, как и сток, отмечены особыми (двойными) стрелками.3.2. Неориентированные графы. Контактные сетиПусть в конечном орграфе Gr (V ; ) бинарное отношениеявляется антирефлексивным (для любой вершины v V ) и антисимметричным (если (u, v)( v, v ), то (v, u )).Следовательно, орграф Gr (V ; ) не имеет петель и две его вершины не могут бытьвзаимносмежными.ВэтомслучаеорграфGr (V ; ) ,определяетконечныйнеориентированный граф Gr (V ; ) , называемый, кроме того, разориентацией орграфаGr (V ; ) .

Граф Gr (V ; ) имеет тот же словарь вершин и его неориентированные рёбрасобранывсовокупностьнеориентированного графа{(u, v) V V : (u, v)R(V , ) {{u, v} {v, u}: (u, v)Gr (V ; )или (v, u)}.бинарное отношениеСледовательно,дляимеетвидV V} и симметричная матрица Mtrс нулями наглавной диагонали определяет неориентированное понятие смежности его вершин. ПоОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев19аналогии с орграфом Gr (V ; ) в графе Gr (V ; ) вводятся понятия путей и их длин, нопонятие смежности вершин теряет ориентацию. Поэтому для вершин графа вводитсятолько одно понятие (общей) валентности, но нельзя ввести позитивные и негативныевалентности.На рис. 5 показана упрощённая диаграмма орграфа, для которого на рис.