Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


В предыдущей лекции без доказательства сформулирована теорема 7.4, согласно которой регулярные языки (в алфавите [math]V[/math]) и языки полукольца [math]\mathcal{R}(V)[/math] — одно и то же. Это позволило нам (так сказать, авансом) называть элементы полукольца [math]\mathcal{R}(V)[/math] регулярными языками. Теперь пришла пора доказать это подробно. Для этого, опять разделив понятия языка из полукольца [math]\mathcal{R}(V)[/math] и регулярного языка (т.е. языка, порождаемого регулярной грамматикой), докажем, что язык допускается конечным автоматом с входным алфавитом [math]V[/math] тогда и только тогда, когда он есть элемент полукольца [math]\mathcal{R}(V)[/math]. Тогда, с учетом доказанной теоремы 7.5, будет доказана и теорема 7.4.


Теорема 7.6 (теорема Клини). Пусть [math]V=\{a_1,\ldots,a_n\}[/math] — произвольный алфавит. Язык [math]L\subseteq V^{\ast}[/math] является элементом полукольца [math]\mathcal{R}(V)[/math] тогда и только тогда, когда он допускается некоторым конечным автоматом.


Докажем, что всякий язык из [math]\mathcal{R}(V)[/math] допускается некоторым конечным автоматом.


Для доказательства этого утверждения мы воспользуемся методом индукции по построению языка из [math]\mathcal{R}(V)[/math] как элемента замыкания множества [math]\{\varnothing,\{\lambda\}, \{a_1\},\ldots,\{a_n\}\}[/math]. Этот метод состоит в следующем: сначала утверждение доказывается для языков исходного множества (замыкание которого строится), а затем в предположении, что утверждение доказано для языков [math]L[/math] и [math]K[/math] из [math]\mathcal{R}(V)[/math], оно доказывается для [math]L\cup K[/math], [math]LK[/math] и [math]L^{\ast}[/math].


Конечные автоматы для языков [math]\varnothing,\,\{\lambda\},\,\{a\}[/math], где [math]a\in V[/math], приведены на рис. 7.7.


Конечные автоматы для языков

Пусть конечные автоматы [math]M_1=(V,Q_1,q_{01},F_1,\delta_1)[/math] и [math]M_1=(V,Q_2, q_{02},F_2,\delta_2)[/math] для языков [math]L[/math] и [math]K[/math] полукольца [math]\mathcal{R}(V)[/math] соответственно уже построены. Обратим внимание на то, что входные алфавиты этих автоматов совпадают (мы работаем на множестве языков в произвольном, но фиксированном алфавите [math]V[/math]) и автоматы не имеют ни общих вершин, ни общих дуг.


На рис. 7.8 изображен метод построения конечных автоматов для языков [math]L\cup K,~LK[/math] и [math]L^{\ast}[/math]. На рисунке видно, что автомат для объединения (см. рис. 7.8, а) получается при сохранении всех дуг и вершин автоматов объединяемых языков путем добавления новой начальной вершины $о, проведения из нее пустых Дуг в каждую из начальных вершин объединяемых автоматов ([math]q_{01}[/math] и [math]q_{02}[/math]) и объявления множеством заключительных вершин объединения множеств заключительных вершин ([math]F_1[/math] и [math]F_2[/math]) объединяемых автоматов. Получается "параллельное соединение" автоматов для языков [math]L[/math] и [math]K[/math]. Любая цепочка [math]x[/math], читаемая на некотором пути из вершины [math]s_0[/math] в какую-то из вершин множества [math]F_1\cup F_2[/math], может быть представлена так: [math]x=\lambda x_1=x_1[/math] (переход по пустой цепочке из [math]s_0~q_{01}[/math] и дальнейшее чтение произвольной цепочки [math]x_1[/math], допускаемой автоматом [math]M_1[/math]) или [math]x=\lambda X_2=X_2[/math] (переход по пустой цепочке из [math]s_0~q_{02}[/math] и дальнейшее чтение произвольной цепочки [math]x_2[/math], допускаемой автоматом* [math]M_2[/math]).


Метод построения конечных автоматов для языков

*Новый конечный автомат как некое распознающее устройство может из своей начальной вершины по пустой цепочке, т.е. не читая ни одного символа входной ленты, перейти в начальную вершину первого автомата и потом "работать за него" или "сделать выбор в пользу" второго автомата, перейдя по пустой цепочке из вершины [math]s_0[/math] в вершину [math]q_{03}[/math].


