Формальные языки


Упражнения


    1. Построить грамматики, порождающие следующие множества цепочек терминального словаря

    Vт = {a, b}:

      а) множество всех слов, которые могут быть построены из символов словаря Vт*,
      б) множество всех слов без пустой цепочки Vт+,
      в) множество всех слов словаря Vт, начинающихся с буквы a.
      г) множество L1 = {ab...b | n >= 0}
      д) множество L2 = {b...ba | n >= 1}

    2. Построить грамматики, порождающие следующие множества цепочек из символов терминального словаря Vт ={a, b, c}, в которых буква b может повторяться n раз.
      а) L3 = {ab...bc | n>=0}
      б) L4 = {ab...bc | n>=1}

    3. Построить грамматику, задающую язык, который состоит из цепочек, начинающихся символом $ и заканчивающихся символом ? , между которыми расположена непустая последовательность из знаков + и -, не содержащая двух одинаковых символов, стоящих рядом.
      Примеры цепочек: $+-?, $+?, $+-+-+?, $-+-+-?.

    4. Построить грамматику, определяющую числа с порядком.
      Примеры: 3.2E-2, .5E+4, 162E3, -34E+20.

    5. Построить грамматику для задания составных идентификаторов. Составной идентификатор может представлять собой несколько обычных идентификаторов, разделенных точкой.
      Примеры: PQ.F11 , SICN.X1.R , BL31.IN3.A6 .

    6. Пусть задано множество биполярных сигналов потенциального типа, длительность которых изменяется дискретно. Начало и конец последовательности сигналов определяется сигналами отрицательной полярности.

    Написать грамматику, задающую множество цепочек, соответствующих сигналам рассматриваемого типа, при условии, что состояния сигнала закодированы буквами a, b, c.

    7. Построить грамматику, порождающую правильные выражения, состоящие из знаков &, V (конъюнкция, дизъюнкция), которые могут соединяться отношениями. Отношение строится из двух идентификаторов, соединенных знаками >, <, =,=/.
      Например, x>y V x>2 или x=a & x>b V x<c.

  • Пред.Страница  След.Страница   Раздел   Содержание


  •  




    - Начало -  - Назад -  - Вперед -