Проблемы КС языков

1. Проблема пустоты. Пусть задан КС-язык L(G), определить, является ли этот язык пустым или нет.

2. Оценка длины цепочки. Если дерево вывода имеет глубину n, то какова длина цепочки.

3. Существуют ли языки не являющиеся КС-языками?

4. Проблема конечности. Если задан язык L(G), то является ли этот язык конечным или нет?

5. Проблема принадлежности. Принадлежи ли некоторая цепочка z КС-языку.

6. Проблема выводимости. Существует ли алгоритм построения дерева вывода для заданной цепочки z.

Теорема: Пусть G - КС-грамматика, L(G)¹Æ, a - терминальная цепочка, длина которой ³ 1. Тогда для a можно поставить в соответствие дерево вывода в грамматике G.

Глубиной дерева будем называть длину самого длинного пути от корня до конечной вершины дерева. Длина дерева измеряется числом дуг, находящихся на этом пути.

Пример:

G: S®AB, A®aA|a, B®bB|b

a= a³b²

глубина дерева = 4

Вопросы и упражнения

1.Что общего и в чем отличие проблем КС-языков и автоматных?

2. Что называют глубиной дерева?