Аналогично при построении конечного автомата для соединения (см. рис. 7.8, б) достаточно объявить новой начальной вершиной начальную вершину первого автомата [math](q_{01})[/math], а множеством заключительных вершин — таковое для второго автомата [math](F_2)[/math], после чего из каждой заключительной вершины первого автомата провести пустую дугу в начальную вершину второго автомата. Получится "последовательное соединение" автоматов.


Конечный автомат для итерации (см. рис. 7.8, в) строится следующим образом. Нужно:


а) ввести новые начальную [math](s_0)[/math] и заключительную [math](t)[/math] вершины, проведя пустую дугу из первой в последнюю;

б) провести пустые дуги из новой начальной вершины в прежнюю начальную вершину автомата итерируемого языка [math](q_0)[/math], a также из каждой заключительной вершины множества [math]F[/math] автомата языка [math]L[/math] в новую заключительную вершину и прежнюю начальную вершину.


Итак, каждый язык полукольца [math]\mathcal{R}(V)[/math] допускается некоторым конечным автоматом.


Докажем теперь, что язык произвольного конечного автомата есть элемент полукольца [math]\mathcal{R}(V)[/math]. Язык конечного автомата, как следует из формулы (7.5), — это конечное объединение языков, являющихся определенными элементами матрицы стоимостей автомата. Матрица стоимостей есть итерация матрицы меток дуг, задающей автомат. Метка каждой дуги — регулярное выражение, обозначающее язык из полукольца [math]\mathcal{R}(V)[/math], и матрица стоимостей, следовательно, является итерацией матрицы, все элементы которой могут быть определены регулярными выражениями, т.е. принадлежат полукольцу [math]\mathcal{R}(V)[/math]. Полукольцо [math]\mathcal{R}(V)[/math] есть полукольцо с итерацией. Поэтому в силу теоремы 3.9 и матрица стоимостей конечного автомата будет состоять из языков полукольца [math]\mathcal{R}(V)[/math]. Отсюда следует, что язык конечного автомата есть элемент этого полукольца.


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


Построение автомата для итерации

Если мы построим автомат для итерации так, как показано на рис. 7.9,б, не вводя новую начальную вершину, то этот автомат будет допускать, в частности, все цепочки языка [math](01)^{\ast}[/math]. Однако эти цепочки не содержатся в итерации исходного языка. В частности, [math]01\notin((01)^{\ast}1)^{\ast}[/math]. Действительно, любая цепочка языка исходного автомата задается регулярным выражением [math](01)^{\ast}1[/math] и есть либо 1, либо цепочка, оканчивающаяся подцепочкой 11. Следовательно, любая цепочка из итерации исходного языка есть либо цепочка [math]1^n[/math], где [math]n\geqslant0[/math], либо цепочка, оканчивающаяся подцепочкой 11.


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


На рис. 7.9,в приведен пример правильно построенной итерации.


Если при построении конечного автомата для итерации мы не будем проводить пустую дугу [math]s\to t[/math], то получим автомат для позитивной итерации исходного языка.




Из теорем 7.5 и 7.6 получим следующий результат.


Следствие 7.2. Следующие утверждения о языке [math]L[/math] в алфавите [math]V[/math] эквивалентны:


1) [math]L[/math] есть элемент полукольца [math]\mathcal{R}(V)[/math];
2) [math]L[/math] порождается некоторой регулярной грамматикой;
3) [math]L[/math] допускается некоторым конечным автоматом.

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


Рассмотрим более подробно решение задачи анализа конечного автомата.


Как же практически вычислить язык конечного автомата? Для этого, вообще говоря, достаточно вычислить, как следует из формулы (7.5), матрицу стоимостей автомата (как размеченного ориентированного графа) любым из способов, которыми мы анализировали размеченные ориентированные графы (см. 5). Если мы выберем для вычисления итерации способ, связанный с решением систем линейных уравнений, нам понадобится решить [math]n=|Q|[/math] систем вида


[math]\xi_j=A\xi_j+\varepsilon_j\,,[/math]

где [math]A[/math] — квадратная матрица n-го порядка*, элемент [math]a_{ij}[/math] которой является регулярным выражением, служащим меткой дуги из вершины (состояния) [math]q_i[/math] в вершину (состояние) [math]q_j[/math] (при некоторой выбранной нумерации состояний!), если такая дуга существует, и равен регулярному выражению [math]\varnothing[/math], если нет дуги из [math]q_i[/math] в [math]q_j[/math]; [math]\varepsilon_j[/math] — j-й столбец единичной матрицы, т.е. столбец, у которого все компоненты, кроме j-й, равны [math]\varnothing[/math] (нулю полукольца [math]\mathcal{R}(V)[/math]), а j-я компонента равна [math]\lambda[/math] (единице полукольца [math]\mathcal{R}(V)[/math]).


