43. Мощность множества языков, порожденных грамматиками. Существование языков, не порождаемых грамматиками.

Мощность множества языков, порожденных грамматиками:

кон. алф.

Доказательство счетности: Лемма

X – множество f : X f : X

инъекция, не сюрьекция Парн. слов

Грамматика построим инъекции F ;

По опред. числам получаем все, что нужно

44. Грамматики и автоматы-распознаватели. Место регулярных языков в Иерархии Хомского.

(Иерархия Хомского) Порождающая грамматика задается упорядоченной четверкой G=(V,N,S,D), где V – алфавит, называемый терминальным, N – алфавит, называемый нетерминальным, причем V

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

Иерархия Хомского

(1) произвольная грамматика, порождающая рекурсивно – перечисляемые языки

(2) контекстно-зависимые грамматики и языки все продукции имеют вид

(3) контекстно-свободные

5. регулярные (правильные) грамматики

Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Регулярные языки порождаются регулярными грамматиками, которые, будучи частным случаем праволинейных грамматик, относятся к «наименьшему» типу грамматик в иерархии Хомского.

Сложность языка определяется его типом. Наиболее сложные — языки с фразовой структурой (сюда можно отнести естественные языки), далее — КЗ-, КС-языки и самые простые — регулярные языки.

Автоматом-распознавателем называется упорядоченная четвёрка , где — ориентированный мультиграф, S — входы, а T — выходы.

Регулярные выражения и недетерминированные конечные автоматы связаны между собой следующим образом:

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

1. Ориент. мультиграф G = (V, E, i) 2. Конечный алфавит A 3. Г(граф автомат) = (G = (V, E, i), A, W, S, T) 4.

45. НК-грамматики. Языки, порожденные НК-грамматиками в иерархии Хомского.

Неукорачивающие грамматики

Грамматика

Место в иерархии Хомского: ∀НК-грамматика эквивалентна некоторой контекстно-зависимой грамматике. Поэтому НК-грамматика занимает место КЗ-грамматики в иерархии Хомского.

Теорема: Для  НК-грамматики может быть построена эквивалентная ей контекстная грамматика.

46. Задача распознавания в нк-грамматиках. Оценка высоты дерева вы­вода.

Неукорачивающие грамматики

Задача распознавания Дано: Верно ли, что W не существует конечный алгоритм Теорема:

47. Существование нерегулярных контекстно-свободных языков. Контекстно-свободными называются языки, порожденные КС-грамматиками, т.е. такими грамматиками, для которых правило вывода следующее: Нетерминал→любая цепочка в объединенном алфавите. КС языки не обязаны быть регулярными т.к. КС-грамматики являются более общими по сравнению с регулярными. Т.е. РЕГКС.

Доказательство существования нерегулярных КС языков:

Докажем нерегулярность языка правильных скобочных структур, порождаемых КС-грамматикой . Для этого рассмотрим пересечение данного языка с регулярным языком (*)*, который содержит все цепочки вида . Поскольку каждая правильная скобочная структура содержит одинаковое число открывающих и закрывающих скобок, то указанное пересечение будет языком . Он нерегулярен (см. доказательство в № 38). Следовательно, предполагая регулярность языка правильных скобочных структур, мы должны предполагать и регулярность его пересечения с другим регулярным языком (в данном случае, с (*)*). Пришли к противоречию, показывающему нерегулярность КС-языка правильных скобочных структур.

Пример: .

Дополнительно (о детерминизации страница 521, если попадется).