1. Алфавит, слова, операции над словами

1. Алфавит, слова, операции над словами Пусть V={v1, v2,…,vn}, n1 – некоторый алфавит. Тогда любая последовательность x1x2…xk, k0, где xi V – 1  i k , слово в алфавите V, при k=0 –получается пустое слово, обозначим его . Множество всех слов алфавита V обозначается V*. Слово X =x1…xk графически совпадает со словом Y=y1…yl, если xiV (1  i k), yjV (1  j k), l=k, и для любого i ,1  i k, xi=yi. Будем обозначать графическое совпадение слов X=Y.Длиной слова Х (обозначается Х) будем называть число вхождений символов в слово Х. Если X =x1…xk, то Х=k . =0Конкатенацией слов X =x1…xk и Y=y1…yl называется слово Z= XY= x1…xk y1…yl. Например, конкатенацией слов «авто» и «бус» будет слово «автобус».Свойства конкатенации: является единицей для конкатенации, т.е. для любого слова Х верно, что Х=Х=Х.Операция конкатенации является ассоциативной, т.е. (XY)Z=X(YZ).Операция конкатенации не является коммутативной, XYYX.Для конкатенации, как и для произведения, конкатенация n одинаковых слов X обозначается Xn. Считаем, что X0= для любого слова Х. Множество V* всех слов алфавита V является полугруппой относительно операции конкатенации. ^ Полугруппа – множество с заданной на нем ассоциативной бинарной операцией.Если слово Х=Х1 Х2, то Х1 начало слова Х, а Х2 – конец слова Х.Говорят, что слово P входит в слово Q, если существует пара слов R и S, такая, что R – первый элемент пары, S – второй элемент пары, и Q =R P S.Легко доказать Утверждение: Если слово P входит в слово Q, то существует некоторое слово U, такое, что P – начало U, а U - конец Q. Следствие: Если слово P входит в слово Q, то P есть начало некоторого конца Q (или конец некоторого начала Q).Если P есть некоторое начало (конец) Q и P  Q, то P собственное начало (конец) Q.Конкретные вхождения слова P в слово Q обозначаются RPS, где R, P,S – слова в алфавите V, V. Тогда R – левое крыло вхождения, S – правое крыло вхождения, P - основа.Говорят, что вхождение P1 слова P в слово Q предшествует вхождению P2 слова P в это же слово, если левое крыло вхождения P1 является собственным началом левого крыла вхождения P2. ^ 2. Языки. Операции над языками Произвольное множество цепочек над алфавитом V, иначе любое подмножество свободной полугруппы V*, называется формальным языком над V. Поэтому язык может быть задан теми же способами, как и любое множество:Перечислением элементов.Ограничивающим свойством.Через известные множестваПорождающей процедурой.В основном будем использовать 4 способ, но начнем с третьего.Например, для любого V множество слов четной длины является языком. Множество слов нечетной длины также явля­ется языком, но в отличие от первого — не замкнутым относи­тельно операции конкатенации. Будем обозначать языки буквой L (с индексами или без них). Рассмотрим операции над языками.Т.к. язык является множеством, то применимы все соответствующие операции, для которых выполняются все законы теории множеств. В частности,  L,  L.Теоретико-множественные операцииПусть L1 и L2 - два языка над алфавитом V. Язык L называется объединением этих языков (L = L1 L2 ), если L ={x / x L1  x L2}.Пересечением языков L1 и L2 называется язык L (L = L1 L2 ), если L ={x / x L1 & x L2}.Дополнением языка L1 до V* называется язык L (L=V*\L1), если L={ x/ xV* & x L1}.Специфические операцииПроизведением (иначе конкатенацией) языков L1 и L2 называется язык L (L=L1L2), если L={x y/xL1 & yL2}.Например, L1={ ac, a }, L2={ cb, b}, тогда L1L2 ={ acb, accb, ab}.Свойства операции конкатенации:Операция умножения языков ассоциативна:L1 (L2L3)= (L1L2) L3Операция умножения языков дистрибутивна от­носительно объединенияL (L1L2 ) = LL1  LL2. (L1L2 ) L = L1L L2LОперация умножения языков не коммутативна: L1L2L2L1. L {}= {} L = L Однако L(L1L2 )  LL1  LL2 , в общем случае равенства нет, что легко показать, подобрав соответствующий пример.В силу ассоциативности операции произведения, как и в случае конкатенации цепочек,записывается как L=L1n. По определению L0={}. Отме­тим, что {}   . так как  (пустой язык) вообще не со­держит никаких цепочек. Итерацией языка L1 называется язык L (L=L1*), если. Как нетрудно видеть, итерация алфавита V* (алфавит можно рассматривать как язык, состоящий из односимвольных слов) образует язык, состоящий из всех возможных цепочек, состав­ленных из символов V. Это обстоятельство и объясняет, по­чему V* используется для обозначения всех слов над алфави­том V.Вводится также операция усеченной итерации. ^ L называ­ется усеченной итерацией языка L1 (L=L1+), если^ 3. Абстрактные формальные системы Абстрактная формальная система – этоАлфавит А ( множество слов в этом алфавите – А*).Разрешимое множество А1  А*, элементы множества А1 называют аксиомами.Конечное множество вычислимых отношений Ri (1, …, n, ) на множестве A*, называемых правилами вывода. Говорят, что слово  выводимо из слов 1, …, n по правилу Ri. Аксиомы тоже могут быть заданы как унарные отношения, но это не всегда удобно.Выводимость. Вывод формулы В из формул A1, A2, … , An - последовательность формул F1, F2, … , Fm = B, такая, что Fi (i=1,…m) либо аксиома, либо одна из формул A1, A2, … , An, либо непосредственно выводима из F1, F2, … , Fi-1 по одному из правил вывода. Если существует вывод формулы В из формул A1, A2, … , An, то В выводима из A1, A2, … , An. Множество формул, выводимых из аксиом, называется теоремами теории.Теорема. Для любой формальной теории множество выводимых в ней слов перечислимо.Док-во:А** - множество всех конечных последовательностей 1, …, n, где i - слова в алфавите А. А** - перечислимо. Из-за разрешимости множества аксиом и вычислимости правил вывода по любой последовательности можно эффективно узнать, является ли она выводом в данной формальной системе (FS). Если в процессе перечисления А** отбрасывать все последовательности, не являющиеся выводами, то получаем перечисление множества выводов  последних слов выводов.  множество слов (формул), выводимых в произвольной формальной системе, перечислимо.Примеры формальных систем: системы продукций Поста (канонические системы), системы подстановок, формальные грамматики, исчисления и т.д.Каноническая система A= {a1,a2,…, an} – алфавит констант, X= {x1, x2,…,xm} – алфавит переменных, M= {M1, M2, …, Mk} – множество аксиом, Mi(AX)*,R = {R1, R2, …, Rl} – множество продукций, имеющих вид1, 2,…, j, i, (AX)*, 1, 2,…,j называются посылками,  - следствием. Слова в (AX)* называются термами, слова в А* - просто словами.Слово  называется применением аксиомы , если  получается из  подстановкой слов вместо переменных.Слово  непосредственно выводимо из 1, …, n применением продукции R , если существует подстановка слов вместо переменных в продукцию R, которая посылки превратит в 1, …, n, а заключение – в .Например, из acb , cabb применением продукции a x1b, x1 b x2 b x2 (подстановка x1=ca, x2=b) непосредственно выводимо bb. Выводимость – транзитивное и рефлексивное замыкание непосредственной выводимости.Доказуемо (теорема формальной системы ) - выводимо из множества аксиом.Например, позволяет построить множество нечетных чисел в унарном представлении. Теорема. Для любого перечислимого множества М слов в алфавите А существует каконическая система над А, множество теорем которой совпадает с М. (доказательство, с использованием МТ, приводится в [3])^ 4. Формальные порождающие грамматики Порождающей грамматикой называется упорядоченная четверка G=, где VT - алфавит терминальных или основных символов; VN — алфавит нетерминальных или вспомогательных символов(VTVN=  ); S - начальный символ или аксиома, S VN, R - конечное множество правил или продукций вида   , где  (VTVN)* VN (VTVN)*,  (VTVN)* - различные цепочки, а  специальный символ, не принадлежащий VTVN и служащий для отделения левой части правила  от правой . Такие символы, которые служат для описания языка, но не принадлежат самому языку, будем называть метасимволами. Го­ворят, что цепочка 1 непосредственно выводима из цепочки 0 (обозначается 01 ), если существуют такие 1, 2, , , что 01 2, 11 2 и существует правило  ( R). Иными словами 01 , если в 0 найдется вхождение левой части какого-либо пра­вила грамматики, а цепочка 1 получена заменой этого вхож­дения на правую часть правила. Существенно, что при опреде­лении отношения непосредственной выводимости обозначаемого  ( разумеется, также метасимвол) мы не указываем, какое правило нужно применять и к какому именно вхождению (если их несколько). Здесь проявляются характерные черты ис­числений, к классу которых относятся и порождающие грамма­тики. Исчисления представляют собой "разрешения" в отличие от алгоритмов, являющихся "предписаниями".Говорят, что цепочка n выводима из цепочки 0 за один или несколько шагов или просто выводима (обозначается 0+n ), если существует последовательность цепочек 1, 2,…, n (n>0), такая, что ii+1, i{0,…n}. Эта последовательность называется выводом n из 0, а n – длиной вывода. Выводимость за n шагов иногда обозначается 0nn На­конец, если 0+n или 0=n , то пишут 0*n.Нетрудно видеть, что + есть транзитивное, а * - транзитивно-рефлексивное замыкание отношения .Цепочка  называется сентенциальной формой, если она совпадает или выводима из начального символа грамматики, т.е. если S   ,Множество цепочек в основном алфавите грамматики, вы­водимых из начального символа, иначе множество сентенциаль­ных форм, состоящих из терминальных символов, называется языком, порождаемым грамматикой G, и обозначается L(G).L(G) = {x / S * x & xVT }.Для любого перечислимого множества слов М существует грамматика G, такая, что М= L(G).Говорят, что грамматики G1 и G2 эквивалентны, если L(G1 )=L(G2).Например, G1 = L(G1)= {a 2n+1, n 0}G2 = R = {S  1 A, A  1 A, A  0 A, A 0 }L(G2) – множество четных двоичных чисел, больших нуля.G3 = R = {S  1 A 0, A  1 A, A  0 A, A  }L(G2) = L(G3)Для сокращения записи грамматик и выводов будем изо­бражать нетерминальные символы прописными буквами латин­ского алфавита А , В , С , … , S терминальные -строчными буквами a, b, c,… и цифрами. Прописными буквами U, V, Z будем обозначать символы, которые могут быть как терминальными, так и нетерминальными; строчными буквами u, v, z c индексами или без них - цепочки, составленные из терминальных сим­волов, а буквами  … - из любых символов. Кроме того, для обозначения правил 1 2 ……….. nбудем пользоваться записью 12…n. Правила вида   , где   VT, называются заключительными.^ 5. Классификация грамматик Выделяются определенные классы грамматик, основными среди которых являются контекстно-свободные (КС), контекстно-зависимые (КЗ), автоматные… Основными типами грамматик являются:Грамматики класса «0» - не накладывается ограничений на вид правила.Контекстно-зависимые (КЗ) – грамматики, все правила которых имеют вид   , где ,  (VTVN )*     Например, грамматика G4 с правилами S  abA abbA  AbaA  aabAaA  aab Контекстно-свободные (КС- грамматики), все правила которых имеют вид А , где АVN , (VTVN )*.Например, грамматика G5 с правилами S  a Аb ab .L(G5) = L(G4)Автоматные (А-грамматики), все правила которых имеют вид Аа, Аa B, А, aVT, A,B VN.Иногда выделяется еще один класс грамматик: контекстные грамматики, или грамматики класса 1, все правила которых имеют вид , где , (VTVN), A VN, (VTVN )*.Здесь пара цепочек  и  составляет неизменяемый контекст правила. Между контекстными грамматиками и КЗ-грамматиками существует взаимно-однозначное соответствие, не всегда очевидное. По выразительной мощности эти классы грамматик совпадают, однако, поскольку для одного и того же языка контекстная грамматика содержит большее число правил, мы будем изучать именно КЗ-грамматики.Пример. Грамматика G6, КЗ-грамматика S aAcA aABcA bbBbbcB Bc L(G6)= {anbncn, n Эквивалентная ей контекстная грамматика G7. В ней правило переноса символа С заменяется на 3 правила. S ABCB ABDCB bbDbbCD EDED ECEC DCCc L(G7)= {anbncn, n В соответствии с классом грамматики, порождающей язык, классифицируются языки. Т.Е. язык, для которого может быть порожден КС- грамматикой, называется КС-языком (т.е. язык, для которого существует порождающая его КС-грамматика, и не существует А-грамматики, порождающей этот язык).А-язык - язык, для которого может быть построена порождающая его А-грамматика.КЗ-язык – язык, который может быть построен только КЗ-грамматикой.Непосредственная классификация грамматик выглядит следующим образом.Класс А-грамматик включается в класс КС-грамматик. Все грамматики принадлежат классу 0.Однако класс КС-грамматик не включается в класс КЗ-грамматик, так как правила вида А могут принадлежать КС-грамматикам, но не КЗ-грамматикам, т.к.  А.Поэтому общий вид классификации следующий:Класс 0КЗ-грамматикиКС-грамматикиКС-грамматики без -правилА-грамматики без -правилА-грамматикиДля рассмотрения иерархии языков надо больше знать о преобразованиях грамматик.^ 6. А-языки. Конечные автоматы. Диаграмма грамматики. Пусть дана А-грамматика G= . Диаграмма А-грамматики – граф с помеченными вершинами и дугами. Множество вершин графа соответствует множеству нетерминалов А-грамматики, приведенной к каноническому виду, а множество дуг – множеству правил грамматики.Преобразование грамматики: Вводим дополнительный нетерминальный символ К. VN =VNКЗаменяем правила вида Аа на правила АаК.Вводим дополнительное правило КТаким образом, все правила грамматики теперь приобрели "стандартный" вид AaB или A.Построение диаграммы опишем следующими правилами.1. Каждому нетерминальному символу поставим в соот­ветствие вершину и пометим ее этим символом.2. Каждому правилу AaB сопоставим дугу из верши­ны A в вершину В и пометим ее терминальным символом а.3. Отметим в графе как начальную вершину - вершину, со­ответствующую начальному символу, и как заключительные - все такие вершины В, что B (на диаграмме используется символ #) .Пример. Пусть грамматика G8 описывается правилами: S aBbCB bbBC aS Грамматика в канонической форме будет иметь вид: S aBbCB bKbBC aSK  Диаграмма грамматики приводится на рис.1.Рис.1 Очевидно, что существует взаимно-однозначное соответсвие между грамматикой в каноническом виде и диаграммой.Например, рассмотрим диаграмму грамматики, представленную на рис.2.Рис.2Очевидно, что диаграмме соответствует грамматика G9 с правилами S aSaBB bKbBK  ^ Порождение и распознавание цепочек. Конечный автомат (автомат Мили) S=, гдеVa={a1,a2,…am}, m1 – входной алфавит автомата,Vb= {b1, b2, …, bn}, n1 – выходной алфавит автомата,Q= {q0,q1,…qk}, k0 – внутренний алфавит (алфавит состояний),q0Q – начальное состояние автомата,F - функция переходов; F: Q Va Q, G - функция выходов, G: Q Va  Vb .Автомат однозначно задает отображение Va*  Vb* (входной цепочки в выходную).Пример автомата:Пусть Va = Vb= {a, b}, Q = {A, B}, q0=A. Функции переходов и выходов могут быть заданы в функциональной форме: F(A, a) = A G(A, a) = a F(A, b) = B G(A, b) = a F(B, a) = A G(B, a) = b F(B, b) = B G(B, b) = b Либо в виде объединенной таблицы входов-выходов, в которой по столбцам указаны исходные состояния, во строкам – входы, в соответствующей ячейке через запятую указываются состояние, в которое переходит автомат и соответствующий выходной сигнал. A B a A, a A, b b B, a B, b Диаграмма (граф переходов автомата), представляющая этот автомат, изображена на рис. 3.Рис. 3Диаграмма автомата похожа на диаграмму грамматики. Отличие состоит в том, что есть некоторый выход, не выделены конечные состояния.Если убрать выходы и ввести конечные состояния, то получится автомат, который не преобразует, а либо распознает, либо порождает цепочки – лингвистический автомат.^ Лингвистический автомат – это SL= T, q0, F, K>, где Q = {q0,q1,…qk}, k0 – множество состояний автомата (внутренний алфавит), VT={a1,a2,…am}, m1– множество терминальных символов (внешний алфавит) автомата,q0 – начальное состояние автомата, q0 Q, F: Q VTQ функция переходов, K Q – множество конечных(заключительных) состояний.Рассмотрим автомат как распознающий, тогда ему соответствует следующая абстрактная модель:Входная лента, на которой расположена анализируемая цепочка, считывающая(входная) головка и устройство управления.На каждом шаге обозревается ровно один символ. Пара (q,a), где a - обозреваемый символ, а q - состояние автомата, называется ситуацией автомата. Если автомат находится в ситуации (qi,aj) и F(qi, aj)=qk, то считывающая головка перемещается на один символ вправо, автомат переходит в состояние qk. Получаемая ситуация (qi,aj+1) (обозревается следующий символ на ленте. Если же F(qi, aj) не определена, то входная цепочка не допускается автоматом.Если в результате прочтения входной цепочки автомат окажется в заключительном состоянии, то говорим, что автомат допустил цепочку.Более строго:В начале работы автомат находится в состоянии q0, на входе – цепочка a1, a2,…,an, обозревается самый левый символ цепочки ситуация (q0, a1) , затем переход в некоторую ситуацию (qi, a1),…, (qj, an), и, наконец, в ситуацию (qs, ) &qsK. Назовём конфигурацией автомата пару H=(q, x), где q — текущее состояние автомата; x — остаток входной цепочки, самый левый символ которой обозревается входной го­ловкой. Конфигурация, очевидно, определяет и ситуацию. Говорят, что конфигурация (p, x1) получена из конфигурации (q, x) за один такт (обозначается (q, x) ├ (p, x1) ), если x= a x1 и F(q, a)= p.. Если H0, H1,…, Hn (n 1) - последовательность конфигураций, таких, что Hi├ Hi+1 , i {1,…,n}, то, как и раньше, будем использовать обозначения H0 ├ +Hnили H0 ├ * Hnесли справедливо H0 ├ +Hn H0=Hn.Пусть x — анализируемая цепочка. Начальная конфигу­рация имеет вид (q0, x) заключительная – (qs, ), qs F. Говорят, что автомат A допустил цепочку x, если (q0, x) ├ * (q, ) и q F (Использование отношения ├ * позволяет включить в множество допускаемых цепочек и пустую цепочку , если q0F.Языком ^ L(A), допускаемым конечным автоматом A, называется множество допускаемых им цепочекL(A) = { x / (q0, x) ├ * (q, ) & q K}.Диаграмма лингвистического автомата отличается от диаграммы автомата Мили выделением конечных состояний и отсутствием выходов.Например, для лингвистического автомата SA= 0, F, {q1}>, функция переходов которого F(q0,c)=q0,F(q0,a)=q1,F(q1, b)= q1, диаграмма представлена на рис. 4. Рис.4Язык, распознаваемый этим автоматом L(SA)= {cn a bm, n,m0}.Цепочка не распознается автоматом, если или нет перехода по читаемому символу, или в результате прочтения цепочки состояние, в которое перешел автомат - не конечное.Процесс допускания цепочки соответствует движению по графу. Цепочка допущена, если существует путь из начальной вершины в заключительную, при котором последовательно выписанные метки проходимых дуг составляют анализируемую цепочку.Граф автомата в силу тождественности его структуры с диаграммой грамматик всегда может рассматриваться как диаграмма некоторой грамматики, роль нетерминальных символов в которой будут играть метки состояний автомата. Нетрудно видеть, что грамматика, полученная по графу переходов автомата, при интерпретации последнего как ее диаграммы будет порождать тот же самый язык, который допускается автоматом. В обоих случаях язык однозначно определяется множеством путей из начальной вершины в заключительные, а множество путей совпадает, так как граф один и тот же. Таким образом, по любому конечному автомату может быть построена эквивалентная А-грамматика и, следовательно, абстрактно взятый ориентированный граф с помеченными вершинами и дугами, в котором выделена начальная и множество заключительных вершин и удовлетворяются требования однозначности отображения F, может рассматриваться и как диаграмма грамматики и как граф переходов автомата - все дело в интерпретации.По диаграмме автомата всегда легко построить эквивалентную грамматику (автомат по грамматике строить сложнее, так как в грамматике одному символу входного алфавита может соответствовать более одного перехода см., например, рис. 2.Правила грамматики по диаграмме автомата строится следующим образом:Каждому состоянию автомата сопоставляем нетерминал грамматики.Каждому переходу, соответствующему из состояния P по терминалу a в состояние Q сопоставляется правило грамматики PaQ.Каждому конечному состоянию R сопоставляется правило R.Начальному состоянию автомата сопоставляется начальный символ грамматики.Например, автомату, диаграмма которого представлена на рис.4, соответствует грамматика G10 с правилами S cS a A A b Aгде состоянию q0 сопоставлен нетерминал S, а состоянию q1 - нетериминал A.Таким образом, состояния конечного автомата однозначно отображаются в нетерминалы грамматики.Однако, если мы рассмотрим грамматику G11 c правилами S a S a A A b Ab K K ,диаграмма которой представлена на рис. 5Рис.5Однозначность нарушается неоднозначностью переходов, допускаемых в грамматиках.^ Детерминизация конечных автоматов Для того, чтобы построить соответствующее таким грамматикам автоматы, можно рассматривать переходы F автомата Q  VT в множество подмножеств Q ( т.е. в P(Q)). При этомP(Q)=2Q.Будем называть недетерминированным конечным автоматом S пятерку объектов S = T, q0, F, K>, где интерпретация Q, VT, q0, K такая же, как и раньше, а F – отображение Q  VT в P(Q).Определение цепочек, допускаемых автоматом, остается прежним, но если в детерминированном автомате последовательность конфигураций однозначно определялась заданием входной цепочки, так как из каждой конфигурации автомат мог перейти не более чем в одну конфигурацию, то в недетерминированном случае это не так. Поэтому при интерпретации определения "цепочка X допущена" как (q0,x) ├ (q, )&qK необходимо при анализе цепочки, моделируя работу автомата, перебрать варианты выполнения тактов, чтобы найти тот (или те), которые приводят в заключительную ситуацию. В силу тех же соображений (тождественность движений по графу и при порождении цепочки, и при ее допускании) можем утверждать, что для любой грамматики G может быть построен конечный автомат A (в общем случае недетерминированный), такой, что L(G)=L(A) . Соответствия между параметрами грамматики и автомата остаются те же.Возникает естественный вопрос о соотношении класса языков, допускаемых детерминированными и недетерминированными автоматами. Ясно, что для любого детерминированного автомата A существует недетерминированный A' допускающий тот же самый язык (достаточно в качестве A' взять А). Но верно ли обратное? Ответ на этот вопрос дает следующая теорема.Теорема 1. Если L=L(A) для некоторого недетерминированного автомата A , то найдется конечный автомат ^ A' такой, что L(A')=L(A).Доказательство:Пусть дан недетерминированный конечный автомат А = T, q0, F, K>. Построим соответствующий детерминированный автомат А’= T, q0’, F’, K’>Q’ = P(Q) . При этом множество состояний будем обозначать как .q0’=[q0].K’ = { / K }F’(, a)= Несложно доказать методом математической индукции, что для любого I([q0],XY) ├iA’(B,Y)  B={p/ (q0, XY) ├iA(p,Y)}X=i.Значит, для любой цепочки Х([q0],X) ├iA’(B,)  B={p/ (q0, X) ├iA(p,)}Поэтому, в случае B K’, т.е. если Х – цепочка, допускаемая детерминированным автоматом, то в исходном недетерминированном автомате существует путь из начального в конечное состояние при чтении этой цепочки, и, следовательно, L(A)=L(A’).Т.о., сопоставляя доказанные утверждения, получаем:Класс А-языков и класс языков, распознаваемых конечными автоматами, совпадает.Так, например, для автомата, представленного на рис. 5, соответствующий детерминированный автомат представлен на рис. 6.Рис.6Здесь F(S,a)= [S,A] = A’F([S,A], a) = [S,A]F([S,A],b) = [A, K] = K’F([A,K],b)= [A, K] = K’Для автомата на рис. 7а детерминированный автомат представлен на рис.7b.Рис.7Алгоритм построения детерминированного автомата по недетерминированному:Строим начальное состояние q0’= [q0], помечаем его как начальное.Для каждого состояния, построенного на предыдущем шаге, строимF(qi’, a) для всех aVT. Если для какого-нибудь из построенных состояний функция перехода ещё не построена, возвращаемся к шагу 2.Помечаем как конечные все состояния qi’= /  K.Конечность процесса обеспечивается конечностью множества P(Q).^ Автоматы с  - переходами. Автоматы с  - переходами естественно возникают в различных приложениях, и позволяют представить любой автомат в виде двухполюсников с одним входом и одним выходом, а так же строить сети из таких автоматов, сохраняя в них единственный вход и единственный выход. От рассмотренных ранее автоматов они отличаются тем, что в них присутствуют переходы, осуществляемыми без чтения входной цепочки ( на диаграмме такие переходы обозначаются стрелками, помеченными символом ).Рис. 8Рис.9Например, рассмотрим автомат с двумя выходами, представленный на рис. 9. Он имеет два выхода. Если просто объединить две выходные вершины, то получившийся автомат не будет эквивалентен исходному, т.к. после построения символа b в результирующем автомате возможно будет построение символов а, что было невозможно в исходном автомате. Эквивалентный исходному автомат представлен на рис. 10.Рис.10.Иногда в двухполюснике конечные состояния изображаются как Очевидно, что если L – А-язык, то ему можно сопоставить двухполюсник.Пусть языкам L1 и L2 сопоставлены соответствующие двухполюсники(рис.11 а). Тогда их объединению, конкатенации и итерации языка L1 будут, соответственно, сопоставлены двухполюсники рис. 11б, 11в, 11гРис.11Т.о. доказана теорема: Класс А-языков замкнут относительно операций объединения, конкатенации и итерации.Оптимизация автоматов с -переходами.Если из состояния А исходит единственная дуга и это -дуга в состояние В, то вершины А и В можно слить.Если из вершины А выходит -дуга в вершину В, являющуюся начальной вершиной некоторой дуги( не петли) или последовательности дуг, а С – конечная вершина этой дуги (последовательности дуг), и единственная дуга из С - -дуга в вершину А, то вершины А,В и С можно слить (примеры такого слияния приводятся на рис. 12 ( для одной дуги – а, б; для последовательности – в, г).Рис.12Теорема:Классы языков, допускаемых детерминированными автоматами и автоматами с -переходами, совпадают.Док-во:Пусть автомат ^ А = T, q0, F, K> - автомат -переходами. Построим соответствующий детерминированный автомат А’= T, q0’, F’, K’>, такой, что L(A)=L(A’) следующим образом.F’(q,a)={p / (q,ax) ├+ (p,x)}K’ = K {p / (q, ) ├* ( p, )& pK}Несложно показать, с использованием математической индукции по числу символов в распознаваемой цепочке, что получаемый таким образом автомат А’ переходит при распознавании цепочки Х в конечное состояние тогда и только тогда, когда существует последовательность переходов в конечное состояние автомата А при распознавании этой же цепочки символов.Пример. Пусть автомат представлен диаграммой на рис. 13а. Объединим по правилу 1 упрощения автоматов с -переходами состояния 4 и 5 и переобозначим состояния, как показано на рис. 13б.Построим функцию переходов детерминированного автомата А’. F(A, a) = [B,C, D, F]F(A, b) = [E]F(A,c) =  F([B, C, D, F], a) = [C,D, F],F([B, C, D, F], b) = [D, E],F([B, C, D, F], c) = , F([E], a) = ,F([E], b) = ,F([E], c) = [D], F([C, D, F], a) = [C, D, F]F([C, D, F], b) = [E]F([C, D, F],c) =  F([D, E], a) = [D, F]F([D, E], b) = [E]F([D, E],c) = [D] F([D, F], a) = [D, F]F([D, F], b) = [E]F([D, F], c) =  F([D], a) = [D, F]F([D], b) = [E]F([D], c) =  K’ = { [B, C, D, F] , [ D, F], [C, D, F]}Диаграмма детерминированного автомата представлена на рис. 14.Рис.14Тот же автомат после переобозначения состояний представлен на рис. 15.Рис.15^ 9. Минимизация числа состояний автомата 9.1. Лингвистический автомат. Алгоритм на основании языка L, порождаемого автоматом.Идея: разбить множество состояний на непересекающиеся множества неразличимых состояний.Строятся матрицы D0, D1,… указывающие различимость состояний по строкам длины n. Состояния qi и qj различимы по строке длины 0( 1 на пересечении строки i и столбца j матрицы D0): qi D0 qj (qiK ) & ( qj K)  (qi K)&( qjK).Далее определение по индукции: при i > 0 состояния qk и qj различимы по строке длины i, т.е. (qk Di qj ) qk Di-1 qj или aVT, такой, что F(qk,a) Di-1 F(qj,a).Состояние qk различимо от состояния qj , если  i 0 , такое, что qk Di qj .Очевидно, что qk Di qj  существует строка Х, Х i , что (F(qi, X)K ) & ( F(qj, X) K)  (F(qi, X) K)&( F(qj, , X)K).Пример.Диаграмма автомата представлена на рис. 16.Рис.16Матрицы, получающиеся при анализе автомата: D0 F T F T T F T T FT D1 F T F T T T T T FT D1=D2 Из анализа полученной матрицы получаем три класса эквивалентных состояний:K1 = {1, 4}, K2 = {2}, K3 = {3,5}. Диаграмма полученного автомата представлена на рис. 17. Рис.17^ 9.2. Метод Хафмена. Этот метод работает как для лингвистических автоматов, так и для автоматов Мили.Идея: объединение предположительно эквивалентных состояний, а затем проверка, являются ли состояния действительно эквивалентными. Затем, если состояния не эквивалентны, классы разбиваем на подклассы, и проверка повторяется. Если состояния ведут себя одинаково, то процедура закончена, и получившиеся классы являются состояниями минимизированного автомата.Два состояния называются эквивалентными, если автомат, находясь в этих состояниях, вырабатывает для любой входной последовательности одну и ту же выходную.Например, рассмотрим автомат, диаграмма которого представлена на рис. 18Рис.181. Составляем таблицы переходов и выходов. A B C D E F G 0 B 1 D 1 E 0 D 1 A 0 G 0 D 0 1 F 0 C 0 G 1 C 0 F 1 E 1 C 1 2. Составляем классы предположительно эквивалентных состояний (т.е. состояний, при переходе из которых на одинаковые входы выдаются одинаковые выходы).В данном случае это классы K1= {A, B, D}, K2= {C, E, F, G}3. Составляем таблицу переходов, в которой вместо состояний указываются классы, которым принадлежат состояния. A B C D E F G 0 K1 K1 K2 K1 K1 K2 K1 1 K2 K2 K2 K2 K2 K2 K2 Если в пределах одного класса состояния ведут себя по-разному, то класс разбивается на соответствующие подклассы, и возвращаемся к шагу 3.(В нашем случае классы разбиваются, таблицы приводятся после алгоритма).4. Если во всех классах состояния ведут себя одинаково, то это действительно классы эквивалентности.Строится автомат, состояниями которого являются классы эквивалентности исходного автомата.В нашем примере класс К2 разбивается на 2 класса - К3= {C, F}, К4 = {E,G} A B C D E F G 0 K1 K1 К4 K1 К4 К4 К4 1 К3 К3 К4 К3 К3 К4 К3 После этого разбиения состояния в классах действительно эквиваленты, Диаграмма полученного автомата представлена на рис. 19.Рис.19Метод Хафмена может быть применен и к лингвистическим автоматам. В этом случае начальное разбиение происходит на класс конечных состояний и тех состояний, которые не являются конечными.Применение метода к автомату, диаграмма которого представлена на рис. 16, имеющему таблицу переходов 1 2 3 4 5 a 2 2 1 2 4 b 3 4 2 5 2 и конечные состояния 3, 5, на первом шаге дает классы К1 = {3, 5}, K2= {1, 2, 4} и, соответственно, получаем таблицу переходов: 1 2 3 4 5 a K2 K2 K2 K2 K2 b К1 K2 K2 К1 K2 Видно, что класс K2 разбивается на два класса K3= {1, 4}, K4={2}. Получается таблица переходов 1 2 3 4 5 a K4 K4 K3 K4 K3 b К1 K3 K4 К1 K4 Очевидно, что, как и следовало ожидать, получившийся минимальный автомат совпадает с тем, который получен в пункте 9.1. Диаграмма полученного автомата приведена на рис. 17.9.3. Минимизация не полностью определенных автоматов (на примере лингвистического автомата, диаграмма которого представлена на рис. 15 ).Повторение, рис. 15.При минимизации не полностью определенных лингвистических автоматов начальное разбиение множества состояний делается так же, как для полностью определённого автомата, на конечные и не конечные состояния. Для данного случая классы K1={B, C, F} – конечные состояния, K2= {A, D, E, G} – не конечные. Приведем таблицы переходов состояний для этого автомата:Исходная таблица: A B C D E F G a C B B F - F F b E E G E - E E c - - - - D - D Проставляем классы состояний (в верхней строке указываем номер класса состояния): № 2 1 1 2 2 1 2 A B C D E F G a K1 K1 K1 K1 - K1 K1 b K2 K2 K2 K2 - K2 K2 c - - - - K2 - K2 Далее разбиваем классы на подклассы в соответствии с одинаковостью- различием столбцов. Класс K2 разбивается на 3 класса K3 = {A, D}, K4 = {E}, K5 = {G}. № 3 1 1 3 4 1 5 A B C D E F G a K1 K1 K1 K1 - K1 K1 b K4 K4 K5 K4 - K4 K4 c - - - - K3 - K3 Получившаяся таблица показывает, что класс K1 так же разбивается на два класса K6= {B, F}, K7 = {C}. № 3 6 7 3 4 6 5 A B C D