Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов, страница 12

Для этого построимнесколько выводов возможных вариантов цепочек:1) S ⇒ aA ⇒ ab;2) S ⇒ aA ⇒ abS ⇒ abaA ⇒ abab;3) S ⇒ aA ⇒ abS ⇒ abaA ⇒ ababS ⇒ ababaA ⇒ ababab; и т.д.Таким образом, грамматика G действительно порождает язык L(A), следовательно,можно построить соответствующий этой грамматике конечный автомат. Для этого введемзаключительное состояние F, начальное состояние соответствует аксиоме S.bSАabFЗапишем преобразование правил вывода в команды:Sa → A - из состояния S при поступлении на вход терминала а автомат переходит всостояние А;Ab → S - из состояния А при поступлении на вход терминала a автомат переходит всостояние S;Ab → F - из состояния А при поступлении на вход терминала b автомат переходит взаключительное состояние F.Таким образом, построен недетерминированный конечный автомат, распознающийзаданный язык L(G).5.4.

Автоматы с магазинной памятьюАвтомат с магазинной памятью (МП-автомат) имеет рабочую ленту, котораяорганизована в виде магазина.МП-автомат - это семерка вида:M = (К, Σ, Г, δ, p0, F, B0), гдеК - конечное множество состояний;Σ - алфавит;Г - алфавит магазина;δ - функция переходов;p0 - начальное состояние;F - множество заключительных состояний;B0 - символ из множества Г для обозначения маркера дна магазина.В общем случае данное определение соответствует недетерминированному автомату.В отличие от конечного автомата для произвольного МП-автомата нельзя построитьэквивалентный детерминированный автомат.Основное использование распознавательных средств задания языков состоит впостроении алгоритмов грамматического разбора.

Поэтому необходимо для произвольнойКС-грамматики уметь строить эквивалентный МП-автомат.МП-автомат представляет интерес как средство разбора в КС-грамматикахпроизвольного вида. Этот факт сформулирован в следующей теореме.Теорема. Языки, порождаемые КС-грамматиками, совпадают с языками,распознаваемыми МП-автоматами.Доказательство. Существуют две стратегии разбора: восходящий и нисходящий разбор.Рассмотрим обе стратегии разбора.5.4.1.

Восходящий разбор в МП-автоматеПри восходящей стратегии необходимо найти основу и редуцировать ее к какому-нибудьнетерминалу в соответствии с правилами данной грамматики. Это можно сделать в томслучае, если реализовать следующий алгоритм функционирования МП-автомата:1) любой входной символ записывается в магазин;2) если в верхушке магазина сформирована основа, совпадающая с правой частьюправила, то она заменяется на нетерминал в левой части этого правила;3) разбор заканчивается, если в магазине остается аксиома, а входная цепочкарассмотрена полностью.В соответствии с этим алгоритмом для КС-грамматики G = (VT, VN, P, S) построим МПавтомат:M = (К, VT, Г, δ, p0, F, B0), где Г = VT ∪ VN ∪ {B0},K = {p0, F}, F = {f}.Функция переходов δ будет содержать следующие команды:а) p0, a, ε → p0, a - для любых a ∈ VT;б) p0, ε, ϕ’ → p0, A - для всех правил A → ϕ ∈ P, где ϕ’ - зеркальное отображение ϕ;в) p0, ε, SB0 → f, B0.В общем случае команда выглядит так:pi, σ, γ → pj, λ , где pi ∈ K – состояние автомата до выполнения команды, σ∈Vt – символна входной ленте, γ∈Γ - символ верхушки магазина, pj ∈ K – состояние автомата послевыполнения команды, λ∈Γ - символ, который записывается в магазин.Таким образом, любому выводу в грамматике G взаимно однозначно соответствуетпоследовательность команд построенного МП-автомата.

Обратное построение КСграмматики по произвольному МП-автомату также возможно, но не представляетпрактического интереса.Рассмотрим пример восходящей стратегии разбора.Пусть дана грамматика G:S → S+A | S/A | AA → a | (S);VN={S, A}, VT={a, (, ), +, /}.Для заданной КС-грамматики G необходимо построить МП-автомат.Эквивалентный МП-автомат должен содержать следующие команды:1. Команды переноса терминальных символов в магазин:p0, a, ε → p0, a ;p0, +, ε → p0, + ;p0, /, ε → p0, / ;p0, (, ε → p0, (;p0, ), ε → p0, ).Эти команды обеспечивают занесение терминального символа из входной ленты вмагазин.2.

