XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 82
Текст из файла (страница 82)
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Рис. 7.6 Обоснование корректности этого построения может быть проведено так же, как и построения регулярной грамматики по конечному автомату („двойной" индукцией по длине вывода в грамматике и по длине пути в автомате), и мы его опускаем. ° Таким образом, конечные автоматы допускают в точности те же языки, которые порождают регулярные грамматики.
Вьппе (см. 7.4) без доказательства сформулирована теоре. ма 7.4, согласно которой регулярные языки (в алфавите У) и языки полукольца Я(У) — одно и то же. Это позволило нам (так сказать, авансом) называть элементы полукольца Я.(У) регулярными языками. Теперь пришла пора доказать это подробно. Для этого, опять разделив понятия языка из полукольца Я,(У) и регулярного языка (т.е. языка, порождаемого регулярной грамматикой), докажем, что язык допускается конечным автоматом с входным алфавитом У тогда и только тогда, когда он есть элемент полукольца Я(У). Тогда, с учетом доказанной теоремы 7.5, будет доказана и теорема 7.4.
Теорема 7.6 (теорема Клини). Пусть У = (ам ..., а,Д— произвольный алфавит. Язык Ь С У' является элементом полукольца Я(У) тогда и только тогда, когда он допускается некоторым конечным автоматом. м Докажем, что всякий язык иэ Я.(У) допускается некоторым конечным автоматом. Для доказательства этого утверждения мы воспользуемся методом индукции по построению языка из Я.(У) как элемента замыкания множества (И, (Л), (а1), ..., (а„Ц.
Этот метод 7.5. Коиечиые автоматы. Теорема Клина 515 состоит в следующем: сначала утверждение доказывается для языков исходного множества (замыкание которого строится), а затем в предположении, что утверждение доказано для языков 1, и К иэ 7с(У), оно доказывается для БОК, ЬК и Ь'. Конечные автоматы для языков И, 1Л), (а1, где а Е У, приведены на рис. 7.7.
Рие. Т.т Пусть конечные автоматы М1 = (К Я1, Ч01, Р1, о1) и М2 = (К Ю2, 902, Р2, о2) для языков Ь и К полукольца Я,(У) соответственно уже построены. Обратим внимание на то, что входные алфавиты этих автоматов совпадают (мы работаем на множестве языков в произвольном, но фиксированном алфавите У) и автоматы не имеют ни общих вершин, ни общих дуг. На рис. 7.8 изображен метод построения конечных автома тов для языков БОК, ЬК и Ь'. На рисунке видно, что автомат для объединения (см. рис.
7.8, а) получается при сохранении всех дуг и вершин автоматов объединяемых языков путем доба. аления новой начальной вершины в0, проведения из нее пустых дуг в каждую из начальных вершин объединяемых автоматов (901 и д02) и объявления множеством заключительных вершин объединения множеств заключительных вершин (Р1 и Р2) объединяемых автоматов. Получается „параллельное соединение" автоматов для языков Ь и К. Любая цепочка х, читаемая на некотором пути из вершины ве в какую-то иэ вершин множества Р1 ОР2, может быть представлена так: х = Ах1 = х1 (переход по пустой цепочке из ве уц и дальнейшее чтение произвольной цепочки я1, допускаемой автоматом м1 ) или х = Ахэ = я2 (переход и' 516 У.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ ЬО К Мз К б Рис. 7.8 по пустой цепочке из ло доз и дальнейшее чтение произвольной цепочки хз, допускаемой автоматом' Мз). Аналогично при построении конечного автомата для соединения (см. рис. 7.8, б) достаточно объявить новой начальной вершиной начальную вершину первого автомата (до1), а множеством заключительных вершин — таковое для второго автомата (гз), после чего из каждой заключительной вершины первого автомата провести пустую дугу в начальную вершину второго автомата. Получится „последовательное соединение" автоматов. Новый конечный автомат как некое распознающее устройство может нз своей начальной вершины по пустой цепочке, т.е. не читая ни одного символа входной ленты, перейти в начав нуш вершнну первого автомата и потом „работать за него" или „сделать выбор в пользу" второго автомата, перейдя по пустой цепочке из вершины ле в вершину ооз.
7.о. Коиечиые автоматы. Теорема Клеим 517 Конечньй автомат для итерации (см. рис. 7.8, и) строится следующим образом. Нужно: а) ввести новые начальную (ее) и заключительную (е) вершины, проведя пустую дугу из первой в последнюю; б) провести пустые дуги иэ новой начальной верпшны в прежнюю начальную вершину автомата итерируемого языка (де), а также иэ каждой заключительной вершины множества г' автомата языка Ь в новую заключительную вершину и прежнюю начальную вершину. Итак, каждый язык полукольца Я(11) допускается некоторым конечным автоматом.
Докажем теперь, что язык произвольного конечного авто- матаестьэлементполукольцаЯ(У). Язык конечного автомата, как следует из формулы (7.5), — это конечное объединение языков, являющихся определенными элементами матрицы стоимостей автомата. Матрица стоимостей есть юиерапил матирипы меток дуг, задающей автомат. Метка каждой дуги — регулярное выражение, обозначающее язык из полукольца Я(У), и матрица стоимостей, следовательно, являетсл итерацией матрицы, все элементы которой могут быть определены регулярными выражениями, т.е.
принадлежат полукольцу Я,( т" ). Полукольцо Я.(У) есть полукольцо с итерацией. Поэтому в силу теоремы 3.9 и матрица стоимостей конечного автомата будет состоять иэ языков полукольца Я.(У). Отсюда следует, что язык конечного автомата есть элемент этого полукольца. В Замечание 7.10. Обратим внимание на то, что в общем случае при построении итерации нельзя обойтись без добавления новых начальной и заключительной вершин.
Рассмотрим в этой связи построение автомата для итерации язьпса, допускаемого автоматом на рис. 7.9, а. Если мы построим автомат для итерации так, как показано на рис. 7.9, б, не вводя новую начальную вершину, то этот автомат будет допускать, в частности, все цепочки языка (01)'. Однако эти цепочки не содержатся в итерации исходного языка- В частности, 01 ф ((01)'1)*.
Действительно, любая цепочка ~зыка исходного автомата задается регулярным выражением 518 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЭЫКИ Ряс. 7.9 (01)'1 и есть либо 1, либо цепочка, оканчивающаяся подцепочкой 11. Следовательно, любм цепочка из итерации исходного языка есть либо цепочка 1", где и > О, либо цепочка, оканчивающмся подцепочкой 11. Можно построить аналогичный пример и для того, чтобы убедиться в необходимости добавления новой заключительной вершины. На рис. 7.9, е приведен пример правильно построенной итерации. Если при построении конечного автомата для итерации мы не будем проводить пустую дугу в -+ $, то получим автомат для позитивной итерации исходного языка.
ф Из теорем 7.5 и 7.6 получим следующий результат. Следствие 7.2. Следующие утверждения о языке Ь в алфавите У эквивалентны: 1) Ь есть элемент полукольца К(У); 2) Ь порождается некоторой регулярной грамматикой; 3) Х допускается некоторым конечным автоматом. Задачу построения конечного автомата по данному регулярному выражению называют задачей сяипзеэа конечного 7.в. Конечные автоматы. Теорема Клики 519 аепмыиапаа. Вычисление же языка конечного автомата есть задача ана.аиэа монечноео аетодаата. Рассмотрим более подробно решение задачи аналюа конечного автомата. Как же практически вычислить язык конечного автомата? Для этого, вообще говоря, достаточно вычислить, как следует из формулы (7.5), матрицу стоимостей автомата (как размеченного ориентированного графа) любым из способов, которыми мы аналюировали размеченные ориентированные графы (см.
5). Если мы выберем для вычисления итерации способ, связанный с решением систем линейных уравнений, нам понадобится решить п = ~ф систем вида с =А(у+с~, где А — квадратная матрица и-го порядка', элемент а;.которой является регулярным выражением, служащим меткой дуги из вершины (состояния) щ в вершину (состояние) ду (при некоторой выбранной нумерации состояний!), если такая дуга существует, и равен регулярному выражению И, если нет дуги из а в д1; еу — у-й столбец единичной матрицы, т.е. столбец, у которого все компоненты, кроме у-й, равны И (нулю полукольца Я(к')), а у-я компонента равна А (единице полукольца 17(17)) Решив указанные и систем, найдем матрицу стоимостей С = = А" заданного конечного автомата.
Но нам, как правило, нУжна не вся матрица стоимостей, а только элементы вида сиь где 3 — номер начального, а Ф вЂ” один из номеров заключительного состояния. Поэтому, вместо того чтобы решать несколько систем линейных уравнений, достаточно решить одну: (7.6) Это не что иное, как матрица меток дуг, опредеввквцаа размеченный ориентированный граф (см, 5), 520 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ 6 = А'~3 = А'(Е~, ..., Ед, Л, в, ..., а, Л, а, ..., Ед)' (7.7) (элементы Л находятся в строках с номерами $д, ..., дпд). Умножая в (7.7) матрицу А', равную матрице С стоимостей, на столбец д3, получим столбец, з-я компонента которого х, будет равна произведению а-й строки матрицы С (сед, ..., Сед„..., с,д,„, ..., С,я) на столбец ~3 В формуле (7.7), т.е. хв = смд +" ° +сзд~,з но зто и есть регулярное выражение, обозначающее язык конечного автомата (ср.
с (7.5)). Таким образом, алгебраическая техника анализа ориентированных графов, размеченных над полукольцами (см. 5), дает возможность чисто злгебраически решать задачи анализа конечных автоматов. Пример 7.8. Найдем язык конечного автомата, изображенного на рис. 7.10. Запишем для зтого автомата матрицу А меток дуг и систему уравнений: А= Ь а 0 хе = ахд+Ьхз, хд =Ьхе+ахд, хз =ахе+Ьхд+Л (слагаемое Л добавлено в уравнение для хз, так как вершина дз является заключительной). где, — столбец, все компоненты которого равны И (нулю полукольца Я( д')), кроме компонент с номерами $д, ..., Ф„„которые являются номерами заключительных состояний. Эти компоненты равны Л (единице полукольца Я(У)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