*Это не что иное, как матрица меток дуг, определяющая размеченный ориентированный граф.


Решив указанные [math]n[/math] систем, найдем матрицу стоимостей [math]C=A^{\ast}[/math] заданного конечного автомата. Но нам, как правило, нужна не вся матрица стоимостей, а только элементы вида [math]c_{st}[/math], где [math]s[/math] — номер начального, а [math]t[/math] — один из номеров заключительного состояния.


Поэтому, вместо того чтобы решать несколько систем линейных уравнений, достаточно решить одну:


[math]\xi=A\xi+\beta,[/math]
(7.6)

где [math]\beta[/math] — столбец, все компоненты которого равны [math]\varnothing[/math] (нулю полукольца [math]\mathcal{R}(V)[/math]), кроме компонент с номерами [math]t_1,\ldots,t_m[/math], которые являются номерами заключительных состояний. Эти компоненты равны [math]\lambda[/math] (единице полукольца [math]\mathcal{R}(V)[/math]). Другими словами, ко всем уравнениям системы, соответствующим заключительным состояниям, добавляется слагаемое [math]\lambda[/math].


Действительно, решение системы (7.6) будет иметь вид


[math]\xi=A^{\ast}\beta= A^{\ast} \bigl(\varnothing,\ldots, \varnothing, \lambda, \varnothing,\ldots, \varnothing, \lambda, \varnothing,\ldots, \varnothing\bigr)^{\mathsf{T}}[/math]
(7.7)

(элементы [math]\lambda[/math] находятся в строках с номерами [math]t_1,\ldots,t_m[/math])


Умножая в (7.7) матрицу [math]A^{\ast}[/math], равную матрице [math]C[/math] стоимостей, на столбец [math]\beta[/math], получим столбец, s-я компонента которого [math]x_s[/math] будет равна произведению s-й строки матрицы [math]C[/math] [math](c_{s1},\ldots, c_{st_1},\ldots, c_{st_m},\ldots, c_{sn})[/math] на столбец [math]\beta[/math] в формуле (7.7),


[math]x_s=c_{st_1}+x_{st_2}+\ldots+c_{st_m},[/math]

но это и есть регулярное выражение, обозначающее язык конечного автомата.


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


Пример 7.8. Найдем язык конечного автомата, изображенного на рис. 7.10. Запишем для этого автомата матрицу [math]A[/math] меток дуг и систему уравнений:


Язык конечного автомата
[math]A=\begin{pmatrix}0&a&b\\b&a&0\\a&b&0\end{pmatrix}\!,\qquad \begin{cases}x_0= ax_1+bx_2,\\ x_1=bx_0+ax_1,\\ x_2=ax_0+bx_1+\lambda\end{cases}[/math]

(слагаемое [math]\lambda[/math] добавлено в уравнение для [math]x_2[/math], так как вершина [math]q_2[/math] является заключительной).


Исключая [math]x_0[/math], получаем [math]\begin{cases}x_1=b(ax_1+bx_2)+ax_1,\\ x_2=a(ax_1+bx_2)+ bx_1+\lambda,\end{cases}[/math], откуда


[math]\begin{cases}x_1=(ba+a)^{\ast}b^2x_2,\\ x_2=(a^2+b)(ba+a)^{\ast} b^2x_2+ abx_2+\lambda\end{cases}[/math]. Тогда [math]\begin{cases}x_2= \bigl((a^2+b)(ba+a)^{\ast}b^2+ab \bigr)^{\ast},\\ x_1=(ba+a)^{\ast}b^2 \bigl((a^2+b)(ba+a)^{\ast}b^2+ ab\bigr)^{\ast}. \end{cases}[/math]

Отсюда получаем регулярное выражение, обозначающее язык конечного автомата, как значение переменной [math]x_0\colon[/math]


[math]x_0= a(ba+a)^{\ast}b^2 \bigl((a^2+b)(ba+a)^{\ast}b^2+ ab\bigr)^{\ast}+ b\bigl((a^2+b)(ba+a)^{\ast}b^2+ ab\bigr)^{\ast}.[/math]

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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved