[14.02.11] Лекция №2 (Конспекты - Теория формальных языков)

Лекция №2 [14.02.11]

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

, ,

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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