Команды редукции по правилам грамматики:p0, ε, A+S → p0, S ;p0, ε, A/S → p0, S ;p0, ε, A → p0, S ;p0, ε, )S( → p0, A ;p0, ε, a → p0, A.Эти команды заменяют зеркальное отображение правила, полученного в верхушкемагазина, на нетерминал в левой части данного правила грамматики.3. Команды проверки на завершение разбора:p0, ε, SB0 → f, B0.Разбор завершается, если в магазине остались аксиома и маркер дна магазина, а входнаяцепочка полностью рассмотрена.Подадим на вход автомата цепочкупредставлен в таблице 1.a/(a+a)и выполним разбор.

Процесс разбора5.4.2. Нисходящий разбор в МП-автоматеНа любом шаге нисходящего разбора должно применяться какое-либо правило. Вначальный момент таким нетерминалом является аксиома. МП-автомат, выполняющийнисходящий разбор, работает по следующему алгоритму:1) в начальный момент времени в магазин заносится аксиома:p0, ε, ε → p1, S;2) для каждого правила A→ϕ∈P нетерминал в верхушке магазина заменяется на правуючасть правила с помощью команды: p1, ε, A → p1, ϕ;3) для каждого терминала a∈VT выполняется сравнение символа на входной ленте ссимволом в верхушке магазина и его поглощение: p1, a, a →p1, ε4) разбор заканчивается по команде: p1,ε,B0 → f, B0.Для грамматики, рассмотренной в предыдущем примере, разбор той же входнойцепочки по нисходящей стратегиибудет выполняться посредством следующегомножества команд:1) команда занесения аксиомы в магазин:p0, ε, ε → p0, S;2) команды замены нетерминала правой частью правила:p1, ε, S → p1, S+Ap1, ε, S → p1, S/Ap1, ε, S → p1, Ap1, ε, A → p1, ap1, ε, A → p1, (S);3) команды сравнения и поглощения символа с входной ленты и символа в верхушкемагазина:p1, a, a → p1, εp1, +, + → p1, εp1, /, / → p1, εp1, (, ( → p1, εp1, ), ) → p1, ε;4) команда завершения разбора:p1, ε, B0 → f, B0.Процесс разбора цепочки представлен в таблице 2.5.5.

ВыводыРассмотренные выше МП-автоматы работают недетерминированно, то есть если цепочкапринадлежит языку, порождаемому заданной грамматикой, то какой-то из вариантовфункционирования автомата осуществит правильный разбор. Если же цепочка непринадлежит языку, то никакой из вариантов разбора не приведет к цели.Отсутствие детерминированного эквивалентного автомата для произвольной КСграмматики означает невозможность построения универсальной простой однопроходнойпрограммы синтаксического анализа. Поэтому для эффективного разбора необходимовыделять специальные классы КС-грамматик, удовлетворяющие требованиям конкретныхтипов анализаторов.Если требуется выполнить разбор для произвольной КС-грамматики, то придетсяиспользовать детерминированную программную модель недетерминированного МПавтомата.5.6.

Понятие преобразователейАвтоматы с выходом называются преобразователями. В зависимости от вида функции,отображающей множество состояний и входных символов в множество выходных символови новых состояний, а также от типа рабочей ленты различают разные видыпреобразователей. Рассмотрим конечные автоматы-преобразователи.Конечным преобразователем называется шестерка видаP = (К, X, Y, f, g, q0), гдеK - конечное множество состояний;X - входной алфавит;Y - выходной алфавит;f - функция переходов;g - функция выходов;q0 - начальное состояние.Типы отображений f и g определяют различные виды автоматов. Если g - отображениеK ⋅ X в Y, то конечный преобразователь называется синхронным.

В общем случае этоотображение имеет вид K ⋅ X → Y*.Пусть P = (К, X, Y, f, g, q0) - конечный преобразователь. Тогда отображение S(x) = g(q0,x), определенное для любой цепочки x ∈ X*, называется конечным преобразователем.Заметим, что для того чтобы выходную цепочку y можно было считать переводомвходной цепочки x, цепочка x должна перевести преобразователь из начального состояния взаключительное.5.7. Автоматы Мили и МураАвтоматы Мили и Мура являются неинициальными автоматами.

В отображении S(x) =g(q0, x) зафиксируем начальное состояние q0, в котором автомат находится в начальныймомент времени. Оно существенно влияет на процесс конечного преобразования, т.к.определяет не только результирующую цепочку, но и множество входных цепочек.Рассмотрим поведение инициальных автоматов, которые могут начинать работать излюбого указанного состояния. Такой автомат получает на вход одну цепочку бесконечнойдлины и перерабатывает её. Реакция такого преобразователя на определенные воздействиянепредсказуема, если неизвестно его начальное состояние. Поэтому необходимо решить двезадачи, имеющие важное практическое значение:1) определение того состояния автомата, в котором он находится в момент, начиная скоторого исследуется его поведение;2) распознавание конечного состояния, в которое перешел автомат после завершенияиспытательной операции.