Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов (1082244), страница 10
Текст из файла (страница 10)
Задания для самостоятельной работы1.Построить КС-грамматику, порождающую язык an для n>0.2.Построить КС-грамматику, порождающую язык anbn для n>0.3.Построить КС-грамматику, порождающую язык (ab)nc*an+m для n>0 и m>0.4.Построить КС-грамматику, порождающую язык (ab)*ca*bn+m для n>0 и m>0.5.Построить КС-грамматику, порождающую язык anb3mcma2n = an(bbb)mcm(aa)n дляn>1 и m>1.6.Построить КС-грамматику, порождающую язык (ab)n(ca)*bn+2(abc)* для n>0.7.Для леворекурсивной грамматики G: S→SabA | ba; A→AbA|bAa|c построитьэквивалентную праворекурсивную грамматику.8.Построить алгоритм устранения правой рекурсии и доказать эквивалентностьсоответствующего преобразования.9.Построить КС-грамматику, порождающую идентификаторы, при этомобозначить символом t любую букву, а символом f - любую цифру.10.
Дана КС-грамматика G:S → Aab | bSb | abB;A→ abS | ba | bbA;B → bB | Da | Aa;D → Dbb | aDa.Построить эквивалентную грамматику, все нетерминалы которой продуктивны.5. ТЕОРИЯ АВТОМАТОВ5.1. Понятие автомата. Типы автоматовАвтомат - это алгоритм, определяющий некоторое множество и, возможно,преобразующий его в другое множество.
Неформальное описание автоматов выглядитследующим образом: автомат имеет входную ленту, управляющее устройство с конечнойпамятью для хранения номера состояния, а также может иметь вспомогательную (рабочую)и выходную ленты.Существует два типа автоматов:1) распознаватели - автоматы без выхода, которые распознают, принадлежит ли входнаяцепочка заданному множеству L;2) преобразователи - автоматы с выходом, которые преобразуют входную цепочку x вцепочку y при условии, что x ∈ L.Входную ленту можно рассматривать как линейную последовательность ячеек, причемкаждая ячейка может хранить один символ из некоторого конечного входного алфавита.Лента автомата бесконечна, но занято на ней в каждый момент времени только конечноечисло ячеек.
Граничные слева и справа от занятой области ячейки могут заниматьспециальные концевые маркеры. Маркер может стоять только на одном конце ленты илиможет отсутствовать вообще.Входная головка в каждый момент времени читает (обозревает) одну ячейку входнойленты. За один такт работы автомата входная головка может сдвинуться на одну ячейкувправо или остаться на месте, при этом она выполняет только чтение, т.е. в ходе работыавтомата символы в ячейках входной ленты не меняются.Рабочая лента - это вспомогательное хранилище информации. Данные с нее могутчитаться автоматом, могут и записываться на нее.Управляющее устройство - это программа, управляющая поведением автомата.
Онопредставляет собой конечное множество состояний вместе с отображением, описывающим,как меняются состояния в соответствии с текущим входным символом, читаемым входнойголовкой, и текущей информацией, извлеченной с рабочей ленты. Управляющее устройствотакже определяет направление сдвига рабочей головки и то, какую информацию записать нарабочую ленту.Автомат работает, выполняя некоторую последовательность рабочих тактов. В началетакта читается входной символ и исследуется информация на рабочей ленте. Затем, взависимости от прочитанной информации и текущего состояния, определяются действияавтомата:1) входная головка сдвигается вправо или стоит на месте;2) на рабочую ленту записывается некоторая информация;3) изменяется состояние управляющего устройства;4) на выходную ленту (если она есть) записывается символ.Поведение автомата удобно описывать в терминах конфигурации автомата, котораявключает в себя:а) состояние управляющего устройства;б) содержимое входной ленты с положением входной головки;в) содержимое рабочей ленты вместе с положением рабочей головки;г) содержимое выходной ленты, если она есть.Управляющее устройство может быть недетерминированным.
В таком случае длякаждой конфигурации существует конечное множество возможных следующих тактов,любой из которых автомат может сделать, исходя из этой конфигурации. Управляющееустройство будет детерминированным, если для каждой конфигурации будет возможентолько один следующий такт.Существуют следующие типы автоматов:1) машина Тьюринга (МТ);2) линейно-ограниченный автомат (ЛОА);3) автомат с магазинной памятью (МП-автомат);4) конечный автомат (КА).Сложность рабочей ленты определяет сложность автомата.
Так, например:1) машина Тьюринга имеет неограниченную в обе стороны ленту;2) у линейно-ограниченного автомата длина рабочей ленты представляет собойлинейную функцию длины входной цепочки;3) у МП-автомата рабочая лента работает по принципу магазина LIFO;4) у конечного автомата рабочая лента отсутствует.5.2.
Формальное определение автоматаНеинициальный автомат - это пятерка вида А = (К, X, Y, δ, γ), гдеК - множество состояний (алфавит состояний);Х - входной алфавит;Y - выходной алфавит;δ - функция переходов, задающая отображение К⋅Х→К;γ - функция выходов, задающая отображение К⋅Х→У.Функционирование автомата можно задать множеством команд вида qx → py, где q и p∈ K, x ∈ X, y ∈ Y.Пусть на некотором такте ti управляющее устройство находится в состоянии q, а извходной ленты читается символ x.
Если в множестве команд есть команда qx → py, то натакте ti на выходную ленту записывается символ y, а к следующему такту ti+1 управляющееустройство перейдет в состояние p, т.е.:y(t) = γ(q(t), x(t)), q(t+1) =δ(q(t), x(t)).Если же команда qx → py отсутствует, то автомат оказывается блокированным и нереагирует на символ, принятый в момент ti, а также перестает воспринимать символы впоследующие моменты времени.В соответствии с определением неинициального автомата в начальный моментсостояние автомата может быть произвольным.Если зафиксировано некоторое начальное состояние, то такой автомат называютинициальным, т.е.
q(0) = q0.Инициальный автомат - это шестерка вида А = (К, X, Y, δ, γ, q0), гдеК - множество состояний (алфавит состояний);Х - входной алфавит;Y - выходной алфавит;δ - функция переходов (отображение К ⋅ Х → К);γ - функция выходов (отображение К ⋅ Х → У);q0 - начальное состояние.5.3. Распознаватели5.3.1. Языки и автоматыЗадача грамматического разбора заключается в нахождении вывода цепочки в заданнойграмматике и определения дерева вывода этой цепочки.Языки могут быть заданы двумя способами:1) грамматиками (порождающее средство языка);2) автоматами (распознающее средство языка).Различным по сложности автоматам соответствуют разные типы языков.
Простейшимтипом автоматов являются конечные автоматы.Конечный автомат имеет входную ленту, с которой за один такт может быть считан одинвходной символ. Возврат по входной ленте не допускается.Конечным автоматом называется пятерка вида А = (К, ∑, δ, p0, F), гдеК - конечное множество состояний;∑ - алфавит;δ - функция переходов;p0 - начальное состояние;F - множество заключительных состояний.Автомат можно определить как формальную систему через состояния, через символы,которые пишутся (читаются) с ленты или с нескольких лент, и через набор команд.Конечный автомат можно представить графом, таблицей переходов, командами, а такжематрицей переходов.5.3.2 Регулярные множестваРегулярные множества образуют класс языков, имеющих важное значение для теорииформальных языков. Рассмотрим несколько методов задания языков, каждый из которыхопределяет регулярные множества.
Среди них - регулярные выражения, праволинейныеграмматики, детерминированные и недетерминированные конечные автоматы.Пусть Σ - некоторый алфавит. Регулярное множество в алфавите Σ определяетсярекурсивно следующим образом:1) 0 - пустое множество;2) {ε} - множество из пустой цепочки;3) {a} - регулярное множество для каждого элемента a ∈ Σ;4) если P и Q - регулярные множества в алфавите Σ, то регулярными являютсямножества:а) P ∪ Qб) PQв) P*.Других регулярных множеств в алфавите Σ нет. Таким образом, некоторое множествоцепочек в заданном алфавите Σ называется регулярным тогда и только тогда, когда либо оноявляется одним из множеств: 0, {ε} или {a} для некоторого a ∈ Σ, либо его можно получитьиз этих множеств применением конечного числа операций объединения, конкатенации иитерации.Для каждого регулярного множества существует по крайней мере одно регулярноевыражение, обозначающее это множество.Язык, распознаваемый конечным автоматом, - это множество цепочек, читаемыхавтоматом при переходе из начального состояния в одно из заключительных состояний:L(A)={a1 a2 ...
an | p0a1 → p1, p1a2 → p2, ..., pn-1an → pn; pn ∈ F}.Множество называется регулярным, если существует конечный детерминированныйавтомат, распознающий его.5.3.3. Операции над регулярными языкамиТаккакпроизвольномуконечномуавтоматуоднозначносоответствуетдетерминированный конечный автомат, операции над конечными автоматами эквивалентныоперациям над регулярными множествами, или регулярными языками.Известно, что для произвольного конечного автомата можно построить эквивалентныйавтомат без циклов в начальных и (или) конечных состояниях.Теорема. Для произвольного конечного автомата существует конечный автомат безциклов в начальном состоянии.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
