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

  • 3.2. Контекстно-зависимые грамматики

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

    		•

    Карпов. СодержаниеПредислови Конечные автоматы


    Скачать 1.07 Mb.
    НазваниеСодержаниеПредислови Конечные автоматы
    АнкорКарпов.pdf
    Дата18.03.2019
    Размер1.07 Mb.
    Формат файлаpdf
    Имя файлаКарпов.pdf
    ТипДокументы
    #26044
    страница3 из 7
    1   2   3   4   5   6   7
    2.3. Лексические анализаторы
    2.3.1. Постройте регулярное выражение и детерминированный конечный автомат для распознавания комментариев в языке Паскаль.
    2.3.2. Целые константы без знака в языке Си определяются так:
    - десятичные: <последовательность цифр, начинающаяся не с нуля>
    - восьмеричные: 0 <последовательность цифр>
    - шестнадцатеричные: 0 {x, X} <последовательность цифр и букв a-f или A-F>
    Постройте синтаксическую диаграмму распознавателя и транслятор этого языка.
    2.3.3. Комментарий в языке Си определяется как любая символьная цепочка между скобками
    /* и */, а также любой текст от пары символов // до конца строки. Постройте детерминированный конечный автомат, синтаксическую диаграмму распознавателя и транслятор, выбрасывающий комментарии в языке Си.
    2.3.4. Постройте блок лексического анализатора, обрабатывающий цепочки языка вещественных констант: т.е. по входной строке записывающий в таблицу констант значение очередной константы и выдающий тип лексемы (const) и ее номер в таблице констант.
    Примеры цепочек языка: +92.009, .345, -.002, -23Е-07, .1е+3, 2301.2.
    2.3.5. Постройте синтаксическую диаграмму и семантические действия лексического анализатора для расширения языка Милан возможностью включения комментариев вида /* < тело комментария> */ и // < тело комментария>. Во втором случае комментарий продолжается до конца строки.
    2.3.6. Постройте синтаксическую диаграмму и семантические действия лексического анализатора для языка Милан++, пример программы на котором приведен ниже: begin read x, y12; /* ввод операндов */ loop x != y12 -> /* выполнять до равенства аргументов */ case x > y12 -> x -= y12 or y12 > x -> y12 -= x esac endloop; write (x) /* полученный НОД */ end

    19
    3.
    Иерархия Хомского
    порождающих грамматик
    и языков
    3.1. Порождающие грамматики Хомского
    3.1.1. Постройте различные структуры (сгруппируйте отдельные части) следующих двусмысленных предложений для различных их значений:
    Мать любит дочь;
    Петерстар поглотил Мегафон;
    В Африке бхуту убивают тутси;
    Ножницы для стрижки волос 20 см.
    3.1.2. Постройте различные структуры (сгруппируйте отдельные части) следующих двусмысленных предложений английского языка для различных их значений:
    Fruit flies like banana;
    The spy saw a cop with the binocular;
    I made her duck;
    They are flying planes.
    3.1.3. Сообщение СМИ: “За свои услуги помощник члена Совета федерации Беридзе запросил
    от 150 до 200 тысяч долларов США”. Сколько смыслов у этого предложения? Постройте различные структуры этого предложения, придающие ему различные смыслы.
    3.1.4. Постройте двусмысленную и недвусмысленную грамматики Хомского, порождающие цепочки языка, абстрактно представляющего структуру программ языков высокого уровня.
    Примеры таких цепочек:
    begin int v, v, v; real v; s; s; s; s end
    begin real v, v; real v, v; s; s; s end
    3.1.5. Пусть L1 = {abc, caa} и L2 = {

    , c, ca, caa} - два формальных языка над словарем

    ={a,
    b, c}. Постройте следующие языки: a) L1

    L2; б) L1

    L2; в) L1\L2; г)
    L1 2
    ; д) L1*.
    3.1.6. Пусть грамматика G определяется правилами:
    S

    aAbB
    AbB

    aAbB bBb

    bb
    A

    ε
    S

    AB
    AB

    CBb
    CB

    ABB
    A

    a aB

    a
    S

    AaB
    AaB

    aAaBb aBb

    abb
    A

    ε

    20
    Какому классу по Хомскому она принадлежит? Порождается ли L(G) грамматикой более узкого класса?
    3.1.7. Постройте несколько цепочек языка, порождаемого следующей грамматикой:
    S

    P . | P ; S
    P

    N = E
    E

    E O E | N | { L } | ( E )
    O


    |

    N

    x | y | z | u | v | w
    L

    A | L , A
    A

    a | b | c | d | e | f
    3.1.8. Пусть грамматика G определяется правилами:
    S

    AB
    AB

    aDB
    DB

    ABB
    B

    b
    Ab

    b
    Какому классу (по Хомскому) она принадлежит? Порождается ли L(G) грамматикой более узкого класса?
    3.1.9. Какому классу по Хомскому принадлежит грамматика с правилами:
    S

    ASB | АВ
    AB

    BA
    A

    a
    B

    b
    Какой язык порождает эта грамматика?
    3.1.10. Какому классу по Хомскому принадлежит каждая из перечисленных ниже грамматик:
    S

    AS | ε
    A

    a | b
    S

    AB
    AB

    aABB
    B

    b
    A

    a
    S

    ASB | BSA
    A

    a
    B

    b | ε
    SB

    ε
    S

    AcBs
    A

    AcA | B
    B

    a | b
    S

    abc | aSQ
    bQc

    bbcc
    cQ

    Qc
    S

    ABaC
    Ba

    aaB
    BC

    DC | E
    aD

    Da
    AD

    AB
    aE

    Ea
    AE


    Какой язык порождает каждая грамматика? Порождается ли язык грамматикой более узкого класса?
    3.1.11. Пусть грамматика G определяется правилами:


    |


    | ,


    and

    21


    tom | dick | barry
    Начальным символом грамматики является нетерминал . Какому классу по
    Хомскому принадлежит эта грамматика? Какой язык порождает эта грамматика? Какой наиболее простой грамматикой можно породить этот язык?
    3.1.12. Какому классу по Хомскому принадлежит грамматика упрощенного английского языка с начальным нетерминалом и с правилами:


    |


    | | |



    |


    and | or | but | ...
    < Pronoun >

    me | you | I | it | she | ...
    < Verb >

    is | see | sees | love | loves | feel | go | carry | went | kill | ...
    < Name >

    John | Mary | Boston | ...
    < Article >

    a | an | the
    < Noun >

    agent | wumpus | gold | nothing | ... . а) Постройте вывод в этой грамматике предложения: I love Mary but Mary loves the gold. б)
    Приведите примеры предложений, которые порождаются в этой грамматике, но не являются предложениями английского языка.
    3.1.13. Одна из возможных контекстно-свободных грамматик упрощенного английского языка с начальным нетерминалом имеет следующие правила:





    < Name > |
    |



    |
    < Verb >

    ate | was built by | saw | was seen by | lay in | crashed | ...
    < Name >

    Jack | Mary | Peter | ...
    < Article >

    a | an | the
    < Noun >

    house | cheese | rat | horse | cat | ...
    Постройте в этой грамматике деревья вывода следующих предложений английского языка: а) the house the cheese lay in was built by Jack.
    б) the house the cheese the rat saw lay in was seen by Mary.
    в) the house the cheese the rat the cat Jack chased caught ate lay in crashed.
    3.1.14. В соответствии с грамматикой языка Милан:
    Prog

    begin L end
    L

    S | L;S
    S

    i := E | if B then L else L | if B then L | while B do L | output (E)
    E

    E ots E | E otm E | ( E ) | i | c
    B

    E q E последний оператор в списке операторов программы не может заканчиваться „;‟. Измените грамматику Милана так, чтобы точка с запятой могла стоять после любого оператора.
    3.1.15. Сколько различных выводов цепочки baaaab существует в грамматике с правилами:
    S

    bAb

    22
    A

    AA | a
    3.1.16. Постройте порождающую грамматику Хомского для языка {ww | w

    {a, b, c}* }.
    3.1.17. Постройте грамматику Хомского для языка {ww
    R
    | w

    {a, b, c}*, w
    R
    – цепочка, обратная к w }.
    3.1.18. Постройте порождающую грамматику Хомского для языка {a
    n
    b
    n
    c
    n
    | n>0}, а также последовательность подстановок и структуру вывода в этой грамматике цепочки a
    2
    b
    2
    c
    2 3.1.19. Постройте однозначную грамматику Хомского для языка, включающего все такие цепочки из a и b, в которых число вхождений а и число вхождений b совпадают.
    3.1.20*. Постройте порождающую грамматику Хомского для языка {a
    n^2
    | n>0}, содержащего цепочки из символов a длиной 1, 4, 9, 16, ... . Примеры цепочек языка: а, aaaa, aaaaaaaaa, ... .
    Указание. Воспользуйтесь соотношением (n+1)
    2
    = n
    2
    + 2n + 1.
    3.1.21*. Докажите, что для любого конечного словаря существуют языки, которые не могут быть порождены грамматиками Хомского.
    Указание. Проще доказать более общее положение, а именно, что для любого конечного словаря существуют языки, которые не могут быть порождены никаким конечным описанием.
    Действительно, число всех возможных слов (цепочек) над конечным словарем счетно. Любой язык является некоторым подмножеством всех возможных слов над конечным словарем, поэтому множество всех языков, как множество подмножеств счетного множества, имеет мощность континуум. Для решения задачи необходимо только показать, что множество всех возможных конечных описаний над любым конечным словарем счетно, поэтому оно заведомо меньше всех возможных языков.
    3.2. Контекстно-зависимые грамматики
    3.2.1. По грамматике типа 0:
    S

    abc | aSQ
    bQc

    bbcc
    cQ

    Qc постройте контекстно-зависимую грамматику.
    3.2.2. Постройте контекстно-зависимую грамматику, порождающую язык L:
    L={ww| w

    {a, b}* }.
    3.2.3. По следующей контекстно-зависимой грамматике:
    S

    aSA | ε
    AA

    Ac

    23
    aA

    ab постройте эквивалентную контекстно-свободную грамматику.
    3.2. 4. Постройте несколько терминальных цепочек, выводимых в следующей грамматике
    Хомского с терминальным словарем {0, 1}:
    S

    SS | RS
    R

    RR | 0
    RS

    SR
    0S0

    010
    Какой язык порождает эта грамматика? Порождается ли этот язык грамматикой более простого типа?
    3.2.5. Выводима ли цепочка cabbaac в грамматике:
    S

    SS | a | c | A
    B

    bB | b
    aAa

    aBa
    Если да, то постройте вывод этой цепочки.
    3.3. Контекстно-свободные грамматики
    3.3.1. Постройте КС-грамматику с начальным нетерминалом <Книга>, описывающую структуру книги. Указание. Любая книга состоит из содержания, оглавления и нескольких глав. Каждая глава состоит из разделов, разделы – из параграфов, параграфы – из предложений.
    3.3.2. Понятие списка в математике задается следующим рекурсивным определением:
    1. Односимвольная цепочка p является списком.
    2. Если v и w – списки, то цепочки [v] и v;w тоже списки.
    3. Других списков нет. а) Постройте словарь языка списков и КС-грамматику Хомского, порождающую все списки c двумя символами а, b. б) Постройте недвусмысленную КС-грамматику Хомского, порождающую все списки. в) Приведите примеры списков.
    3.3.3. Правильно построенные формулы логики высказываний определяются так: а) любое атомарное высказывание p есть ППФ; б) если

    и

    1 – ППФ, то
    
    и
    
    1 – тоже ППФ; в) других правильно построенных формул логики высказываний нет.
    Постройте КС-грамматику Хомского, порождающую все правильно построенные формулы логики высказываний.

    24 3.3.4. Регулярные выражения над конечным словарем

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

    ,

    - и любое a
    
    - регулярные выражения; б) Если R
    1
    и R
    2
    - регулярные выражения, то регулярными выражениями будут их сумма R
    1
    + R
    2
    ; (знак „+‟, иногда записывают как „|‟) их произведение R
    1
    R
    2
    ; итерация R
    1
    * и урезанная итерация R
    1
    +
    ; в) Скобки ( ) используются для группировки (для задания порядка выполнения операций). г) Других регулярных выражений нет.
    Постройте КС-грамматику Хомского, порождающую все регулярные выражения в алфавите

    ={a, b}.
    3.3.5. Формулы линейной темпоральной логики (LTL) рекурсивно определяются так: а) любой атомарный предикат p является формулой LTL; б) если

    и

    – формулы LTL, то
    
    и
    
    – тоже формулы LTL; в) если

    и

    – формулы LTL, то Х

    и

    U

    – тоже формулы LTL; г) Скобки „(‟ и „)‟ используются для группировки (для задания порядка выполнения операций); д) других формул линейной темпоральной логики нет.
    Постройте КС-грамматику Хомского, порождающую все правильно построенные формулы линейной темпоральной логики.
    3.3.6. Формулы темпоральной логики ветвящегося времени (СTL) рекурсивно определяются так: а) любой атомарный предикат p является формулой СTL; б) если

    и

    – формулы СTL, то
    
    и
    
    1 – тоже формулы СTL; в) если

    и

    – формулы СTL, то AХ

    , ЕХ

    , AF

    , ЕF

    , AG

    , ЕG

    , А(

    U

    ) и E(

    U

    )
    – тоже формулы CTL; г) других формул темпоральной логики ветвящегося времени нет.
    Постройте КС-грамматику Хомского, порождающую все правильно построенные формулы темпоральной логики CTL.
    3.3.7. Правильно построенные формулы логики предикатов определяются на предметной области М так:
    Вводятся символы, которые подразделяются на классы: константы М c1, c2, … переменные М x, y, z, … функциональные символы М f, g, ...
    Вводятся термы как константы, переменные или n-местные функции от термов: c, x, f (t, t, …, t)
    Вводятся атомарные m-местные предикатные символы: Р
    Правильно построенные формулы логики предикатов формально определяются так: любой m-местный атомарный предикатный символ есть ППФ; любые ППФ, связанные логическими операторами – ППФ;
    ППФ, перед которой стоит квантор

    x или

    x, тоже является ППФ.

    25
    Пример правильно построенной формулы логики предикатов:

    x

    y P(x, c, g(y)).
    Постройте КС-грамматику Хомского, порождающую все правильно построенные формулы логики предикатов.
    3.3.8. В КС-грамматике:
    S

    ASB |

    A

    aAS | a | aEb
    B

    SbS | A | bb |

    C

    cC | EdA
    E

    cE | BdС а) освободитесь от бесполезных и циклических продукций; б) освободитесь от

    -правил.
    3.3.9. Освободитесь от бесполезных, пустых и циклических продукций в грамматике:
    S

    0A0 | 1B1 | BB
    A

    C | EaA
    B

    S | A
    C

    S |

    | CE
    E

    CE | aE
    S

    SbAc | adA
    A

    BcS | abc
    B

    Ec | dB
    D

    ccC | DdA|d
    E

    CE
    S

    аA | aBB
    A

    aaA |

    B

    bB | bbC
    C

    B | DdA
    E

    CE
    Какой язык порождает каждая грамматика?
    3.3.10. Освободитесь от

    -продукций в грамматике:
    S

    aSbS
    S

    BaB
    B


    B

    bS какой язык порождает эта грамматика?
    3.3.11. Существуют ли грамматики LL(0)? Если да, то постройте пример такой грамматики.
    3.3.12. Какой язык порождает КС-грамматика:
    {S

    #B#, B

    E=E, B

    i, E

    E+i, E

    i}
    3.3.13. Нетерминал A называется рекурсивным, если существует вывод: A

    *

    A

    с непустой цепочкой
    
    . Можно ли язык {a
    n
    bc
    m
    | n,m>0} задать грамматикой без рекурсивных правил?
    3.3.14. Принадлежит ли цепочка abaababb языку, порождаемому КС-грамматикой с правилами:
    S

    SaSb|ε
    3.3.15. Постройте однозначную КС-грамматику Хомского для языка правильных скобочных выражений.

    26 3.3.16. Следующая КС-грамматика Хомского с начальным символом Lexp-seq, представленная в БНФ-нотации, порождает цепочки упрощенного языка Lisp:
    Lexp-seq ::= Lexp-seq Lexp | Lexp
    Lexp ::= Atom | List
    Atom ::= „number‟ | „identifier‟
    List ::= „(‟ Lexp-seq „)‟
    Постройте дерево вывода цепочки b ( a 23 b ( m a y ) z ) в этой грамматике.
    3.4.17. Следующая КС-грамматика Хомского с начальным символом Stmt, представленная в
    БНФ-нотации, порождает цепочки операторов языка nanoPromela (Process meta language):
    Stmt ::= „skip‟ | „x := expr‟ | „c?x‟ | „c!expr‟ |
    Stmt { „;‟ Stmt } | „atomic’ „{‟ Assignments „}‟ |
    „if :: g

    ‟ Stmt { „:: g

    ‟ Stmt} „fi‟ |
    „do :: g

    ‟ Stmt { „:: g

    ‟ Stmt} „od‟
    Assignments ::= „x := expr‟ { „ ; x := expr‟}
    Постройте несколько цепочек операторов языка nanoPromela.
    3.3.18. Постройте все возможные деревья вывода слова cabbca в следующей грамматике
    Хомского:
    S

    SS | a | c | aBc
    B

    Bb | b
    3.3.19. Грамматика, порождающая арифметические выражения:
    E

    E+E | E-E | E*E | E/E | (E) | i является двусмысленной. Постройте для следующей цепочки все возможные деревья вывода в этой грамматике:
    i * ( i + i – i ) + i
    3.3.20. Постройте левый и правый выводы цепочки abbbb в грамматике:
    G={ S

    aAB, A

    bBb, B

    A |

    }
    3.3.21. Принадлежит ли цепочка ( ( )( )) ( ) языку, порождаемому КС-грамматикой с правилами:
    S

    SA | A
    A

    (S) | ( )
    Постройте канонический левый и канонический правый выводы этой цепочки в грамматике.
    3.3.22. Принадлежит ли цепочка 00011011 языку, порождаемому КС-грамматикой с правилами:
    S

    SS | A
    A

    0A1 | S | 01
    Постройте вывод этой цепочки в грамматике.
    3.3.23. Принадлежит ли цепочка 0111000 языку, порождаемому КС-грамматикой с правилами:

    27
    S

    A0B | B1A
    A

    BB | 0
    B

    AA | 1
    Постройте вывод этой цепочки в грамматике.
    3.3.24. Постройте КС-грамматику, порождающую языки: а) {w

    {a, b}* | |w|
    a
    =2|w|
    b
    }, т.е. язык, в каждом слове которого число символов a вдвое меньше числа символов b. б) { a
    n
    b
    m
    | m

    n+2}. в) {wuw
    R
    | u,w

    {a,b}* }. г) { a
    2

    n
    | n

    0}.
    3.3.25. По грамматике Хомского:
    S

    LDL
    L

    La | Lb | a
    D

    D0 | D1 | 0 | 1 постройте деревья вывода следующих слов: ab10aa, abba0a, a1a. Покажите, что слова ab10,
    b1a, abba не выводимы в этой грамматике. Опишите язык, порождаемый этой грамматикой.
    Существует ли регулярное выражение, задающее тот же язык?
    3.3.26. Постройте дерево вывода цепочки

    = cbcaadcb в следующей грамматике:
    S

    A S B| a
    A

    c | Ab
    B

    aDA | b
    D

    dD |d
    По построенному дереву вывода восстановите вывод

    от начального символа S и вывод

    от терминальной цепочки до S.
    3.3.27. Постройте дерево вывода цепочки

    = aaabcbbbdbc в следующей КС-грамматике:
    S

    аSbA| a
    A

    c | AB
    B

    bBD | b
    D

    dD |d
    По построенному дереву вывода цепочки восстановите ее левый и правый вывод.
    3.3.28.Каждое правило КС грамматики Хомского представляет собой цепочку некоторого языка. КС грамматика Хомского – это конечное множество КС-правил, которое . Пример КС грамматики Хомского: { E

    > E+T | T, T

    > T*P | P, P

    > i | c | (E) }. а) Постройте КС грамматику языка, задающего все возможные правила КС грамматик
    Хомского. б) Постройте КС грамматику языка, задающего все возможные КС грамматики
    Хомского.
    3.3.29. Описание языка грамматикой тоже должно быть записано цепочкой символов, т.е. представляет собой язык (его часто называют „метаязыком‟. Представление грамматики

    28
    Хомского в БНФ-нотации представляет собой цепочку некоторого метаязыка. Пример правил в БНФ:
    ::= var {; }
    ::= [ + | - ] {}
    Постройте грамматику этого метаязыка.
    3.3.30. Для естественных языков грамматики Хомского неадекватны: они не могут выразить всех синтаксических связей, существующих в естественных языках. Однако для небольших фрагментов естественных языков, например, шаблонов, конечных списков команд и т.п., грамматики Хомского использовать очень удобно. Пример грамматики фрагмента русского языка:
    S → Q V | V Q
    Q → Nим
    V → V O | O V | V
    N
    z
    → A
    z
    N
    z
    | N
    z
    // z – один из шести падежей русского языка
    V → шла | бежала | летела | скакала | ...
    N
    z
    → деревня
    z
    | дорога
    z
    | студентка
    z
    | ведьма
    z
    | метла
    z
    ...
    A
    z
    → красивая
    z
    | молодая
    z
    | широкая
    z
    | пыльная
    z
    | ночная
    z
    ...
    O → пешком | верхом | галопом | на N
    предл
    | над N
    твор
    | в N
    предл
    | по N
    дат
    ...
    В этой грамматике постройте деревья вывода предложений: а) над темной деревней верхом на метле летела старая ужасная ведьма. б) молодая студентка мчалась по пыльной дороге на новой дорогой машине.
    в) ехала деревня мимо мужика.
    3.3.31. Пусть в представлении булевых функций в виде BDD обозначение подграфа с вершиной v, помеченной переменной х, записывается формулой так: [х

    p
    0
    , p
    1
    ], где x- переменная, помечающая вершину, а p
    0
    и p
    1
    – подграфы, в которые из вершины v идут ребра, помеченные, соответственно, 0 и 1. Терминальные вершины, помеченные 0 и 1, записываются как [0] и [1]. Постройте КС-грамматику, порождающую все такие формулы. Постройте дерево вывода формулы:
    [x1

    [ 0 ], [ x2

    [1], [x3

    [0], [x4

    [0],[1]] ] ] ] и определите, какую булеву функцию представляет эта BDD.
    3.3.32. Пусть в представлении булевых функций в виде BDD обозначение подграфа с вершиной vk, помеченной переменной хi, записывается формулой так: vk: [хi

    p
    0
    , p
    1
    ], где p
    0
    и p
    1
    – подграфы, в которые из вершины vk идут ребра, помеченные, соответственно, значениями 0 и 1 переменной xi. Терминальные вершины, помеченные 0 и 1, записываются как 0: [0] и 1: [1]. Постройте КС-грамматику, порождающую все такие формулы. Порождает ли эта грамматика редуцированную BDD? Порождает ли эта грамматика упорядоченную
    BDD? Как с помощью семантических проверок гарантировать упорядоченность BDD, построенных по сгенерированным формулам?
    3.3.33*. КС-грамматика в нормальной форме Грейбах содержит только правила вида A

    aW, где a-терминал, а W - последовательность (может быть пустая) нетерминалов, а также правило S
    
    , если порождаемый грамматикой язык содержит пустую цепочку. Покажите,

    29 что любой КС-язык можно описать грамматикой в нормальной форме Грейбах. Приведите к этой форме грамматику:
    S

    A S B| Dab
    A

    c | Ab
    B

    aDA |

    D

    dD |dB
    1   2   3   4   5   6   7

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