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

  • Основное применение ФГ

  • Опр. Длиной цепочки w называется число составляющих ее символов (обозначается | w|

  • Опр. Если х - слово и п ∈ N, то через х п обозначается слово х ⋅ х ⋅ ... ⋅ x . По определению х Пример.

  • Опр. Через |w|a обозначается количество вхождений символа а в слово Пример. Если V = {a,b,c} , то аи. Опр. Формальный язык

  • Опр. Грамматика

  • Контекстно-свободные грамматики и языки

  • Лекции по теории автоматов - 2. Теория формальных грамматик (ФГ) дает способы задания входных данных способы задания и генерации выходных данных способы задания функции, алгоритма преобразования входных данных в выходные способы анализа входных данных и др. Основное применение фг


    Скачать 1.45 Mb.
    НазваниеТеория формальных грамматик (ФГ) дает способы задания входных данных способы задания и генерации выходных данных способы задания функции, алгоритма преобразования входных данных в выходные способы анализа входных данных и др. Основное применение фг
    АнкорЛекции по теории автоматов - 2.pdf
    Дата12.04.2018
    Размер1.45 Mb.
    Формат файлаpdf
    Имя файлаЛекции по теории автоматов - 2.pdf
    ТипДокументы
    #15721
    страница1 из 6
      1   2   3   4   5   6
    Теория автоматов Часть Формальные грамматики и языки. Применение. Основные понятия и определения
    Теория формальных грамматик (ФГ) дает
    - способы задания входных данных
    - способы задания и генерации выходных данных
    - способы задания функции, алгоритма преобразования входных данных в выходные
    - способы анализа входных данных и др.
    Основное применение ФГ:
    - разработка собственных компиляторов
    - разработка переводчиков
    - преобразование строк, массивов
    - разработка поисковых запросов.
    Опр. Алфавит V - конечное непустое множество элементов, называемых символами
    (буквами).
    Опр. Цепочкой a в алфавите V называется любая конечная последовательность символов этого алфавита.
    Пример. Пусть алфавит V = {a,b,c}. Тогда baaa является словом в алфавите V.
    Опр. Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается ε(λ).
    Опр. Длиной цепочки w называется число составляющих ее символов (обозначается
    |w|
    ), причём каждый символ считается столько раз, сколько раз он встречается в Пример. Очевидно, |baaa| = 4 и |ε| = Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку ε, а через V
    +
    - множество, содержащее все цепочки в алфавите V, исключая пустую цепочку Пример. Пусть V = {1,0}, тогда V* = ,0,l,00,01,10,11,000,...}, а V
    +
    ={0,1,00,01,10,11,000,...}.
    Опр. Если хи у - слова в алфавите V, то слово ху результат приписывания слова у вконец словах) называется конкатенацией (катенацией, сцеплением) слов хи у. Иногда конкатенацию слов хи у обозначают х у.
    Опр. Если х - слово и п
    ∈ N, то через х
    п
    обозначается слово х
    ⋅ х ⋅ ... x. По определению х Пример. ba
    3
    = bааа и (ba)
    3
    = bababa.

    Опр. Говорят, что слово х - префикс (начало) слова у, если у = хи.

    Опр. Говорят, что слово х - суффикс (конец) слова у, если у = их.
    Опр. Говорят, что слово х — подслово слова у, если у = uxv для некоторых слови и v.
    Опр. Через |w|
    a обозначается количество вхождений символа а в слово Пример. Если V = {a,b,c}, то аи.
    Опр. Формальный язык – это множество конечных слов (строк, цепочек) над конечным алфавитом V. Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения, разности и дополнения языков, заданных над одними тем же алфавитом (обозначения L
    1
    ∪ L
    2
    , L
    1
    ∩ L
    2
    , L
    1
    — Пример. Множество {a, abb} является языком над алфавитом Пример. Множество {a
    k
    ba
    l
    | k
    ≤ l} является языком над алфавитом {a,b}. Необходимо различать пустой языки язык, содержащий только пустую цепочку L={ε}≠0.
    Опр. Пусть L – язык над алфавитом V*. Тогда язык V* — L называется дополнением языка L относительно алфавита V. Когда из контекста ясно, о каком алфавите идёт речь, говорят просто, что язык V* — L является дополнением языка L.
    Опр. Грамматика – система правил, предназначенная для задания множества цепочек и символов данного алфавита. G – грамматика L(G) – язык этой грамматики. Выделяют 3 группы формальных грамматик
    1. Порождающие (позволяют строить правильную цепочку в заданном алфавите сопи- санием ее строения и не позволяют строить ни одной неправильной цепочки.
    2. Распознающие (позволяют определить к каждой входной цепочке является ли она правильной в случае положительного ответа распознающая ФГ выдает строение цепочки. Преобразующие (для каждой правильно построенной цепочки способны построить ее отображение в виде другой цепочки и вывести информацию о порядке проведения изображения.
    Способы описания языков Конечный язык можно описать простым перечислением его цепочек. Поскольку формальный язык может быть и бесконечным, требуются механизмы, позволяющие конечным образом представлять бесконечные языки. Можно выделить два основных подхода для такого представления механизм распознавания и механизм порождения (генерации).
    Механизм распознавания (распознаватель, по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом дате. допускает цепочку иначе – останавливается с ответом нет или зацикливается. Язык, определяемый распознавателем – это множество всех цепочек, которые он допускает.
    Примеры распознавателей Машина Тьюринга
    (МТ). Язык, который можно задать с помощью МТ, называется рекурсивно перечислимым. Вместо МТ можно использовать эквивалентные алгоритмические схемы нормальный алгоритм Маркова (НАМ, машину Поста и др. Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лента не бесконечна, а ограничена длиной входного слова. Определяет контекстно-зависимые языки. Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, головка не может изменять входное слово и не может сдвигаться влево имеется дополнительная бесконечная память (магазин, или стек, работающая по дисциплине LIFO. Определяет контекстно-свободные языки. Конечный автомат (КА. Отличается от МП-автомата отсутствием магазина. Определяет регулярные языки. Основной способ реализации механизма порождения — использование порождающих грамматик, которые иногда называют грамматиками Хомского. Порождающие
    ФГ являются наиболее важными и распространенными. Порождающей ФГ
    называется четверка вида G = (V
    T
    ,V
    N
    ,P,S), где V
    N
    - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы
    - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), V
    T
    V
    N
    =0; Р - множество правил вывода грамматики элемент (α,β) множества Р называется правилом вывода и записывается в виде α→β (читается из цепочки α выводится цепочка
    β»)
    S - начальный символ грамматики, S V
    N
    . Для записи правил вывода с одинаковыми левыми частями вида α→β1, α→β2,…,α→βn используется сокращенная форма записи Пример. Грамматика G1=({0, 1}, {A, S}, Р, S), где множество Р
    1
    состоит из правил вида 1) S→0A1; 2) 0А→00А1; А.
    Опр. Цепочка β∈ (V
    T
    V
    N
    )* непосредственно выводима из цепочки в грамматике G = (V
    T
    ,V
    N
    ,P,S) обозначается α⇒β), если α=ξ
    1
    γξ
    2 и β=ξ
    1
    δξ
    2
    , где ξ
    1
    ,
    ξ
    2
    ,
    δ ∈
    V*, γ∈V
    + и правило вывода γ→δ содержится во множестве Р

    Опр. Цепочка β∈V* выводима из цепочки α∈V
    + в грамматике G =(V
    T
    ,V
    N
    ,P,S) обозначается, если существует последовательность цепочек γ0,γ1,…,γn (n≥0) такая, что Пример. В грамматике G
    1
    S=>*000111, т.к. существует вывод S => А А =>
    000A111 => 000111.
    Опр. Языком, порожденным грамматикой = (V

    T
    , V
    N
    ,P,S), называется множество всех цепочек в алфавите V
    T
    , которые выводимы изначального символа грамматики S с помощью правил множества Рте. множество L(G)= {αV* Пример. Для грамматики G
    1
    L(G1)={0
    n
    1
    n
    | п>0}.
    Опр. Цепочка α∈V*, для которой существует вывод S*α, называется сентенциальной формой в грамматике G = (V
    T
    , V
    N
    ,P, S).
    Опр. Грамматики G
    1 и G
    2 называются эквивалентными, если L(G
    1
    ) Пример. Для грамматики G
    1 эквивалентной будет грамматика G2 =({0, 1}, {S}, Р, S), где множество правил вывода Р содержит правила вида S→0S1|01.
    Классификация грамматики языков по Хомскому
    Правила порождающих грамматик позволяют осуществлять преобразования строк. Ограничения на виды правил позволяют выделить классы грамматик. Рассмотрим классификацию, которую предложил Н. Хомский.
    Тип 0. формальные грамматики с фразовой структурой, неограниченные. Грамматика) называется грамматикой типа 0, если на ее правила вывода не накладывается никаких ограничений, кроме тех, которые указаны в определении грамматики. Любое правило α→β может быть построено с использованием произвольных цепочек α, β∈(V
    T
    ∪V
    N
    ). Этот тип грамматик самый общий, включающий все грамматики. Однако некоторые грамматики могут принадлежать только к этому типу. Практического применения в силу своей сложности такие грамматики не имеют. Например
    P = TR→HT или Тип 1.
    (контекстно-зависимые, контекстные грамматики, грамматика непосредственно составляющих, НС-грамматика). К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Грамматика G = (V
    T
    ,V
    N
    ,P,S) называется контекстно-зависимой грамматикой (КЗ- грамматикой, если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α,
    β∈V*, γ∈V
    +
    , A∈V
    N
    . Грамматика G = (V
    T
    ,V
    N
    ,P,S) называется неукорачивающий грамматикой, если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V
    +
    , и
    |A|<=|γ|. Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.
    Тип 2. (Контекстно-свободной грамматикой, КС-грамматикой, бесконтекстной грамматикой. Грамматика G = (V
    T
    ,V
    N
    ,P,S) называется контекстно-свободной грамматикой
    (КС-грамматикой), если ее правила вывода имеют вид A→β, где β∈V+ (для неукора- чивающих КС-грамматик, β∈V* для укорачивающих, A∈V
    N
    . То есть грамматика допускает появление в левой части правила только нетерминального символа. КС- грамматики широко применяются для описания синтаксиса компьютерных языков
    (программирования).
    Тип 3. регулярная, Р-грамматика, линейная. К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, нос ограниченными возможностями. Все регулярные грамматики могут быть разделены на два эквивалентных класса Грамматика G = (V
    T
    , V
    N
    , Р, S) называется праволинейной, если ее правила вывода имеют вид A→γB или A→γ, где γ∈V
    T
    *, A, Грамматика G = (V
    T
    , V
    N
    , Р, S) называется леволинейной, если ее правила вывода имеют вид A→Bγ или A→γ, где γ∈V
    T
    *, A, Регулярные грамматики применяются для описания простейших конструкций идентификаторов, строк, константа также языков ассемблера, командных процессоров и др

    Контекстно-свободные грамматики и языки
    КС грамматики широко используются в практике программирования как способ задания формализованных языков. КС грамматики способны выразить большую часть синтаксиса языков программирования. Применяются также при описании языков
    HTML, XML
    , языка описания документов DTD и других. Определение. Язык называется контекстно-свободным, если существует кон- текстно-свободная грамматика, его порождающая. Пример Возьмем язык палиндромов. Это цепочки символов, читающиеся одинаково справа и слева.
    otto madam madamimadam Для упрощения рассмотрим палиндромы в алфавите {0, 1}.
    00100 10101 Выразим определение языка палиндромов в виде КС-грамматики: Первые три правила говорят, что язык палиндромов включает цепочки из пустых символов, 0 и 1. Четвертое и пятое правила – если взять произвольную цепочку w
    из языка Р, то 0w0 и 1w1 также будут в языке Р
    Эти 4 компонента образуют КС-грамматику. Будем представлять КС-грамматику в виде где V – множество переменных, T – терминалов, P – правил вывода, S – стартовый символ. Пример 1.
    G
    pal
    = ({P}, {0, 1}, A, P) где А – вышеприведенные правила вывода. Грамматика G
    pal порождает цепочки языка палиндромов 10101, 01010, 0110, Выведем первую цепочку с помощью грамматики палиндромов
    P
    → 1P1 → 10P01 → 10101
    Пример 2. Допустим язык выражений типичного языка программирования состоит из идентификаторов, которые начинаются с буквы a или b, за которой следует цепочка {a,b,0,1} и арифметических операторов + и * .
    ( a + b ) * ( a + b + a0 + a1 ) Введем для грамматики 2 переменные Е – выражения языка, стартовый символ – идентификаторы языка
    G
    выр
    = (Е, I}, {a, b, 0, 1, +, *}, A, E) где A = { E→I | E+E | E*E | (E), I→a | b | Ia | Ib | I0 | I1 } Упрощенная запись грамматики
    G
    выр
    = { E→I | E+E | E*E | (E), I→a | b | Ia | Ib | I0 | I1 } Теперь рассмотрим, как выводится из построенной грамматики вышеуказанная цепочка
    ( a + b ) * ( a + b + a0 + a1 )
    E → E*E → (E)*(E) → (E+E)*(E+E) → (I+I)*(E+E+E+E) → (a+b)*(I+I+I+I) →
    → (a+b)*(a+b+I0+I1) → (a+b)*(a+b+a0+a1) Вывод в КС-грамматике удобно представлять с помощью дерева вывода. Закрепление материала
    1. Составить последовательность вывода цепочки 101101 из грамматики палиндромов.
    2. Составить последовательность вывода цепочки (a+b0)*a0+b из грамматики выражений
    Дерево вывода и неоднозначность грамматик
    Определение. Деревом вывода цепочки w ϵ Т в грамматике G = (V, T, P, S) называется упорядоченное дерево, узлы которого помечены символами из множеств V, T так, что корень дерева помечен аксиомой (стартовым символом, внутренние узлы – нетер- миналами, а листья – терминалами. Пример. Построим дерево вывода цепочки ( a + b ) * ( a + b + a0 + a1 ) из грамматики выражений. Корень дерева Е, внутренние узлы E и I, листья – заданная цепочка. Начнем с умножения выражений в скобках, затем перейдем к сложению внутри скобок.
    Если обойти все листья дерева слева направо, то получим в точности выводимую цепочку. Основная роль дерева вывода состоит в том, что оно связывает синтаксис и семантику (смысл) выводимой цепочки. Например, семантика естественного языка – смысл фразы, а для компьютерной программы – это алгоритм решения задачи. Чтобы сохранить семантику языковой цепочки, грамматика и дерево вывода должны быть однозначны) ЕЕ ЕЕ+ ЕЕ+ ЕЕ+ ЕЕ a
    Определение. Грамматика называется однозначной, если каждая цепочка выводимого языка представляется единственным деревом вывода, и неоднозначной, если найдется цепочка, представленная двумя различными деревьями вывода. Неоднозначность – отрицательное свойство грамматики. Если программа кодирует 2 различные последовательности машинных инструкций, то одна из них наверняка реализует не тот алгоритм. Пример. Грамматика G = {E→E+E | E*E | 0 | 1 | … | 9} является неоднозначной, т. к. цепочка 4+2*3 имеет 2 дерева вывода:
    Дерево а показывает, что сложение должно применяться к результату умножения
    4+(2*3)=10, а дерево б - в умножении участвует результат сложения (4+2)*3=18. Неоднозначность данной грамматики приводит к невозможности однозначно определить значение выражения, и следовательно, к непригодности данной грамматики для порождения арифметических выражений. Аналогичная грамматика GA
    1
    = {E
    →E+E | E*E | (E) | x} также является неоднозначной, т. к. отсутствует порядок (приоритет) выполнения операций. Эта грамматика порождает и правильную и неправильную цепочки арифметических выражений Е → E*E → (Е)*х → (х → (х+х)*х Е → E+E → х+(Е) → х+(Е*Е) → х+(х*х) Для устранения неоднозначности уточним грамматику согласно определению арифметического выражения арифметическое выражение – это сумма одного или более слагаемых, каждое из которых произведение одного или более множителей, каждый из которых есть буквах или арифметическое выражение в скобках. Введем дополнительно нетерминал Т для слагаемых и нетерминал «F» для множителей Попробуем вывести правильную и неправильную цепочки
    Е → ТЕТ Т+Т*F → F+F*x → х+х*х Неправильную цепочку породить не удалось, вместо нее породили правильную, без скобок. Второй пример уточнения грамматики. Язык двоичных чисел порождается грамматикой
    GN
    1
    = { S
    → L | .L | L.L, L→ LB | B, B→ 0 | 1 } Породим число 6,75 (10) или 0110.1100 (2)
    S
    → L.L → LB.LB → LB0.LB0 → LB10.LB00 → B110.B100 → 0110.1100 Данная грамматика порождает неправильные цепочки, начинающиеся и заканчивающиеся нулем. Если целая часть всегда начинается единицей, а дробная единицей заканчивается, то вводим нетерминал «R», обозначающий правую часть числа и уточняем правила вывода левой и правой части
    GN
    2
    = { S
    → L | .R | L.R, L→ L0 | L1 | 1, R→ 0R | 1R | 1 }
    S
    → L.R → L0.1R → L10.11 → Закрепление материала. Составить деревья вывода правильной и неправильной цепочек из грамматики
    GA
    1
    = {E
    →E+E | E*E | (E) | x}
    2. Составить деревья вывода правильной и неправильной цепочек из грамматики
    GA
    2
    = { E
    → E+T | T, T→ T*F | F, F→ (E) | x Выведем неправильную цепочку x+(x*x)
    :
    E
    → E+T → T+F → F+(E) → x+(T) → x+(T*F) → x+(F*x) → Грамматика все же порождает неправильную цепочку. Необходимо еще уточнить. В скобках может быть только сумма.
    GA
    2
    = { E
    → E+T | T, T→ T*F | F, F→ (E+T) | x Проверим
    E
    → E+T → T+T*F → F+F*x → Теперь грамматика не порождает неправильных цепочек
    Применение КС-грамматик
    В описании языка гипертекстовых ссылок HTML применяется КС-грамматика:
    Рассмотрим вывод цепочки языка HTML, соответствующего тексту:
    Вещи, которые я люблю
    1. Бананы.
    2. Людей общительных, ответственных

    Element

    Doc →
    Element Doc →
    Text Element Doc →
    Char Text DocElement Doc → В Char Text Element Doc
      List
    Doc → В Char Text Text
      Listitem List

    Вeщ Char Text Char Text
    1. Doc Listitem

    Вeщи Char Text л Char Text
    1. Element Doc
    2. Doc

    Вeщи, Char Text лю Char Text
    1. Text Doc
    2. Element Doc

    Вeщи, Char Text люб Char Text
    1. Char Text
    2. Text

    Вeщи, к Char Text любл Char Text
    1. Б Char Text
    2. Char Text
    → Вещи, которые я люблю
      Бананы. Людей общительных, ответственных.
    Закрепление материала составить последовательность вывода цепочки языка HTML, соответствующего тексту Мне нравится весна
    1) травой зеленой
    2) теплым солнцем.
    КС-грамматики часто используются в описании языков программирования. В этом случае грамматики записываются в определенных формах (метаязыках. Рассмотрим наиболее применимые из них – формы Бэкуса-Наура.

      1   2   3   4   5   6
    написать администратору сайта