[14.02.11] Лекция №2 (1061944)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция №2 [14.02.11]

Примеры грамматик

, ,

Язык, порождаемый грамматикой , есть множество всех выводимых из аксиомы грамматики терминальных цепочек.

Грамматики и эквивалентны, если они порождают один и тот же язык.

Если есть набор правил , … , то пишем

Пример:

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

Грамматика правильных скобочных структур:

Классификация грамматик и языков (Хомского)

Или ограничения, накладываемые на правила вывода. Общее ограничение: в левой части правила вывода должен быть хотя бы один нетерминал.

1) грамматики типа О (общего вывода) – никаких дополнительных ограничений;

2) неукорачивающие грамматики – размер размеру ;

3) контекстно-зависимые (КЗ) – если любое правило имеет вид , , , . Если в КЗ убрать , то грамматика будет ОКЗ (обобщённая КЗ);

4) контекстно-свободные (КС) – каждое правило , , . Вот там выше рассмотренные примеры - и являются КС-грамматиками;

5) линейные грамматики - или , где ,

и вот в наших примерах - линейная, а - нет;

6) регулярные - , , ,

Утверждения о грамматиках:

1) для любой грамматики типа О существует эквивалентная обобщенная контекстно-зависимая грамматика (ОКЗ);

2) для любой грамматики типа неукорачивающей существует эквивалентная КЗ;

3) для любой грамматики типа леволинейной существует эквивалентная праволинейная;

4) для любой грамматики типа праволинейной существует эквивалентная регулярная;

Классификация языков, порождаемых грамматиками, тесно связана с классификацией грамматик, но не тождественна ей. Язык относится к классу C, если существует грамматика класса C, порождающая данный язык.

Утверждения о языках:

1) существует ОКЗ-язык, не являющийся КЗ;

2) существует КЗ-язык, не являющийся КС;

3) существует КС-язык, не являющийся линейным;

4) существует линейный язык, не являющийся регулярным;

Имеют место строгие включения некоторых языков:

,

Чтобы определить класс грамматики, достаточно посмотреть на её множество правил. Чтобы доказать класс языка, достаточно придумать любую грамматику данного класса, порождающую этот язык.

Чтобы доказать отрицательное утверждение о классе языка, нужно доказать, что не существует грамматики данного класса, порождающей этот язык.

Пример: палиндром

палиндром в - любая

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций