Главная страница
Навигация по странице:

  • Определение.

  • Задача распознавания цепочек языка. Задачей распознавания является задача, определяющаяся является ли заданная цепочка порождением заданной грамматикой. Определение.

  • Классификация грамматик по Хомскому.

  • Примеры построения грамматик.

  • Примеры грамматик, используемых при определении языков программирования

  • Пример. Построить грамматику, порождающую десятичные числа с точкой и знаком: +23.5; 0.5; -1.5; .01 ::=+

  • Грамматика для выполнения арифметических операций.

  • Соответствие конечных автоматов и автоматных грамматик.

  • Этапы для заданной автоматной грамматики. 1. Преобразование автоматной грамматики. Пример.

  • Построение грамматики по заданному конечному автомату

  • Недетерминированные конечные автоматы

  • Преобразование недетерминированного автомата в детерминированный Имеется два способа: 1. Общий способ Пример.

  • Преобразование некоторых типов грамматики к автоматному ввиду

  • Алгоритм получения правил, не содержащих правил вывода нетерминальных символов.

  • Построение распознавателей и преобразователей

  • Построение распознавателей Пример.

  • Алгоритм построения преобразователя.

  • Автоматы, языки и грамматики


    Скачать 459.8 Kb.
    НазваниеАвтоматы, языки и грамматики
    АнкорАвтоматы, языки и грамматики.pdf
    Дата13.01.2020
    Размер459.8 Kb.
    Формат файлаpdf
    Имя файлаАвтоматы, языки и грамматики.pdf
    ТипДокументы
    #17244

    Автоматы, языки и грамматики.
    Язык – это совокупность правильно построенных конструкций (предложений).
    Грамматика - это совокупность следующих объектов: G=т
    ,V
    n
    ,I,R>
    V
    т
    словарь терминальных символов, который состоит из основных символов языка, к которым относятся буквы, цифры, знаки и неделимые конструкции языка (for, while,…).
    V
    т
    = {a,b,…,z}
    V
    n
    – словарь нетерминальных символов, используемый для обозначения конструкций языка при записи правил грамматики.
    V
    n
    = {A,B,…,Z}
    I – начальный символ грамматики, является элементом нетерминального словаря.
    I € V
    n
    R – множество порожденных правил вида:
    φ  ψ, где φ и ψ – некоторые последовательности символов полного алфавита грамматики: V* = (V
    т v V
    n
    )
    *
    ,
    где
    V = V
    т v V
    n
    – полный словарь (алфавит) грамматики.
    В φ входит хотя бы один нетерминальный символ.
    V
    т
    *
    - множество конечных цепочек, построенных из терминальных символов.
    V*
    - множество всех конечных цепочек, построенных из символов полного словаря
    (терминальных и нетерминальных символов).
    φ, ψ € V
    *
    - конечные цепочки, построенные из символов общего словаря.
    Порождающее правило определяет подстановку, при котором рассматриваемая цепочка последовательных символов φ заменяется на последовательность ψ.
    Пусть задано правило R : φ  ψ, тогда, если задана цепочка:
    ώ
    1
    = ξ
    1
    φ ξ
    2
    , где ξ
    1
    ξ
    2
    € V* - цепочки, и если из нее получается цепочка следующего вида:
    ώ
    2
    = ξ
    1
    ψ ξ
    2
    Тогда говорят, что ώ
    2
    выводима непосредственно из ώ
    1
    и обозначается
    ώ
    1
    => ώ
    2 или
    *
    ώ
    1
    => ώ
    n
    Предположим, что есть множество цепочек:
    Ω = { ώ
    1
    , ώ
    2
    , ώ
    3
    , … , ώ
    n
    }, таких, что
    ώ
    1
    => ώ
    2
    ώ
    2
    => ώ
    3

    ώ
    n-1
    => ώ
    n
    , то говорят, что
    *
    ώ
    1
    => ώ
    n

    n выводима из
    ώ
    1
    )
    Определение. Множество конечных цепочек, которые выводятся из начального символа грамматики и, которые представлены только терминальными символами, называются языком порождаемой грамматикой:
    *
    L(G) = { ώ : ώ € V
    т
    *
    & I => ώ }
    Рассмотрим примеры грамматик и языков:
    1.G
    1
    :
    V
    т
    = {a , b , c}
    I
    V
    n
    = {I}
    R = {Iabc}
    L(G
    1
    ) = {(abc)}
    2. G
    2
    :

    V
    т
    = {a , d , c}
    I
    V
    n
    = {I , B , C}
    R = { IaB,
    - правило 1
    BCd,
    - правило 2
    BdC,
    - правило 3
    C c}
    - правило 4
    I
    1
    => aB
    2
    => aCd
    4
    => acd
    3
    => adC
    4
    => adc
    L(G
    2
    ) = {(acd) , (adc)}
    3. G
    3
    :
    V
    т
    = {a , b , e}
    I
    V
    n
    = {I , A}
    R = { IaAb,
    - правило 1 aAaaAb, - правило 2
    Ae}
    - правило 3 где e

    V
    T
    – пустой символ
    I
    1
    => aAb
    3
    => ab
    I
    1
    => aAb
    2
    => aaAbb
    2
    => aabb
    I
    1
    => aAb
    2
    => aaAbb
    2
    => aaaAbbb
    3
    => aaabbb

    L(G
    3
    ) = {(a n
    b n
    ) n>=1}
    4. G
    4
    :
    V
    т
    = {a, b}
    I
    V
    n
    = {I , A}
    R = { IaA,
    - правило 1
    AbA}
    - правило 2
    I
    1
    => aA
    2
    => abA
    2
    => abbA
    2
    => …
    Грамматика не порождает цепочек, содержащих только нетерминальные символы, следовательно язык не порождающий цепочек, следовательно язык пустой.
    Чтобы язык был не пуст в нем должно быть: a) хотя бы одно правило вида:
    η  w , w € V
    т
    *
    * b) I => η
    Если пронумеровав все правила грамматики записать последовательность номеров правил, использованных для порождения цепочки, то эта последовательность номеров называется синтаксическим разбором цепочки. Синтаксический разбор цепочки может осуществляться в виде синтаксического дерева.
    Пример:
    G
    5:
    V
    т
    = {a , b}
    V
    n
    = {I , A}
    I
    R = {I  aAb,
    - правило 1
    A  aAb,
    - правило 2
    A  ab,
    - правило 3
    A  e},
    - правило 4
    где e

    V
    T
    – пустой символ
    L(G
    5
    ) = {(a n
    b n
    ) n>=1}
    Это синтаксический разбор цепочки. Порожденная цепочка представляет собой конечные вершины дерева, которые выписываются при обходе вершин дерева против часовой стрелки.
    Определение. Две грамматики называются эквивалентными, если они порождают одинаковые языки.
    G
    3
    и G
    5
    – эквивалентны: L(G
    3
    ) = L(G
    5
    ).
    Определение. Цепочка, порожденная грамматикой, называется неоднозначной, если она может быть выведена из начального символа более чем одним способом, т.е. цепочка имеет несколько синтаксических разборов.
    Определение. Грамматика называется неоднозначной, если содержит хотя бы одну неоднозначно выводимую цепочку.
    G
    6
    :
    V
    т
    = {a , b , с , d}
    I
    V
    n
    = {I , A , B}
    R = { IAB,
    - правило 1
    Aa,
    - правило 2
    Aac,
    - правило 3
    Bb,
    - правило 4
    Bcb}
    - правило 5
    I
    1
    => AB
    2
    => aB
    4
    => ab
    I
    1
    => AB
    3
    => acB
    4
    => acb
    I
    1
    => AB
    2
    => aB
    5
    => acb
    Данная цепочка неоднозначна, следовательно G
    6
    неоднозначна.
    Задача распознавания цепочек языка.
    Задачей распознавания является задача, определяющаяся является ли заданная цепочка порождением заданной грамматикой.
    Определение. Пусть заданы две цепочки:
    ώ
    1
    = ξ
    1
    φ ξ
    2
    ώ
    2
    = ξ
    1
    ψ ξ
    2
    ξ
    1
    ξ
    2
    € V*
    И правило:
    R = φψ, где φ,ψ € V
    *
    I
    A
    A
    A e a a a a b b b b aaaabbbb
    то говорят, что цепочка ώ
    1 получается из цепочки ώ
    2
    путем непосредственного сворачивания ώ
    1
    <= ώ
    2
    за счет применения правила R,
    либо n
    ώ
    1
    <= ώ
    2
    Определение. Пусть задано множество цепочек:
    Ω = { ώ
    1
    , ώ
    2
    , ώ
    3
    , … , ώ
    n
    }
    ώ
    n-1
    <
    = ώ
    n

    ώ
    1
    <= ώ
    2 то говорят, что
    *
    ώ
    1
    <= ώ
    n
    (просто сворачивание)
    Определение. Если заданная цепочка терминальных символов может быть сведена сворачиванием к начальному символу, то она принадлежит языку, порождаемому заданной грамматикой.
    Классификация грамматик по Хомскому.
    1) Грамматика типа 0 или общего вида.
    Порождающие правила этой грамматики не имеют ограничений:
    R: φ  ψ , φ ≠ e (e – символ конца)
    φ может содержать не только терминальные символы
    | ώ | - длина цепочки – число символов цепочки.
    | φ | < | ψ |
    Могут быть правила, которые укорачивают цепочки. Эта грамматика не имеет практического использования.
    2) Грамматика типа 1 или непосредственных составляющих.
    Это контекстно-зависимая грамматика, то есть применение правил этих грамматик зависит от контекста, и не укорачивает длину цепочки.
    R: ξ
    1
    φ ξ
    2
     ξ
    1
    ψ ξ
    2
    ξ
    1
    ξ
    2
    φ ψ € V
    *
    Пример:
    G
    8
    V
    т
    = {a, b, с, d}
    I
    V
    n
    = {I, A, B}
    R = { IaAI,
    AIAAI,
    AAAABA,
    AB, aBA  bcdA, bI  ba}
    3) Грамматика типа 2 или контекстно-свободная
    На порождающее правило накладывается гораздо большее ограничение:
    R: A ώ
    A € V
    n
    , ώ € V
    *
    Пример:
    G
    9
    V
    т
    = {a , b}
    I
    V
    n
    = {I }

    R = { IaIa,
    - правило 1
    IbIb,
    - правило 2
    Iaa,
    - правило 3
    I  bb}
    - правило 4
    I
    1
    => aIa
    2
    => abIba
    1
    => abaIaba
    4
    => ababbaba
    L(G
    9
    ) = {xx
    1
    ; x € V
    т
    *
    } где x
    1
    – зеркальное отражение x.
    4) Грамматика типа 3 или автоматная
    На порождающее правило накладывается суровое ограничение: a) Левосторонняя автоматная грамматика:
    A  a, A  Ba b) Правосторонняя автоматная грамматика:
    A  a, A  aB
    A, B € V
    n
    , a € V
    т
    В автоматной грамматике не могут быть одновременно право и левосторонние правила – только одни из них.
    Правила вида:
    A  aA – для правосторонней грамматики,
    A  Aa - для левосторонней грамматики называются рекурсивными.
    Для каждой автоматной грамматики может быть построен, реализующий ее конечный автомат.
    Пример:
    G
    10
    V
    т
    = {a, b}
    I
    V
    n
    = {I, A}
    R = { IaI,
    IaA,
    AbA,
    A  b}
    I
    1
    => aI
    1
    => aaI
    2
    => aaaA
    3
    => …
    4
    =>aa…abb…bb
    L(G
    10
    ) = {a n
    b m
    , a,b € V
    т
    , n>0 , m>0 }
    Язык, порождаемый грамматикой типа i, называется языком типа i, где i меняется от 0 до 3.
    L
    0
    <=L
    I
    <=L
    II
    <=L
    III
    Язык L
    III
    более узкий – самый простой, автоматный, чем язык L
    0
    (наиболее общий язык).
    Примеры построения грамматик.
    Предположим, что необходимо построить грамматику, содержащую 2 символа *, /, при этом каждая цепочка начинается с одной *, а заканчивается **, называемыми, началом и концом цепочки. Внутри содержит последовательность ////, разделенных *, т.е. допустимы */**,
    *///**, *//*/*///**.
    V
    т
    = {/,*}
    V
    n
    = {A, I}
    Начнем с простого:
    A будет обозначать любую непустую последовательность наклонных.
    R = { I  *A**,
    - правило 1
    A/,
    - правило 2
    A  A/}
    - правило 3

    Чтобы получить произвольное количество цепочек из наклонных, введем нетерминальный символ B, который означает цепочку из наклонных, разделенных *, при этом надо добавить два правила (B  A, B  B * A) и изменить первоначальное правило (I  *B**). Тогда:
    R = { I  *B**,
    - правило 1
    B  A,
    - правило 2
    B  B * A, - правило 3
    A/,
    - правило 4
    A  A/}
    - правило 5
    Пример:
    I
    1
    =>*B**
    3
    =>*B*A**
    3
    =>*B*A*A**
    2
    =>*A*A*A**
    4
    =>*/*A*A**
    5
    =>*/*A/*A**=>…
    4
    =>*/*///*////**.
    Примеры грамматик, используемых при определении языков программирования
    Терминальный словарь – множество основных символов языка.
    Нетерминальный словарь – множество синтаксических понятия языка.
    При формальном описании языка программирования используется так называемый метаязык
    (язык, используемый для описания другого языка).
    Для описания правил языка будем использовать язык Бекуса (Бекусовская нормальная форма).
    Пример. <целое без знака>
    ::= - “это есть”.
    В левой части Бекусовского правила пишется определяемое понятие, а в правой цепочка состоящая из основных символов и синтаксических понятий.
    В правой части может стоять вертикальная черта | (понятие “ИЛИ”).
    Пример.
    Бекусовское правило:
    <целое без знака>::=<цифра>|<целое без знака><цифра>
    <цифра>::=0| 1|2 … | 9.
    Грамматика (формальная):
    V
    т
    = {0,1,2…9}
    V
    n
    = {I,A}
    I
    R = {IIA , IA , A0 , A1…A9}
    Это контекстно-свободная грамматика (типа 2).
    Пример.
    Грамматика для идентификатора (цепочка из символов, букв, цифр, или символов подчеркивания, начинающихся с буквы для простоты):
    Бекусовское правило:
    <идентификатор>::=<буква>|<идентификатор><буква>|<идентификатор><цифра>
    <цифра>::=0| 1| 2…|9
    <буква>::=_|a|b|c…|z
    Грамматика (формальная):
    V
    т
    = {0, 1, 2, …, 9, a, b, …, z}
    V
    n
    = {I, B, C}
    R = {IB, IIB, IIС, B_, Ba, B…z, C0…C9}
    Порождение:
    I
    3
    =>IC
    3
    =>I9=>B8 5
    =>a9
    Контекстно-свободные грамматики типа 2
    <идентификатор>::=<буква><конец идентификатора>
    <буква>::=a|b…|z

    <конец идентификатора>::=<буква><конец идентификатора>|<цифра><конец идентификатора>| <пусто>
    Предполагается, что идентификатор заканчивается символом <пустой символ> - обозначим его как e.
    V
    т
    = {0, 1…9, a, b, c…, z, e}
    V
    n
    ={I , B , C , E}
    I
    R = {IBE, EBE, ECE, Ee, Ba..z, C0..9}
    Сделаем ее автоматной:
    I=>aE, E=>aE, E=>0E, E->a, E=>0

    I=>zE, E=>zE, E=>9E, E->z, E=>9
    Пример.
    Построить грамматику, порождающую десятичные числа с точкой и знаком:
    +23.5; 0.5; -1.5; .01
    <десятичное число с(.)>::=+<десятичное число с (.)>|<десятичное число с (.)>|-
    <десятичное число с (.)>
    < десятичное число с (.)>::=<целое число>.<целое число> |.<целое число>.
    <целое число>::= <цифра>|<целое число><цифра>
    <цифра>::=0|1…|9
    V
    т
    ={0,1…9, +, -, .}
    V
    n
    = {P, Q, N, D}
    P – начальный символ грамматики.
    P – десятичное число с(.) и со знаком
    Q - десятичное целое число с(.).
    N – целое число.
    D – цифры.
    R = {P+Q, PQ, P-Q, QN.N, Q.N , ND, NND, D0, D1…D9}
    Переведем эту грамматику в автоматную:
    R = {N0N,…, N9N, N0 ,…, N9, A.N, Q1D, …, Q9D , P+Q , P-Q, PQ}
    Грамматика для выполнения арифметических операций.
    Пример грамматики, определяющей множество правил построения арифметических выражений, использующих правила сложения и умножения.
    V
    т
    = {i, X, +, *, (, )}
    V
    n
    ={ E }
    E
    R = { Ei+E;
    - правило 1
    Ei;
    - правило 2
    Ei*E;
    - правило 3
    E(E)}
    - правило 4
    E
    1
    => i+E
    3
    => i+i*E
    4
    => i+i*(E)
    1
    => i+i*(i+E)
    2
    =>i+i*(i+i)
    Набор данных правил не обеспечивает скобки для первых операндов, то есть нельзя построить (i+i)+i.
    Пример.
    V
    т
    = {i, X, +, *, (, )}

    V
    n
    ={ E }
    E
    R = { EE*E;
    - правило 1
    EE+E;
    - правило 2
    E(E);
    - правило 3
    Ei }
    - правило 4
    E
    2
    =>E+E
    1
    =>E+E*E
    4
    =>i+i*i
    E
    1
    =>E*E
    4
    =>E*i
    2
    =>E+E*i
    4
    =>i+i*i
    Для одной и той же цепочки получили два синтаксического разбора, следовательно грамматика не однозначна.
    Недостаток - грамматика не обеспечивает приоритет операций сложения и умножения.
    Чтобы обеспечить приоритеты операций мы можем операции суммирования сделать в скобках, тогда:
    R = ( E(E*E);
    - правило 1
    E(E+E);
    - правило 2
    Ei)
    - правило 3
    E
    2
    => (E+E)
    1
    => (E+(E*E))
    3
    => (i+(i*i))
    E
    1
    => (E*E)
    2
    => ((E+E)*E)
    3
    => ((i+i)*i)
    Грамматика получилась неоднозначной, однако каждая операция оказалась в своей скобке.
    Приоритетность операции * по отношению к операции + обеспечивается благодаря скобкам.
    Недостаток – слишком много скобок.
    V
    т
    = {I, *, +, (, )}
    V
    n
    ={ E,T, P}
    E – арифметическое выражение.
    Т – слагаемое (или терм).
    Р – произведение или сам множитель.
    R={ EE+T,
    ET,
    TT*P,
    TP,
    P(E),
    Pi}
    Нужно получить : (i+i) + i * i
    E
    1
    =>E+T
    2
    =>T+T
    4
    =>P+T
    5
    =>(E)+T
    1
    =>(E+T)+T
    3
    =>(E+T)+T*P
    2
    =>(T+T)+T*P
    4
    =>(P+P)+P*P
    6
    =
    >(i+i)+i*i
    Данная грамматика полностью удовлетворяет требованиям арифметической операции для умножения и суммирования, однако она не однозначна. Если в правилах в правой части существует два разных нетерминальных символа, то грамматика будет неоднозначна.
    При распознавании цепочки в процессе трансляции осуществляется ее сворачивание.
    Пример.
    i+i*i<=
    666
    P+P*P<=
    44
    T+T*P<=
    3
    T+T<=
    2
    E+T<=
    1
    E
    Если в процессе сворачивания не учитывать приоритет операций, то цепочку свернуть невозможно.

    Соответствие конечных автоматов и автоматных грамматик.
    Цепочка терминальных символов входного алфавита автомата называется допустимой, если в результате действий этой цепочки автомат из начального состояния переходит в одно из конечных состояний (их может быть несколько).
    Множество допустимых цепочек автомата называется языком, который допустим данным автоматом.
    Утверждение:
    Для каждой автоматной грамматики может быть построен конечный автомат допускающий язык, который порождается заданной грамматикой.
    Этапы для заданной автоматной грамматики.
    1. Преобразование автоматной грамматики.
    Пример. Пусть задана автоматная грамматика. Для ее преобразования: a) Добавим нетерминальный символ Z

    V
    N
    b) Все правила вида Ax, где A

    V
    N
    , x

    V
    T
    преобразуем к виду: AxZ
    (правосторонняя грамматика), AZx (левосторонняя грамматика), в зависимости от того, какая грамматика. c) Добавляем правило ZE, где E

    V
    N
    – пустой символ.
    2. Построение графа автомата и его разметка.
    Сопоставим каждому нетерминальному символу вершину графа, помеченную этим символом.
    Для каждого правила AxB, где A,B

    V
    N
    , x

    V
    T
    ставится в соответствие дуга между вершинами A и B, которые помечаются символом x:
    Этапы:
    1. Начальному символу грамматики сопоставляется начальное состояние автомата.
    2. Алфавиту нетерминальных символов – алфавит состояний.
    3. Алфавиту терминальных символов – алфавит входных слов.
    4. Операции ZE соответствует конечная вершина автомата.
    5. Правилам грамматики соответствует функции перехода автомата.
    Пример.
    V
    т
    = {с, d}
    V
    n
    ={I}
    I
    R = {Ic; - правило 1
    IIc; - правило 2
    IId} - правило 3
    I
    2
    =>Ic
    3
    =>Idс
    3
    =>Iddc
    1
    =>cddc
    Цепочка росла справа налево, так как грамматика левосторонняя.
    Построим автомат:
    V
    т
    = {с, d}
    V
    n
    ={I, Z}
    I
    R = {IZc,
    - правило 1
    IIc,
    - правило 2
    A
    B x

    IId,
    - правило 3
    ZE}
    - правило 4
    Z - конечная вершина
    Это левосторонняя грамматика.
    Автомат является недетерминированным, так как из I под воздействием с у нас два перехода - из IZ; II.
    Переведем в правостороннюю грамматику:
    V
    т
    = {с, d}
    V
    n
    ={I, Z}
    I
    R = {IсZ,
    - правило 1
    ZсZ,
    - правило 2
    ZZd,
    - правило 3
    ZE}
    - правило 4
    Утверждение.
    Для каждой левосторонней автоматной грамматики можно построить эквивалентную ей правостороннюю автоматную грамматику.
    Для доказательства этого утверждения необходимо построить для каждой из них конечный автомат, из рассмотрения которых будет видно, что для перехода от одного автомата к другому надо поменять местами начальную и конечную вершины и изменить направление всех дуг на противоположные.
    Построение грамматики по заданному конечному автомату
    Пусть задан автомат в виде формировании предыстории, без выходного преобразователя.
    A=
    0
    , φ>
    Чтобы построить грамматику, порождающую язык, допускаемый заданным автоматом, надо:
    V
    т
    = P - поставить в соответствие алфавиту терминальных символов входного алфавита.
    V
    n
    = S - алфавит нетерминальных символов – алфавит состояний.
    I = s
    0
    I
    Z c
    c d
    I
    Z c
    c d

    Получаем правила из функции возбуждения.
    Следовательно, s i
     s j
    V
    т
    = {0,1}
    V
    n
    ={I, A, B}
    I
    R = { I0I;
    I1A;
    A0A;
    A1B;
    B0B;
    B1I}
    В результате преобразования видно, что между автоматными грамматиками и автоматами существует взаимно-однозначное соответствие, следовательно, грамматику можно рассматривать как форму представления конечного автомата.
    Недетерминированные конечные автоматы
    Пусть A
    0
    – недетерминированный конечный автомат.
    A
    0
    =
    0
    , S
    0
    , s
    0 0
    , φ
    0
    , F
    0
    >
    F
    0
    – множество конечных состояний автомата.
    S = {S
    0
    , S
    1
    , S
    2
    }
    M(S) = {{S
    0
    }, {S
    1
    }, {S
    2
    }, {S
    0
    , S
    1
    }, {S
    0
    , S
    2
    }, {S
    1
    , S
    2
    }, {S
    0
    , S
    1,
    S
    2
    }} – множество всех подмножеств множества S.
    φ: P*SS – детерминированный алфавит.
    φ
    0
    : P
    0
    *S
    0
    M(S) - недетерминированный автомат.
    Отличие недетерминированного автомата от детерминированного состоит в том, что функции перехода может определять не одно состояние, в которое переходит автомат, а некоторое подмножество состояний.
    ТЕОРЕМА: Если L(A
    0
    ) – язык, который допускается некоторым конечным автоматом A
    0
    , то существует детерминированный конечный автомат A, который допускает этот же язык.
    Преобразование недетерминированного автомата в детерминированный
    Имеется два способа:
    1. Общий способ
    Пример.
    S
    i
    S
    j b
    I
    A
    1
    B
    1 1
    0 0
    0

    P = {a, b}
    S = {I, B, C}
    M(S)={[I], [B], [C], [IB], [IC], [BC], [IBC], 0}
    Построение функций возбуждения:
    φ(I, a) = [I, c]
    φ(I, b) = [B]
    φ(B, a) = [C]
    φ(B, b) = [0]
    φ(C, a) = [B]
    φ(C, b) = [B]
    φ(IB, a) = [IC]
    φ(IB, b) = [B]
    φ(IC, a) = [IBC]
    φ(IC, b) = [B]
    φ(BC, a) = [BC]
    φ(BC, b) = [B]
    φ(IBC, a) = [IBC]
    φ(IBC, b) = [B]
    Вершины IB и BC являются недостижимыми => исключаем их из рассмотрения.
    Вершина 0 – тупиковое состояние => его также исключаем из рассмотрения.
    Получаем детерминированный автомат:
    I
    B b
    С b
    a a
    a a
    I
    IBC
    IC
    B
    IB
    0
    C
    BC b b b b b b b a a a a a a a

    Это общий способ построения автомата, так как мы рассматривали все подмножества S.
    Но при большом S число этих подмножеств велико.
    2. Сокращенный способ.
    В этом способе будем рассматривать только те переходы из подмножеств, в которые существует переход. a) Строится заготовка таблицы переходов детерминированного конечного автомата. b) В качестве начального состояния выбирается начальное состояние недетерминированного автомата. Для него строим подмножество состояний, в которое переходим из начального. Строку заносим в заготовку таблицы переходов. c) Если полученное подмножество состояний или состояния отсутствуют в левой части таблицы переходов, то они заносятся туда и осуществляется переход к пункту b. d) Процесс заканчивается если в результате получения подмножества, мы не получаем новое подмножество, которое создается в левом столбце.
    Пример.
    P
    i
    / S
    i a b
    I
    IC
    B
    IC
    IBС
    B
    B
    C
    ---
    IBC
    IBС
    B
    C
    B
    B
    I
    IBC
    IC
    B
    C a a a b b a a b
    I
    B b
    С b
    a a
    a a

    Преобразование некоторых типов грамматики к автоматному ввиду
    Утверждение: любой конечный язык, не содержащий пустой цепочки является автоматным языком, следовательно, существует автоматная грамматика, порождающая данный язык.
    Для доказательства данного утверждения рассмотрим следующий способ построения автоматной грамматики, порождающий данный язык.
    Пусть задан язык:
    L = {x
    1
    x
    2
    x
    3
    …x n
    }, где x i
    € V
    t
    *
    - цепочки языка. x
    i
    = a
    1
    a
    2
    a
    3
    …a m
    – последовательность символов, где a i
    € V
    t
    Тогда для порождения конкретной цепочки x i
    введем следующие нетерминальные символы A
    1
    , A
    2
    ,…, A
    m-1
    , тогда запишем:
    X
    i
     a
    1
    A
    1
    A
    1
     a
    2
    A
    2

    A
    m-2
    a m-1
    A
    m-1
    A
    m-1
    a m
    Применяя данную процедуру по всем цепочкам x i
    , получим множество порождающих правил автоматной грамматики, соответствующих исходному языку.
    Рассмотрим приведение контекстно-свободные грамматики к автоматному виду.
    Определение.
    Контекстно-свободная грамматика является левосторонней
    (правосторонней), если все правила ее только левосторонние (правосторонние), или являются заключительными.
    Правила вида:
    A  xB – правосторонняя грамматика, где A, B

    V
    N
    – нетерминальные символы.
    A  Bx – левосторонняя грамматика.
    A  x – заключительное правило.
    Утверждение. Для любой правосторонней или левосторонней грамматики может быть построена эквивалентная ей правосторонняя или левосторонняя автоматная грамматика.
    Доказательство:
    Пусть задана правосторонняя грамматика:
    G: t
    , V
    n
    , I, R>
    R: A  xB , где x € V
    t
    *
    Предположим, что x i
    = a
    1
    a
    2
    …a m
    введем нетерминальные символы A
    1
    A2…A
    m-1
    и добавим правила:
    I
    B b
    С b
    a
    С
    IСB b
    a a
    a, b

    A  a
    1
    A
    1
    A
    1
    a
    2
    A
    2
    A
    m-1
    a m-1
    A
    m-1
    A
    m-1
     a m
    B, либо A
    m-1
     a m
    Цепочка правил, заканчивающаяся A
    m-1
     a m
    B заменит одно правило A  xB. Цепочка правил, заканчивающаяся A
    m-1
     a m
    заменит правило A  x
    Применяя данную процедуру для каждого правила праволинейной грамматики, получим автоматную грамматику.
    Утверждение. Если контекстно-свободная грамматика содержит правила вида AB, где
    A, B

    V
    N
    , то ее можно привести к автоматному виду.
    Такая грамматика может быть преобразована в контекстно-свободную грамматику, не содержащую таких правил.
    Доказательство.
    Пусть есть правила вида:
    R = {…AB…BCx}
    В этом случае вывод любой цепочки, содержащий нетерминальный символ A, осуществляется следующим образом:
    Пусть есть цепочка:
    ώ=>ξ
    1
    A ξ
    2
    , тогда данная цепочка преобразуется в конечную следующим образом:
    ξ
    1
    A ξ
    2
    => ξ
    1
    B ξ
    2
    => ξ
    1
    Cx ξ
    2
    Что равносильно A => Cx.
    Пусть есть правила вида:
    R = {A
    1
    A
    2
    …A
    n
    Z}
    То если есть цепочка вида:
    ώ=>ξ
    1
    A ξ
    2
    , тогда данная цепочка преобразуется в конечную следующим образом:
    ξ
    1
    A
    1
    ξ
    2
    =>…=> ξ
    1
    A
    n
    ξ
    2
    => ξ
    1
    Z ξ
    2
    Или проще: A
    1
    => Z
    Алгоритм получения правил, не содержащих правил вывода
    нетерминальных символов.
    Пусть существует грамматика с множеством правил, которые можно разбить на подмножества, например:
    1)
    Грамматика имеет набор правил R. Разобьем его на R
    1
    и R
    2
    Причем: в R
    1
    будут входить только правила типа A  B , где A,B € V
    n в R
    2
    будут входить только правила автоматной грамматики A  xB , A  x
    2)
    Для каждого правила из множества R
    1
    , содержащего символ A
    i в левой части, построим множество правил S(A
    i
    ) следующим образом,
    Если из A
    i выводится символ A
    n
    (A
    i
    => A
    n
    ), а из A
    n
    =>ηB , то в S(A
    i
    ) включаем правило вида A
    i
     ηB.
    3)
    Проделывая эту процедуру для каждого символа A
    i
    , получаем множество правил:
    R = U
    i=1
    k
    S(A
    i
    ) v R
    i где k – число нетерминальных символов, находящихся слева в правилах набора R подмножества.
    Построение грамматики будет автоматной и эквивалентно исходной.
    Пример.
    G:
    R = {IaM, MA, AaA, AB, BbB, Bb}

    V
    t
    = {a , b}
    V
    n
    = {I , M , A , B}
    R
    1
    = {M  A , A  B}
    R
    2
    = {I  aM , A  aA, B  bB , B  b}
    S(M) = {MaA , M  bB , M  b}
    S(A) = {A  bB , A  b}
    R = {M  aA , M  bB , M  b , A bB , A b , I  aM , A  aA , B  bB , B  b}
    Контекстно-свободная грамматика может быть преобразована в автоматную, если она правосторонняя или левосторонняя и содержит правила нетерминал-нетерминал.
    Контекстно-свободная грамматика не может быть преобразована в автоматную, если:
    1) Содержит одновременно левосторонние и правлосторонние правила.
    2) Содержит правила с самовосстановлением (A  φAψ , φ,ψ € V
    *
    - любые символы, причем не пустые).
    Если грамматика порождает не пустой язык, то в общем случае можно построить эквивалентную ей автоматную грамматику, для этого нужно получить язык, затем построить автоматную грамматику.
    Построение распознавателей и преобразователей
    Распознаватель – это автомат, у которого нет выходного. Он определяет, является ли заданная цепочка допустимой для автомата.
    Преобразователь – это полный автомат, имеющий выходной преобразователь, т.е. у него кроме входного есть выходной алфавит и функция выхода.
    Синтаксический преобразователь позволяет решать задачу синтаксического анализа, так как его выходная последовательность (цепочка), есть синтаксический разбор заданной входной цепочки.
    Построение распознавателей
    Пример.
    Построить распознаватель из множества слов двоичного алфавита длиной в три буквы, слова с двумя единицами, т.е. цепочек из «0» и «1» длиной три.
    V
    t
    = {0, 1}
    L = {011, 101, 110}
    V
    n
    = {I, A, B, C, D, Z, E}
    I 0A 1C 1Z
    I 1B 0D 1Z
    I 1B 1E 0Z

    R = {I0A, I1B , A1C , B0D , B1E , C1Z , D1Z , E0Z , ZE}
    Пример.
    Построим распознаватель для представленной задачи обнаружения допустимых и недопустимых слов.
    Введем два конечных состояния Z
    1
    для допустимых слов и Z
    2
    для недопустимых слов.
    I 0 A 1 C 1 Z
    1
    I 1 B 0 D 1 Z
    1
    I 0 A 0 F 0 Z
    2
    I 0 A 0 F 1 Z
    2
    I 0 A 1 C 0 Z
    2
    I 1 B 0 D 0 Z
    2
    I 1 B 1 E 0 Z
    1
    I 1 B 1 E 1 Z
    2
    P = {0, 1}
    V
    n
    = {I, A, C, Z
    1,
    Z
    2
    , B, D, E, F } = S
    Где E – пустой символ.
    I
    1
    A
    B
    D
    E
    Z
    C
    0 0
    0 1
    1 1
    1
    I
    1
    A
    B
    D
    E
    Z
    2
    Z
    1 0
    0 1
    1 1
    1
    С
    F
    0 0
    0,1 0
    1 0

    Алгоритм построения преобразователя.
    Построение преобразователя для выполнения синтаксического разбора. Преобразование, выполняя синтаксический разбор цепочки, выдает номера правил следующий его выходной алфавит представляет собой множество номеров правил.
    Пусть задана автоматная грамматика:
    Задана цепочка G = T
    , V
    N
    , I, R>
    T = {P, S, s
    0
    , W, φ, ψ}
    P , S , W – алфавит входных состояний и выходов. s
    0
    – начальное состояние.
    φ , ψ – функции переходов и выходов.
    P = W
    T
    / e
    S = V
    N
    s
    0
    = I
    φ , ψ  R
    Для построения преобразователя необходимо:
    1) По заданной грамматике cтроится распознаватель.
    2) В качестве выходного алфавита использовать номера правил грамматики.
    3) Строится множество функций выходов преобразователя. Для каждого правила с номером m вида A m
     bC, где A, C € V
    N и b € V
    T
    построить фрагмент:
    Пример.
    G:
    V
    T
    = {a, b, c}
    V
    N
    = {I, A, B}
    I
    R = {I aA, A  aA, A bB, B  bB, Bc, (B cZ, Z  E)}
    Построим распознаватель.
    W = {1, 2, 3, 4, 5} – выходной алфавит.
    Если подать на вход aabbbc, то получим синтаксический разбор [1 , 2 , 3 , 4 , 4, 5].
    A
    C b/m
    I
    A a / 1
    B
    Z a / 5
    b / 3
    a / 2
    b / 4


    написать администратору сайта