32. Преобразование дка в рв.

Если язык L=L(A) язык некоторого ДКА, то существует регулярное выражения, которые это язык описывают:

1. Способ: вводится регулярное выражение следующего вида: - регулярное выражение, язык которого состоит из множества путей ведущих из состояния i в состояние j для автомата А и не имеющих промежуточных состояний больше чем К. Данная процедура итерационная:

33. Преобразование дка в рв. Метод сокращения состояний.

Если исключить все пути S, ведущие из состояния q в p,то потребуется на дуге ведущей из q в p написать все метки. В результате получаем что, метка записывается в виде цепочки (РВ)

Стратегия построение РВ по конечному автомату такова.

1. Для каждого допускающего состояния q применить описанный выше процесс сокращения. Исключить все состояния кроме q и q_0.

2. Если q≠q₀, то должен остаться автомат с двумя состояниями. Причем РВ записывается в виде

3. Если q≠q₀ то регулярное выражение R^* задает цепочки допускаемые этим автоматом

34. Преобразование рв в конечный автомат.

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

Док-во: Предположим, что L= L(R) для РВ R. Покажем, что L= L(Е) для некоторого ε-НКА Е, обладающего следующими свойствами.

1. Он имеет 1 допускающее состояние

2. У него нет дуг, ведущих в начальное состояние.

3. У него нет дуг выходящих из допускающего состояния

Доказательство проводится структурной индукцией по выражению R

а) R+S

б) RS

в) R^*

35. Применение регулярных выражений.

Одним из наиболее ранних применений регулярных выражений было использование их для спецификации компонента компилятора, называемого «Лексическим анализатором». Этот компонент анализирует исходную программу и распознает лексемы (идентификаторы, ключевые слова), т.е. подцепочки последовательных символов, логически со9ставляющее единое целое.

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

36. Алгоритмические законы для РВ.

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

Для РВ выполняются три закона такого типа:

L+M = M+L, т. е. коммутативный закон для объединения утверждает, что 2 языка можно объединять в любом порядке.

(L+M)+N= L+(M+N). Ассоциативный закон объединения

(LM)N= L(MN). Ассоциативный закон конкатенации

Этот закон гласит, что является единицей объединения

Этот закон гласит, что является единицей конкатенации

Этот закон гласит, что является нулевым элементом конкатенации

L(M+N)= LM+LN. Левосторонний дистрибутивный закон конкатенации относительно объединения

(M+N)L= ML+NL. Правосторонний дистрибутивный закон конкатенации относительно объединения

L+L=L Закон идемпотентности операции объединения

(L^*)^*= L^* Закон утверждает, что при повторной итерации язык уже итерированного выражения не меняется.

^*= ; ^*= ; L⁺=LL^*= L^*L; L^*= L⁺+