НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

2.4. Теорема Клини

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

Теорема 2.9. Язык представим тогда и только тогда, когда он регулярен.

Доказательство. В силу леммы 2.6 достаточно доказать, что каждый представимый язык регулярен. По лемме 2.3 для этого достаточно доказать, что каждый язык, представимый конечным детерминированным автоматом, регулярен.

Предположим, что L = L(G), где G - конечный детерминированный автомат с n вершинами q1, ..., qn, n≥1, и начальной вершиной q1. Через L(i, j, k), где 1≤i≤n, 1≤j≤n и 1≤k≤n, обозначим семейство помечающих слов всех таких путей в G из qi в qj, которые не проходят ни через одну вершину qt, где t>k (из определения ясно, что λ∈ L (i, j, k), точности тогда, когда i = j).

Для всех i и j язык L (i, j, 0) либо пуст, либо представляет собой объединение некоторых из языков {λ} и {a}, где a пробегает алфавит языка L(G). Следовательно, для любых i и j язык L(i, j, 0) регулярен. (Заметим, что {λ} обозначается регулярным выражением ∅∧*.)

Продолжая индукцию по k, предположим, что для фиксированного k, 0≤k≤n-1, каждый язык L(i, j, k) регулярен. Очевидно, что для любых i и j

L(i, j, k+1) = L(i, j, k)∪L(i, k+1, k)L(k+1,k+1, k)*L{k+1, j, k),

откуда мы заключаем, что каждый язык L(i, j, k+1) регулярен. Следовательно, по индукции каждый язык L(i, j, n) также регулярен.

Но язык L = L(G) представляет собой объединение языков L(i, j, n), таких, что q1, является заключительной вершиной G; поэтому язык L регулярен. □

Еще раз отметим, что все рассуждения, проведенные в доказательстве теоремы 2.9, конструктивны: если дано регулярное выражение для языка L, то можно построить конечный (или конечный детерминированный) автомат, представляющий L, и обратно. Таким образом, в силу теоремы 2.8 существует алгоритм, устанавливающий, задают ли два данных регулярных выражения один и тот же язык. Мы хотим подчеркнуть, что алгоритмы, вытекающие из приведенных выше доказательств, не являются самыми практичными. В конкретных ситуациях специфические соображения или алгоритмы, приведенные, например, в [Sal], оказываются более удобными.

Отметим, наконец, что один и тот же язык может быть задан регулярными выражениями, которые выглядят совершенно по-разному. Читатель может при желании проверить, что регулярные выражения

(ab*c)* и 0*∪a(b∪ca)*c

задают один и тот же язык; в свою очередь регулярные выражения

(ba∪aab)*a и (a∪ab∪ba)*

тоже залают один язык.

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru