38. Свойства замкнутости ря

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

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

1. Объединение.

2. Пересечение.

3. Дополнение.

4. Разность.

5. Обращение.

6. Итерация (звездочка).

7. Конкатенация.

8. Гомоморфизм (подстановка цепочек вместо символов языка).

9. Обратный гомоморфизм.

39. Временная сложность взаимных преобразований представлений регулярных языков. Вопросы разрешимости ря.

Преобразование НКА в ДКА

Время выполнения преобразования может быть эспоненциальной функцией от количества состояний НКА. Вычисления ε-замыкания n состояний занимает время O(n³).Если всего n состояний то дуг не более n².

Преобразование ДКА в НКА займет время О(n) для ДКА с n состояниями

Преобразование автомата в регулярное выражение. Если сначала преобразовать НКА в ДКА, а затем ДКА в регулярное выражение, то на это потребуется время О(n³4³²n

Проверка принадлежности регулярному языку.

Если язык L задан с помощью ДКА, то имитируем ДКА обрабатывающий цепочку входных символов w, начиная со стартового состояния. Если ДКА заканчивает в допускающем состоянии, то цепочка w принадлежит этому языку, в противном случае нет. Этот алгоритм является предельно быстрым. Если | w|=n и ДКА представлен с помощью подходящей структуры данных, напримр двухмерного массива (таблицы переходов), то каждый переход требует постояного времени, а вся проверка занимает время O(n).

40. Контекстно-свободные грамматики (КСГ). Определение КСГ. Терминалы, переменные, продукции. Проверка принадлежности цепочки языку КСГ. Порождения. Выводимые цепочки.

Определение КСГ:

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

2. существует конечное множество переменных называемых нетерминалами, или синтаксическими категориями. Каждая переменная представляет язык т.е. множество цепочек

3. одна из переменных представляет определяемый язык- она называется стартовым имволом.

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

1. Переменная (частично ) определяемая продукцией. Эта переменная – голова продукции.

2. Символ продукции —>;

3. Конечная цепочка состоящая из терминалов и переменных, возможно пустая. Она называется телом продукции и представляет способ образования цепочек языка обозначаемого переменной в голове.

КСГ – это способ описания языка с помощью рекурсивных правил, анзываемых продукциями.

Порождения и языки. Начиная со стартового символа, мы порождаем терминальные цепочки, повторяяя замены переменных телами продукции с этими переменными в голове. Язык КС граматики это множество терминальных цепочек, которые можно породить , он называется кс-языком.

Левые и правые порождения. Если мы всегда заменяем крайнюю слева (крайнюю справа) переменую, то такое порождение является левым (правым)каждая цепочка имеет одно левое и одно правое порождения как минимум.

Выводимые цепочки. Любой шаг порождения дает цепочку переменных и\или терминалов. Она называется выводимой цепочкой. Если порождение является левым (правым), то цепочка называется левовыводимой (правовыводимой).