Моделирование формальных языков и грамматик

 

Продуктивная работа с формальными языками и формальными грамматиками предполагает знакомство с алгебраическими системами (по крайней мере с теорией групп) и наличие навыков чтения математических текстов: Как читать математику :)

 

 

 

  1. Изучить материал (включая примеры задания (описания, моделей) языков)

  2. Создать документ ФамилияFLG и заполнить его метаданные.

  3. Просмотреть рекомендованную литературу (по крайней мере оглавления книг!).

    В первых трех книгах найти (следует использовать разные модели поиска!) определение "порождающей грамматики" выбрать наиболее приемлемое для Вас и в документе ФамилияFLG  заполнить таблицу вида (аргументировав свой выбор):

Фамилия Имя

 

Определение  
Аргументация выбора

 

 

  1. Данное задание для некоторых оказывается чрезмерно трудным, хотя и простое.
    Поэтому оно выполняется всеми в обязательном порядке, но принимается любой вариант, а не только верный.
     верное решение будет проанализировано после выполнения всеми данной работы
         Выполнить моделирование (задание, определение) 4 (четырех) формальных языков.

    В каждом из задаваемых языков
    должна быть возможна (как цепочка, слово, фраза) Ваша Фамилия

    1. язык должен состоять из одного слова

    2. язык должен включать конечное число (а именно N! (N-факториал) слов, где N - число символов в Вашей Фамилии).

    3. язык должен включать конечное число слов (строго меньше N!) слов, где N - число символов в Вашей Фамилии).

    4. язык должен быть определен над алфавитом включать бесконечное число слов и замкнут относительно операций ....

    В документе ФамилияFLG  заполнить таблицу вида (воспользовавшись примерами 1-3 из  материала:

Фамилия Имя Отчество

 

Задание

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

язык из одного слова

здесь должна быть модель вида L = {G | пояснение к G},
где G - формальная грамматика

язык с N! (факториал числа N) слов, где N - число символов в Фамилии.

здесь должна быть модель вида L = {G | пояснение к G},
где G - формальная грамматика

язык с конечным числом слов (строго меньше N!), где N - число символов в Фамилии.

здесь должна быть модель вида L = {G | пояснение к G},
где G - формальная грамматика

язык над алфавитом из N символов (N - число символов в Фамилии) с бесконечным числом слов

здесь должна быть модель вида L = {G | пояснение к G},
где G - формальная грамматика

  1. Скачать программу JFLAP (JAR-файл - он не нанесёт вреда Вашему компьютеру!), запустить ее и познакомиться с возможностями (о том, что это такое смотри модуль JFLAP в материале)
    Скачать и распаковать архив с рабочими     документами

  2. В Grammar, открыть и просмотреть файл kmp01 (из каталога kmp-jff)
    (это     простая грамматику вида anbmcp where m=n+p, n>0, p>0).
    Отредактировать грамматику из     oea,  заменив строчные символы на строчные первые буквы своих ФИО (латиницей!).
    В грамматиках (при вводе и редактировании) не используются пробелы!
    Сохранить документ под именем Фамилия    1, сделать скрин согласно образца (случай Орловой Евы Адамовны) и вставить скрин в документ ФамилияFLG.

  3. Определить, к какому типу относится грамматика в Фамилия1 (меню Test и единственная команда там...).

  4. Открыть в редакторе файл kmp02 (из каталога kmp-jff), заменить заменить строчные символы на строчные первые буквы своих ФИО (латиницей!). Сохранить документ под именем Фамилия2, определить тип грамматики, сделать скрин согласно образца (случай Орловой Евы) и вставить скрин в документ ФамилияFLG.

  5. Произвести парсинг (синтаксический разбор) формально правильного текста языка, построенного на основе грамматики в файле Фамилия2, для этого:

    • открыть в редакторе Фамилия1

    • выбрать меню Input выбрать команду Brute Force Parse

    • в поле Input  ввести текст из 12-16 букв(соответствующий грамматике: anbmcp where m=n+p, n>0, p>0).
      Примерные тексты (для случая Орловой, Ваш случай определяется строчными начальными буквами Ваших ФИО)

      • oeea

      • oooeeeeeaa

      • oooeeeea

      • oeeeeeeeaaaaaaa

      • на языке повседневности: число последовательно идущих букв е равняться сумме обрамляющих их букв o и а

    • Пошагово получить дерево синтаксического разбора (Nononverted Tree), сделать скрин согласно образца (случай Орловой Евы) и вставить скрин в документ ФамилияFLG.

    • Пошагово получить деривационную таблицу синтаксического разбора (Derivation Table), сделать скрин согласно образца (случай Орловой Евы) и вставить скрин в документ ФамилияFLG.

  6. Попробовать получить структуры разбора формально неправильных текстов (не соответствующих грамматике) и текстов, содержащих неопределенные в грамматике литералы. Заполнить в в документе ФамилияFLGтаблицу вида:

Фамилия Имя Отчество

 

Эксперимент

Результат

вводимая строка грамматически неверного текста

описание выхода парсинга

вводимая строка с неопределенными в грамматике литералами

описание выхода парсинга

 

  1. Заполнить в ФамилияFLG метаданные.

  2. Отослать преподавателю файлы ФамилияFLG, Фамилия1, Фамилия2 (+ отзыв).

  3. Продолжить самостоятельное освоение возможностей JFLAP

  4. Готовить конспект ответов на экзаменационные вопросы.

  5. Изучать рекомендованную литературу по теме:

kmp