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

При записи строки каждыйзаписываемый знак характеризуется своим местом в строке, можно сказать номером места(позиции) или просто – номером. Место начальной буквы имеет номером 1, номер местаследующей буквы, если таковая имеется, равен 2 и т.д. Длина слова определяется номеромпоследней буквы в слове.Дляобозначениястрокмогутиспользоватьсязнакиилидругиестроки,становящиеся символами.Особо выделяется пустая строка, не имеющая в своей записи ни одной буквы.

Длязаписи пустой строки используется символ.Определение 1.1. (знакового алфавита). Алфавит знаков – это строка, начальный(заключительный) знак которой равен( ), и между этими знаками (начальным изаключительным), последовательно, через знак запятой, перечислены попарно различныезнаки этого алфавита. Такой алфавит обязан содержать хотя бы один знак.►Пример 1.1 (знаковых алфавитов).а) a, b,, – алфавит из 3-х знаков;б) В алфавите a, _, b знак _ играет роль пробела.►Замечание 1.1 (об алфавитных знаках). Для обозначения алфавита используются дваждыподчёркиваемые знаки-символы. Если A – обозначение алфавита, то A – обозначениесовокупности знаков этого алфавита, в частности,знаков алфавита Aa, b, b, b, a – совокупность из двухa, b .

Алфавит устанавливает «старшинство» среди своих знаков.Самый младший – первый и т.д. Совокупность A знаков алфавита A будет называтьсяквази-алфавитом.►Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев7Определение 1.2 (формального языка). Пусть A – алфавит знаков. Тогда все строки, взаписи которых участвуют знаки только этого алфавита, образуют позитивный язык дляэтого алфавита. Такой позитивный язык обозначается символом A . Добавив к языку Aпустую строку, получим универсальный язык для этого алфавита, обозначаемый A* .

ЯзыкA* – совокупность всехA -строк. Любая подсовокупность универсального языканазывается формальным A -языком.►Большие тексты состоят из последовательной записи многих строк. Поэтому привведении формальных языков определяют особую операцию присоединения строк,называемую сцеплением или конкатенацией строк.Определение 1.3 (сцепления строк).

Пусть x и y – строки. Сцепить строку x со строкойy – это значит приписать к слову x справа слово y . Результат такого сцепленияобозначается выражением xПо определению, строкиy , гдеx и x– символ-знак сцепления (конкатенации) строк.совпадают со строкой x (Согласно такому определению aabbb– пустая строка).►aabbb .Замечание 1.2. Если x и y – строки, то ( xy ) результат сцепления x и y , совпадающийссцеплениярезультатомxy.ассоциативности, т.е. ( xДляy)операцииzx(yстроксправедливотождествоz ) .

Из этого тождества следует сочетательныйзакон сцепления строк. То есть скобки при сцеплении строк можно не указывать.►Определение 1.4 (буквенного алфавита и его слов). Список из попарно различныхнепустых строк, в записи которых не участвует знак запятой, может образовыватьбуквенный алфавит, где буквы – это строки из этого списка. Пустьсписок попарно различных букв (угловая скобкаy1,..., yn– такой– начало списка, скобка– егоокончание). Список y1 ,..., yn является буквенным алфавитом, если любое сцепление егобукв допускает однозначное побуквенное чтение. Следовательно, если u1 ,..., uk , v1 ,..., vmэто буквы этого списка и u1...

ukv1... vm , то km и u1v1 и u1v1 ,..., ukvm .Результат сцепления букв алфавита называется словом в этом алфавите.►Замечание 1.3. Как и для знаковых алфавитов, вследствие однозначности прочтения, длябуквенных алфавитов определяются соответствующие понятия универсальных иформальных языков.

Далее, поскольку алфавит знаков также можно рассматривать какбуквенный алфавит, для знаковых и буквенных алфавитов используется общий термин –алфавит.►Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев82.

Лексикографический порядок. Словари формальных языковНа протяжении настоящего раздела используется алфавит Aa1,..., a k , для которого A– символ совокупности его букв. Совокупность A будет называться квази-алфавитом,Aчисло N (ai ) i ( 1 i k ) номером буквы ai в алфавите A или A -номером этой буквы.Следовательно, далее | A | | A | k – размер этого алфавита.Для пустого слова, которое является пустой строкой, как и ранее, будетиспользоваться символ. Совокупность всех слов, включая пустое, записанных из буквалфавита A (совокупность A -слов), образует универсальный язык A , любой подъязыккоторого называется формальным A -языком.

