Мониторинг обменных курсов валют
18c0693f

КС-грамматики и МП-автоматы


Пусть G = (N, T, P, S) - контекстно-свободная грамматика. Введем несколько важных понятий и определений.

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S

*u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определяется правосторонний вывод. Будем обозначать шаги левого (правого) вывода посредством
l (
r).

Упорядоченным

графом называется пара (V, E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ..., (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершину v2, и т.д.

Упорядоченным помеченным деревом называется упорядоченный граф (V, E), основой которого является дерево и для которого определена функция f : V

F (функция

разметки) для некоторого множества F.

Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:

  • корень дерева D помечен S;

  • каждый лист помечен либо a
    T, либо e;

  • каждая внутренняя вершина помечена нетерминалом A
    N;

  • если X - нетерминал, которым помечена внутренняя вершина и X1, ..., Xn - метки ее прямых потомков в указанном порядке, то

    X

    X1...Xk - правило из множества P;

  • Цепочка, составленная из выписанных слева направо меток листьев, равна w.

    • Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.

    Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A

    +A
    для некоторой цепочки
    .

    Автомат с магазинной памятью (МП-автомат) - это семерка M = (Q, T,

    , D, q0, Z0, F), где

  • Q - конечное множество состояний,

    представляющих всевозможные состояния управляющего устройства;

  • T - конечный входной алфавит;

  • - конечный алфавит магазинных символов;


  • D - отображение множества QЧ(T
    {e})Ч
    в множество конечных подмножеств QЧ
    *, называемое функцией переходов;


  • q0
    Q - начальное состояние управляющего устройства;


  • Z0
    - символ, находящийся в магазине в начальный момент (начальный символ магазина);


  • F
    Q - множество заключительных состояний.


    • Конфигурацией МП-автомата называется

    тройка (q, w, u), где

  • q
    Q - текущее состояние управляющего устройства;


  • w
    T* - непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана;


  • u
    * - содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.


    • Такт работы МП-автомата M будем представлять в виде бинарного отношения
    , определенного на конфигурациях. Будем писать

    если множество D(q, a, Z) содержит (p, v), где q, p
    Q, a
    T
    {e}, w
    T*, Z
    и u, v
    *.

    Начальной конфигурацией МП-автомата M называется конфигурация вида (q0, w, Z0), где w
    T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине находится только начальный символ Z0.

    Заключительная конфигурация - это конфигурация вида (q, e, u), где q
    F, u
    *, т.е. управляющее устройство находится

    в одном из заключительных состояний, а входная цепочка целиком прочитана.

    Введем транзитивное и рефлексивно-транзитивное замыкание отношения
    , а также его степень k
    0 (обозначаемые
    +,
    * и
    k соответственно).

    Говорят, что цепочка w допускается МП-автоматом M, если (q0, w, Z0)
    *(q, e, u) для некоторых q
    F и u
    *.

    Язык, допускаемый (распознаваемый, определяемый) автоматомM (обозначается L(M)) - это множество всех цепочек, допускаемых автоматом M.

    Пример 4.1. Рассмотрим МП-автомат



    у которого функция переходов D содержит следующие элементы:

     

    D(q0, a, Z) = {(q0, aZ)},

    D(q0, b, Z) = {(q0, bZ)},

    D(q0, a, a) = {(q0, aa), {q1, e)},

    D(q0, a, b) = {(q0, ab)},

    D(q0, b, a) = {(q0, ba)},

    D(q0, b, b) = {(q0, bb), (q1, e)},



    D(q1, a, a) = {(q1, e)},

    D(q1, b, b) = {(q1, e)},

    D(q1, e, Z) = {(q2, e)}.

     

    Нетрудно показать, что L(M) = {wwR|w
    {a, b}+}, где wR

    обозначает обращение («переворачивание») цепочки w.

    Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если (q0, w, Z0)
    *(q, e, e) для некоторого q
    Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива

    Теорема 4.1. Язык допускается магазинным автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.

    Доказательство. Пусть L = L(M) для некоторого МП-автомата M = (Q, T,
    , D, q0, Z0, F). Построим новый МП-автомат M', допускающий тот же язык опустошением магазина.

    Пусть M' = (Q
    {q0', qe}, T,
    {Z0'}, D', q0', Z0',
    ), где функция переходов D' определена следующим образом:

  • Если (r, u)
    D(q, a, Z), то (r, u)
    D'(q, a, Z) для всех q
    Q, a
    T
    {e} и Z
    ;


  • D'(q0', e, Z0') = {(q0, Z0Z0')};


  • Для всех q


    F и Z
    {Z0'} множество D'(q, e, Z) содержит (qe, e);

  • D'(qe, e, Z) = {(qe, e)} для всех Z
    {Z0'}.


    • Автомат сначала переходит в конфигурацию (q0, w, Z0Z0') в соответствии с определением D' в п.2, затем в (q, e, Y 1...Y kZ0'), q
    F в соответствии с п.1, затем в (qe, e, Y 1...Y kZ0'), q
    F в соответствии с п.3, затем в (qe, e, e) в соответствии с п.4. Нетрудно показать по индукции, что (q0, w, Z0)
    +(q, e, u) (где q
    F) выполняется для автомата M тогда и только тогда, когда (q0', w, Z0')
    +(qe, e, e) выполняется для автомата M'. Поэтому L(M) = L', где L' - язык, допускаемый автоматом M' опустошением магазина.

     

    Обратно, пусть M = (Q, T,
    , D, q0, Z0,
    ) - МП-автомат, допускающий опустошением магазина язык L.

    Построим автомат M', допускающий тот же язык по заключительному состоянию.

    Пусть M' = (Q
    {q0', qf}, T,
    {Z0}, D', q0', Z0', {qf}), где D' определяется следующим образом:

  • D'(q0', e, Z0') = {(q0, Z0Z0')} - переход в «режим M»;


  • Для каждого q
    Q, a
    T
    {e}, и Z
    определим D'(q, a, Z) = D(q, a, Z) - работа в «режиме M»;




  • Для всех q


    Q, (qf, e)
    D'(q, e, Z0') - переход в заключительное состояние.


    • Нетрудно показать по индукции, что L = L(M'). __

    Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности

    МП-автоматов и КС-грамматик.

    Теорема 4.2. Язык является контекстно-свободным тогда и только тогда, когда он допускается магазинным автоматом.

    Доказательство. Пусть G = (N, T, P, S) - КС-грамматика. Построим МП-автомат M, допускающий язык L(G) опустошением магазина.

    Пусть M = ({q}, T, N
    T, D, q, S,
    ), где D определяется следующим образом:

  • Если A
    u
    P, то (q, u)
    D(q, e, A);


  • D(q, a, a) = {(q, e)} для всех a
    T.


    • Фактически, этот МП-автомат в точности моделирует все возможные выводы в грамматике

    G. Нетрудно показать по индукции, что для любой цепочки w
    T*

    вывод S
    +w в грамматике G существует тогда и только тогда, когда существует последовательность тактов (q, w, S)
    +(q, e, e) автомата M.

     

    Обратно, пусть M = (Q, T,
    , D, q0, Z0,
    ) - МП-автомат, допускающий опустошением магазина язык L. Построим грамматику G, порождающую язык L.

    Пусть G = ({ [qZr] | q, r
    Q, Z
    }
    {S}, T, P, S), где P состоит из правил следующего вида:

    Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.

    Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что (q, w, A)
    +(p, e, e) тогда и только тогда, когда [qAp]
    +w.

    Тогда, если w
    L(G), то S
    [q0Z0q]
    +w для некоторого q
    Q. Следовательно, (q0, w, Z0)
    +(q, e, e) и поэтому

    w
    L. Аналогично, если w
    L, то (q0, w, Z0)
    +(q, e, e). Значит, S
    [q0Z0q]
    +w, и поэтому w
    L(G). __

    МП-автомат M = (Q, T,
    , D, q0, Z0, F) называется детерминированным (ДМП-автоматом), если выполнены следующие два условия:

  • Множество D(q, a, Z) содержит не более одного элемента для любых q
    Q, a
    T
    {e}, Z
    ;




  • Если D(q, e, Z)
    , то D(q, a, Z) =
    для всех a
    T.


    • Язык, допускаемый ДМП-автоматом, называется детерминированным КС-языком.

    Так как функция переходов ДМП- автомата содержит не более одного элемента для любой тройки

    аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.

    Пример 4.2. Рассмотрим ДМП-автомат



    у которого функция переходов определяется следующим образом:

     

    D(q0, X, Y ) = (q0, XY ), X
    {a, b}, Y
    {Z, a, b},

    D(q0, c, Y ) = (q1, Y ), Y
    {a, b},

    D(q1, X, X) = (q1, e), X
    {a, b},

    D(q1, e, Z) = (q2, e).

     

    Нетрудно показать, что этот детерминированный МП-автомат допускает язык L = {wcwR|w
    {a, b}+}.

    К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы. Доказано, в частности, что

    существуют КС-языки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).

    Рассмотрим еще одну важную разновидность МП-автомата.

    Расширенным автоматом с магазинной памятью назовем семерку M = (Q, T,
    , D, q0, Z0, F), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечного подмножества множества QЧ(T
    {e})Ч
    *

    во множество конечных подмножеств множества QЧ
    *. Все остальные определения (конфигурации, такта, допустимости) для расширенного

    МП-автомата остаются такими же, как для обычного.

    Теорема 4.3. Пусть M = (Q, T,
    , D, q0, Z0, F) - расширенный МП-автомат. Тогда существует такой МП-автомат M', что L(M') = L(M).

    Расширенный МП-автомат M = (Q, T,
    , D, q0, Z0, F) называется детерминированным, если выполнены следующие условия:

    Теорема 4.4. Пусть M = (Q, T,
    , D, q0, Z0, F) - расширенный ДМП-автомат. Тогда существует такой ДМП-автомат M', что L(M') = L(M).

    ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе, соответственно, LL и LR-анализаторов.




    Самый выгодный курс обмена валюты