В частности, если из универсального языкаA исключить пустое слово, то такой формальный A -язык называется позитивным A -языком и для него используется обозначение A .Если x и y – два слова, то выражение xсо словом y (aab _ bb– знак операции сцепления или конкатенации слов). Например,aab _ bb и xx.xДля универсального языка Aнатуральнымy обозначает результат сцепления слова xA -словарём.Aсоздаётся особый словарь Dc ( A ) , называемыйДлясозданиятакогословаряиспользуетсялексикографический A -порядок «старшинства» слов в языке A , индуцированный(наведённый) алфавитом A .

Если два A -слова имеют различные длины и | x | | y | , то,согласно такому порядку, слово y «старше» слова x . Если же их длины одинаковы и,кроме того, они имеют представление xb, cAA и N (c)bи yc, где, ,A ,AN (b) , то, в этом случае, слово y «старше» слова x .Упражнение 2.1. Доказать, что в формальном позитивном A -языке A количество словдлиной nравно | A |n .►Замечание 2.1. Из результатов упражнения 1.1 следует, что в универсальном A -языкеколичество слов, длина которых не превышает число n| A |0, конечно и равна числу| A |1 ... | A |n . Поэтому количество слов в универсальном A -языке, которые,Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев9согласно лексикографическому A -порядку, «младше» некоторого фиксированного слова,конечно. Кроме того, за этим фиксированным словом непосредственно следуетединственное слово, которое «старше» его в лексикографическом A -порядке.

Следуятакому лексикографическому«старшинству»,законечноечислошаговможно«добраться» до любого A -слова. Таким образом, согласно лексикографическому A порядку, все слова формального языка A можно расположить в натуральном A -словареADc ( A ) , согласно их «старщинству» (пустое слово – начальное слово этого словаря).►Пример 2.1. Пусть задан алфавит BBDc ( B ) имеет вид:Если LAa, b . Тогда начало натурального B -словаря, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb .►– непустой формальныйA -язык, то для него также создаётсяAнатуральный A -словарь Dc ( L) следующим образом.

Для этого при развёртыванииAсловаря Dc ( A ) из него последовательно вычёркиваются слова, не принадлежащиеAязыку L . В результате остаётся натуральный A -словарь Dc ( L) языка L . ВследствиеAпринципа математической индукции, каждое слово x L получает в словаре Dc ( L)Aсвой естественный номер N L ( x ) , а именно: начальное слово этого словаря получаетпервый номер, непосредственно следующее (если таковое имеется) – второй и т.д.Приведём способ вычисления номера слова в натуральном A -словаре позитивногоязыка A .Теорема 2.1.

Для слова x b1A , где b1,..., bm... bmA , его номер N AA ( x) вAнатуральном A -словаре Dc ( L) вычисляется согласно формуле:N AA ( x)N A (b1 ) k m1N A (b2 ) k m2... N A (bm 1 ) kгде | A | | A | k .►Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. БушуевN A (bm ) ,(1)10AСледствие 2.1. Номер N A ( y) непустого слова yAсогласно формуле N A ( y)Пример 2.2. Если BA в словаре Dc A ( A ) вычисляетсяAN A ( y) 1 .►a, b – алфавит из примера 1.1, то, согласно теореме 1.1, номераBN B ( y ) слова y bbb B равен числу:N BB ( y )N B (b) 231N B (b) 232N B (b) 2 22 2 2 2 14 ,что соответствует словарю примера 2.1.►Замечание 2.2. Если какому-либо символу x присваивается значение другого символа y ,то для этого используется обозначение x : y , где :– знак операции присваиваниязначения символа, стоящего справа от этого знака, символу, стоящему слева от этогознака.

В частности, в этом случае возможно выражение x : x 1, если символу x ужеприсвоено некоторое значение.►Пример 2.3. Приведём алгоритм вычисления слова в натуральном словаре позитивногоязыка по его номеру в этом словаре.ПустьA– номер словаn N A ( x)xAв натуральном словареADc ( A ) ,вычисленный согласно формуле (1). Тогда для определения этого слова x используетсяалгоритм, имеющий вид:(1-ый шаг) y : n ;(2-ой шаг) m : 1 ;(3-ий шаг) x;(4-ый шаг) если y0 , перейти к 14-ому шагу;(5-ый шаг) z : y rest k (остаток от деления числа y на число k );(6-ой шаг) если z 0 перейти к 10-ому шагу;(6-ой шаг) y : ( y z ) div k (частное от деления числа ( y z ) на число k );(7-ой шаг) xax , где aAA и N (a)z;(8-ой шаг) m : m 1 ;(9-ый шаг) перейти к 4-ому шагу;(10-ый шаг) y : ( y k ) div k ;Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.