Слово длины $$k$$ ( $$k > 0$$ ) можно отождествить с элементом декартова произведения ( $$A \x A \x \ldots \x A)$$, в котором $$k$$ сомножителей, обозначаемого $$A^k$$. При $$k = 0$$ имеем $$A^0$$, состоящее из одного пустого слова; не путать с пустым множеством, обозначаемым знаком $$\varnothing$$.
Замечание. При отождествлении элемента декартова произведения со словом полагаем, что слово составлено из входящих в него символов в соответствующем порядке.
Множество всех слов в алфавите $$A$$ обозначают
$$\eq*{ A^{*} =A^{0} \cup A^{1} \cup A^{2} \cup \ldots= \bigcup_{i=0}^{\infty } A^i. }$$
Множество всех непустых слов в алфавите $$A$$ обозначают
$$\eq*{ A^{+} =A^{1} \cup A^{2} \cup \ldots=\bigcup_{i=1}^{\infty}A^{i}. }$$
Если $$k < |u|$$, то префикс и суффикс называются собственными. Заметим, что при нашем определении пустое слово $$\lm$$ будет и собственным префиксом, и собственным суффиксом любого слова $$u$$.
Операции над формальными языками. Поскольку формальные языки
являются множествами, то к ним применяются обычные теоретико-множественные
операции: объединение, пересечение, дополнение (до множества всех слов в
рассматриваемом алфавите). Кроме перечисленных, применяются специфические
операции — это конкатенация двух языков и
Результатом конкатенации языков $$L_1$$ и $$L_2$$ является язык $$L = \{uv \,|\, u \in L_1, v \in L_2\}$$, обозначаемый также $$L_1\cdot L_2$$. Результат конкатенации $$k$$ экземпляров языка $$L$$ обозначим через $$L^k$$.
Результатом
Замечание. При работе с формальными языками операцию объединения часто обозначают знаком " $$+$$ ". В следующих тождествах используется именно это соглашение.
Основные тождества. Пусть $$\al$$, $$\beta$$, $$\gamma$$ — произвольные формальные языки над некоторым фиксированным алфавитом, тогда справедливы следующие тождества:
$$\begin{gather*} (\al + \beta) + \gamma = \al + (\beta+ \gamma),\\ (\al \cdot \beta)\cdot \gamma = \al \cdot (\beta \cdot \gamma),\\ \al + \beta = \beta+ \al,\\ \al \cdot (\beta + \gamma) = \al \cdot \beta + \al \cdot \gamma,\\ (\al + \beta)\cdot \gamma = \al \cdot \gamma+ \beta \cdot \gamma,\\ \al \cdot \varnothing^\ast = \al,\\ \al \cdot \varnothing = \varnothing,\\ \al^\ast = \al \cdot \al^\ast + \varnothing^\ast,\\ \al^\ast = (\al + \varnothing^\ast)^\ast. \end{gather*}$$Прежде всего, для задания формального языка может подойти любое
математически корректное определение множества слов в заданном алфавите.
Однако если иметь в виду задание, при котором возможно алгоритмическое
решение вопроса о принадлежности слова языку, то нужны средства более
ограниченные. Наиболее общим из конструктивных способов задания языков
является способ, использующий так называемые
Правило $$\varphi \to \psi$$ применимо к слову $$u$$, если $$\varphi$$ является фрагментом слова $$u$$. Результатом применения этого правила к слову $$u$$ называется слово $$v$$, полученное заменой любого фрагмента $$\varphi$$ в слове $$u$$ на слово $$u \Rightarrow v$$.
Если $$v$$ — результат применения некоторого правила к слову $$u$$, то пишем $$u \Rightarrow v$$.
Если $$u \Rightarrow v_1 \Rightarrow v_2 \Rightarrow \ldots \Rightarrow v_n \Rightarrow v$$, то пишем $$u \Rightarrow \Rightarrow v$$.
Язык $$L(G)$$, порождаемый грамматикой $$G$$, определяется следующим образом:$$\eq*{ L(G) = \{v\, |\, v \in A^\ast,\ S \Rightarrow\Rightarrow v\}. }$$ Другими словами, $$L(G)$$ — множество слов в основном алфавите, которые могут быть получены из стартового символа $$S$$ путем конечного числа применений правил грамматики.
Известно, что класс языков, задаваемых грамматиками типа $$0$$, является классом рекурсивно перечислимых языков, не совпадающим с классом рекурсивных языков. На языке теории алгоритмов это означает, что не существует алгоритма, который по любой грамматике $$G$$ типа 0 и любому слову $$u$$ отвечает на вопрос " $$u \in L(G)$$?". С другой стороны, существует алгоритм, который, получив на входе грамматику $$G$$ и слово $$u$$, ответит "да", если $$u \in L(G)$$, в противном случае он либо ответит "нет", либо будет работать бесконечно.
Классы языков, задаваемых грамматиками типа $$1$$, $$2$$, $$3$$, являются классами рекурсивных языков.
Альтернативный способ задания формальных языков — их описание с
помощью различных видов автоматов. Одним из простейших классов языков, имеющих
большое прикладное значение, является класс
Регулярные выражения — это аналитический (формульный) способ задания
Определение. Регулярным выражением над алфавитом $$A$$ называется выражение, построенное по следующим правилам:
Регулярное выражение $$R$$ задает язык $$L(R)$$ в соответствии со следующими правилами:
Пример. Рассмотрим регулярное выражение $$R = (ab \vee ac)^\ast (a \vee \lm)$$ над алфавитом $$A = \{a, b, c\}$$. Язык $$L(R)$$ состоит из слов, в которых на нечетных местах стоит символ $$a$$, а на четных $$b$$ или $$c$$.
Замечание 1. В регулярных выражениях вместо знака " $$\vee$$ " часто используют знак " $$+$$ ".
Замечание 2. Если дополнить правила построения регулярных выражений еще двумя правилами
то получим так называемые расширенные регулярные выражения. Здесь дополнение берется до множества всех слов в алфавите $$A$$. Если не использовать дополнение, то получим полурасширенное регулярное выражение.
Как увидим в дальнейшем, использование
Замечание 3. Используя описанную выше интерпретацию регулярных выражений, мы будем вместо соотношения $$u \in L(R)$$ писать $$u \in R$$.
Рассмотрим уравнение вида $$X = \al \cdot X + \beta$$, где $$\al$$ и $$\beta$$ — формальные языки над некоторым алфавитом $$A$$.
Теорема. Если $$\lm \not \in \al$$, то уравнение $$X = \al X + \beta$$ имеет единственное решение $$X= \al^\ast \bt$$. Если $$\lm \in \al$$, то $$X = \al^\ast (\beta+ \gamma)$$ будет решением уравнения $$X = \al X + \beta$$ при любом $$\gamma \in A^\ast$$.
Доказательство. Пусть $$\lm \not \in \al$$ и $$X_0$$ — решение, тогда, подставляя его в уравнение, получим$$\eq*{ X_0 = \al X_0 + \beta = \al(\al X_0 + \beta) + \beta = \al(\al(\al X_0 + \beta) + \beta) + \beta = \al^3X_0 + \al^2 \beta + \al \beta + \beta. }$$
Продолжая выполнять подстановки, видим, что при любом $$k = 0, 1, 2,\ldots$$ выполняется равенство$$\eq{ X_0 = \al_{k+1}X_0 + (\al^k\beta + \al^{k-1}\cdot \beta + \ldots + \al \beta + \beta). }$$
Покажем сначала, что $$\al^\ast \cdot \beta \subseteq X_0$$. Действительно, пусть $$u \in \al^\ast \cdot \beta$$, тогда при некотором значении $$k$$ получим $$u \in (\al^k \beta +\al^{k-1}\beta + \ldots + \al \beta + \beta)$$ и из (1) при таком значении $$k$$ получаем $$u \in X_0$$.
Осталось показать, что $$X_0 \subseteq \al^\ast\beta$$. Действительно, пусть $$u \in X_0$$, тогда при любом $$k$$$$\eq*{ u \in \al^{k+1} \cdot X_0 + (\al^{k}\beta +\al^{k-1}\beta + \ldots + \al \beta + \beta). }$$
Но так как $$\lm \not \in \al$$, то при достаточно больших значениях $$k$$ каждое слово в множестве $$\al^{k+1}\cdot X_0$$ будет длиннее слова $$u$$ и, следовательно, $${u \not \in \al^{k+1} \cdot X_0}$$, но тогда при таких $$k$$$$\eq*{ u \in (\al^k \beta +\al^{k-1}\beta + \ldots + \al \beta + \beta) \subseteq \al^\ast\beta. }$$
Следовательно, $$u \in \al^\ast\beta$$. Итак, мы показали, что если $$X_0$$ — решение, то оно задается формулой $$X_0 = \al^\ast \beta$$, то есть является единственным. Тот факт, что $$\al ^\ast \beta$$ на самом деле — решение, проверяется простой подстановкой. Второе утверждение теоремы предоставляем доказать читателю.
Замечание. Если в уравнении $$X = \al X + \beta$$ под $$\al$$ и $$\beta$$ понимать регулярные выражения, то в случае $$\lm \not \in L(\al)$$ его единственным решением будет регулярное выражение $$\al^\ast \beta$$.
В случае, когда $$L(\al)$$ содержит $$\lm$$, уравнение имеет бесконечно много решений вида $$X = \al^\ast(\beta + \gamma)$$, но здесь под $$\gamma$$ можно понимать не только регулярные выражения, но и выражения в каком-либо формализме, задающие произвольный язык. Часто в таком случае интересуются наименьшим по включению решением, так называемой "наименьшей неподвижной точкой".
Системы линейных уравнений с регулярными коэффициентми. Под стандартной системой понимают систему вида
$$\eq*{ \left\{\begin{aligned} X_{1} =\alpha_{11} X_{1} +\alpha_{12} X_{2} +\ldots +\alpha_{1n} X_{n} +\beta_{1}, \\ X_{2} =\alpha_{21} X_{1} +\alpha_{22} X_{2} +\ldots +\alpha_{2n} X_{n} +\beta_{2}, \\ \mdots{6cm} \\ X_{n} =\alpha_{1n} X_{1} +\alpha_{1n} X_{2} +\ldots +\alpha_{nn} X_{n} +\beta_{n}, \end{aligned}\right. }$$где $$\al_{ij}$$, $$\beta_i$$ — регулярные выражения, $$X_i$$ — переменные ( $$i, j = 1, 2\dts n$$ ).
Решением системы называется набор $$(L(X_1), L(X_2)\dts L(X_n))$$ формальных языков, которые при подстановке вместо соответствующих переменных в уравнения обращают их в равенства. Удобно на решение смотреть как на отображение $$L$$, которое каждой переменной $$X_i$$ ставит в соответствие язык $$L(X_i)$$. Решение $$L^1$$ называется наименьшей неподвижной точкой системы, если для любого другого решения $$L$$ выполняются соотношения $$L^1(X_i) \subseteq L(X_i)$$ при $$i = 1, 2\dts n$$.
Теорема. Каждая стандартная система уравнений имеет единственную неподвижную точку.
Доказательство. Действительно, нетрудно видеть, что отображение $$L^1$$, определяемое по формулам $$L^{1} (X_{i})=\bigcap\limits_{L} L(X_{i})$$, где пересечение берется по всем решениям $$L$$ ( $$i = 1, 2\dts n)$$, является искомой неподвижной точкой системы.
Решаются такие системы уравнений методом исключения неизвестных. Если, например, $$\al_{11} \ne \varnothing$$, то первое уравнение можно представить в виде $$X_1 = \al_{11}X_1 + \beta$$, где $$\beta = \al_{12}X_2 + \ldots +\al_{1n}X_n + \beta_1$$, записать его решение описанным выше способом в виде $$(\al_{11})^\ast \beta$$ и подставить в остальные уравнения. Получим систему с меньшим числом неизвестных и так далее.
Недетерминированные конечные автоматы с $$\varepsilon$$ -переходами. Недетерминированным конечным автоматом с $$\varepsilon$$ -переходами над алфавитом $$A$$ называется набор
$$\eq*{ {\Re} = (Q, A, q_0, F, \varphi), }$$где $$Q$$ — множество состояний, $$A$$ — алфавит, $$q_0$$ — начальное состояние $$(q_0 \in Q)$$, $$F$$ — множество финальных состояний ( $$F \subseteq Q)$$ и $$\varphi\colon Q \x (A\cap \{\varepsilon\}) \to 2^Q$$ — переходная функция.
Такой автомат можно представить нагруженным ориентированным
Язык $$L(\Re)$$, порождаемый автоматом $$\Re$$, состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния $$q_0$$, по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества $$F$$ не обязательно при первом попадании туда. При чтении символов следует воспринимать $$\varepsilon$$ как пустое слово.
Пример. Пусть алфавит $$A = \{a, b, c\}$$, $$Q = \{q_0, q_1, q_2\}$$, $$F = \{q_1\}$$ и переходная функция $$\varphi$$ задана таблицей
| $$\varepsilon$$ | $$a$$ | $$b$$ | $$c$$ | |
| $$q_0$$ | $$\{q_1\}$$ | $$\{q_1,q_2\}$$ | $$\varnothing$$ | $$\varnothing$$ |
| $$q_1$$ | $$\varnothing$$ | $$\varnothing$$ | $$\{q_0\}$$ | $$\{q_0\}$$ |
| $$q_2$$ | $$\{q_1\}$$ | $$\varnothing$$ | $$\varnothing$$ | $$\varnothing$$ |
(рис 13.1) Недетерминированные конечные автоматы без $$\varepsilon$$ -переходов. Недетерминированным конечным автоматом без $$\varepsilon$$ -переходов над алфавитом $$A$$ называется набор
$$\eq*{ \Re = (Q, A, q_0, F, \varphi), }$$где $$Q$$ — множество состояний, $$A$$ —
алфавит, $$q_0$$ — начальное
состояние $$(q_0 \in Q)$$, $$F$$ — множество финальных
состояний $$(F \subseteq Q)$$ и $${\varphi\colon Q \x A \to 2^Q}$$
— переходная функция. Такой автомат также можно представить нагруженным ориентированным
Язык $$L(\Re)$$, порождаемый таким автоматом $$\Re$$, состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния $$q_0$$, по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества $$F$$ не обязательно при первом попадании туда.
Детерминированные конечные автоматы. Детерминированным конечным автоматом над алфавитом $$A$$ называется набор$$\eq*{ \Re = (Q, A, q_0, F, \varphi), }$$ где $$Q$$ — множество состояний, $$A$$ — алфавит, $$q_0$$ — начальное состояние $$(q_0 \in Q)$$, $$F$$ — множество финальных состояний $$(F \subseteq Q)$$ и $$\varphi\colon Q \x A \to Q$$ — переходная функция.
Такой автомат также можно представить нагруженным ориентированным
Язык $$L(\Re)$$, порождаемый таким автоматом $$\Re$$, определяется аналогично тому, как это было для недетерминированных автоматов.
Теорема. Классы языков, задаваемые детерминированными конечными автоматами, недетерминированными конечными автоматами с $$\varepsilon$$ -переходами, недетерминированными конечными автоматами без $$\varepsilon$$ -переходов, регулярными выражениями совпадают.
Доказательство. Для доказательства достаточно по регулярному выражению научиться строить равносильный недетерминированный конечный автомат с $$\varepsilon$$ -переходами (синтез), затем избавляться от $$\varepsilon$$ -переходов, затем детерминировать и, наконец, по детерминированному автомату строить регулярное выражение (анализ).
Регулярное выражение $$\lm$$ представляется автоматом $$\Re {=} (Q{,} A{,} q_0{,} F{,} \varphi)$$, где $$Q = \{q_0, q_1\}$$, алфавит $$A$$ — произволен, $$q_0$$ — начальное состояние, $$F = \{q_1\}$$ — множество финальных состояний и переходная функция $$\varphi$$ задается соотношениями $$\varphi(q_0, \varepsilon) = \{q_1\}, \varphi(q_1, \varepsilon) = \varnothing$$ и $${(\forall x \in A) \varphi (q_0, x) = \varnothing}$$, $$\varphi (q_1, x) = \varnothing$$.
Регулярное выражение $$a$$ $$(a \in A)$$ представляется автоматом $$\Re = (Q, A, q_0, F, \varphi)$$, где $$Q = \{q_0, q_1\}$$, $$q_0$$ — начальное состояние, $$F = \{q_1\}$$ — множество финальных состояний и переходная функция $$\varphi$$ задается соотношениями $$\varphi(q_0, a) = \{q_1\},\ (\forall x \in (A \cup \{\varepsilon \})\backslash \{a\}) \varphi (q_0, x) = \varnothing$$ и $$(\forall x \in (A \cup \{\varepsilon\})) \varphi (q_1, x) = \varnothing$$.
Для регулярного выражения $$(P \vee S)$$, где $$P$$ и $$S$$ — регулярные выражения, можно построить задающий автомат $$\Re = (Q, A, q_0, F, \varphi)$$ следующим образом. Пусть автомат $$\Re_1 = (Q_1, A, q_1, F_1, \varphi_1)$$ задает $$L(P)$$, а автомат $$\Re_2 = (Q_2, A, q_2, F_2, \varphi_2)$$ задает $$L(S)$$. Не уменьшая общности, можно считать, что $$F_1 = \{f_1\}$$ и $$F_2 = \{f_2\}$$ — одноэлементные и что $$q_1 \ne f_1$$, $$q_2 \ne f_2$$. Положим $$Q = Q_1 \cup Q_2 \cup \{q_0, f\}$$, где $$q_0$$, $$f$$ — новые состояния, и поясним построение автомата $$\Re$$ на языке диаграмм. Состояние $$q_0$$ соединим дугами со стартовыми состояниями $$q_1$$, $$q_2$$ автоматов $$\Re_1$$, $$\Re_2$$ и пометим их символом $$\varepsilon$$. Состояния $$f_1$$ и $$f_2$$ автоматов $$\Re_1$$, $$\Re_2$$ соединим дугами с новым состоянием $$f$$ и также пометим их символом $$\varepsilon$$. Начальным состоянием построенного автомата объявим $$q_0$$, а финальным — $$f$$.
Для регулярного выражения $$P\cdot S$$, где $$P$$ и $$S$$ — регулярные выражения, можно построить задающий автомат $$\Re = (Q, A, q_0, F, \varphi)$$ следующим образом. Пусть автомат $$\Re_1 = (Q_1, A, q_1, F_1, \varphi_1)$$ задает $$L(P)$$, а автомат $$\Re_2 = (Q_2, A, q_2, F_2, \varphi_2)$$ задает $$L(S)$$. Не уменьшая общности, опять считаем, что $$F_1 = \{f_1\}$$ и $$F_2 = \{f_2\}$$ — одноэлементные и что $$q_1 \ne f_1$$, $$q_2 \ne f_2$$. Положим $$Q = Q_1 \cup Q_2$$ и поясним построение автомата $$\Re$$ на языке диаграмм. Финальное состояние автомата $$\Re_1$$ соединим дугой со стартовым состоянием автомата $$\Re_2$$ и пометим ее символом $$\varepsilon$$. В качестве $$q_0$$ возьмем стартовое состояние автомата $$\Re_1$$, а в качестве финального состояния $$f$$ возьмем финальное состояние $$f_2$$ автомата $$\Re_2$$.
Для регулярного выражения $$P^\ast$$, где $$P$$ — регулярное выражение, можно построить задающий автомат $$\Re_\t{new} = (Q, A, q_0, \{f_0\}, \varphi)$$ следующим образом. Пусть автомат $$\Re_1 = (Q_1, A, q_1, \{f_1\}, \varphi_1)$$ задает $$L(P)$$. Опять не уменьшая общности, считаем, что $$F_1 = \{f_1\}$$ — одноэлементное и что $$q_1 \ne f_1$$. Добавляем к множеству $$Q_1$$ два новых состояния — $$q_0$$ и $$f_0$$. Соединяем $$\varepsilon$$ -переходами пары состояний $$(q_0, q_1)$$, $$(f_1, f_0)$$, $$(q_0, f_0)$$ и $$(f_1, q_1)$$.
В завершение заметим, что изложенные приемы, очевидно, позволяют по любому регулярному выражению $$R$$ построить недетерминированный автомат $$\Re$$ с $$\varepsilon$$ -переходами, с одним стартовым и одним финальным состоянием, причем стартовое состояние отлично от финального, и при этом такой, что $$L(R) = L(\Re)$$.
Таким образом, задача синтеза решена.
Избавление от $$\varepsilon$$ -переходов.
Покажем, как по недетерминированному автомату $$\Re = (Q, A, q_0, F, \varphi)$$
с $$\varepsilon$$ -переходами построить недетерминированный
автомат $$\Re_1 = (Q, A, q_0, F_1, \varphi_1$$ ) без $$\varepsilon$$ -переходов,
такой, что $$L(\Re_1) = L(\Re)$$. Назовем $$\varepsilon$$ -путем путь
в
Положим $$F_1 = \{q\,|\,\t{существует \varepsilon-путь из}\ q\ \t{в}\ F\}$$. Переходную функцию $$\varphi_1$$ построим следующим образом $$\eq*{ \varphi_{1}(q,a)=\bigcup_{q^{1} \in \lambda (q)}\varphi (q^{1},a). }$$ Заметим, что в полученном автомате множество финальных состояний может быть не одноэлементным.
Детерминизация.Покажем, как по недетерминированному автомату $$\Re = (Q, A, q_0, F, \varphi)$$ без $$\varepsilon$$ -переходов построить детерминированный автомат $$\Re_1 = (Q_1, A, q_1, F_1, \varphi_1)$$, такой, что $$L(\Re_1) = L(\Re)$$. Положим $$Q_1 = 2^Q$$, $$q_1 = \{q_0\}$$, $$F_1= \{q\,|\,(q \subseteq Q) \ (q \cap F \ne \varnothing)\}$$, а $$\varphi_1\colon Q_1 \x A \to Q_1$$ определим следующим образом: $$\eq*{ (\forall q\in Q_{1})(\forall a\in A) \varphi_{1} (q,a)=\bigcup_{s\in q}\varphi(s,a). }$$ Нетрудно видеть, что построенный таким образом автомат $$\Re_1$$ удовлетворяет условию $$L(\Re_1) = L(\Re)$$.
Анализ. Для завершения доказательства теоремы покажем, как по заданному детерминированному конечному автомату ( построить регулярное выражение $$\Re$$, такое, что $$L(R) = L(\Re)$$. Именно это и называют задачей анализа. Правда, метод, который мы используем, можно применить и к недетерминированным автоматам. Метод заключается в том, что мы сводим задачу к решению стандартной системы уравнений. Итак, рассмотрим автомат $$\Re = (Q, A, q_0, F, \varphi)$$.
Пусть $$Q = \{q_0, q_1\dts q_n\}$$, $$A = \{a_1, a_2\dts a_m\}$$. Введем переменные $$X(q_0)$$, $$X(q_1)\dts X(q_n)$$. Переменную $$X(q_i)$$ для каждого $$i = 0, 1\dts n$$ будем интерпретировать как множество слов, которые можно прочитать, начиная от состояния $$q_i$$ и заканчивая в финальном состоянии, тогда $$X(q_i)$$ должна удовлетворять уравнению$$\eq*{ X(q_i) = a_1 \cdot X(\varphi(q_i, a_1)) + a_2\cdot X(\varphi(q_i, a_2)) + \ldots + a_m \cdot X(\varphi(q_i, a_m)) + \bt_i, }$$ где $$\beta_i = \lm$$, если $$q_i \in F$$, $$\beta_i = \varnothing$$, если $$q_i \not \in F$$. Решив систему, берем в качестве ответа значение переменной $$X(q_0)$$.
Задача. Построить регулярное выражение в алфавите $$\{a, b\}$$, задающее язык, порождаемый автоматом $$\Re = (Q, A, q_0, F, \varphi)$$, где $$Q = \{q_0, q_1, q_2, q_3\}$$, $$A = \{a, b\}$$, $$F = \{q_3\}$$ и переходная функция $$\varphi$$ задана таблицей
| $$a$$ | $$b$$ | |
| $$q_0^{}$$ | $$q_3^{}$$ | $$q_1^{}$$ |
| $$q_1^{}$$ | $$q_3^{}$$ | $$q_2^{}$$ |
| $$q_2^{}$$ | $$q_2^{}$$ | $$q_3^{}$$ |
| $$q_3^{}$$ | $$q_1^{}$$ | $$q_3^{}$$ |
(рис 13.2) Решение. Запишем систему уравнений $$\eqa*{ X_0 = a X_3 + b X_1,\\ X_1 = a\cdot X_3 + b \cdot X_2,\\ X_2 = a \cdot X_2 + b \cdot X_3,\\ X_3 = a \cdot X_1 + b \cdot X_3 + \lm. }$$ Заметим, что при записи системы мы упростили обозначения переменных, используя индексы.
Из четвертого уравнения получаем $$X_3 = b^\ast (a\cdot X_1+\lm)$$. Подставляя полученное выражение во все остальные уравнения, получим систему из трех уравнений: $$\eqa*{ X_0 = a\cdot b^\ast (a \cdot X_1 + \lm) + b \cdot X_1,\\* X_1 = a\cdot b^\ast (a \cdot X_1 + \lm) + b \cdot X_2,\\* X_2 = a\cdot X_2 + b\cdot b^\ast (a\cdot X_1 + \lm). }$$ Перепишем ее в стандартном виде: $$\eqa*{ X_0 = (a\cdot b^\ast \cdot a + b) X_1+ a\cdot b^\ast,\\ X_1 = a\cdot b^\ast \cdot a\cdot X_1 + b\cdot X_2 + a\cdot b^\ast,\\ X_2 = b \cdot b^\ast \cdot a \cdot X_1 + a\cdot X_2 + b\cdot b^\ast. }$$ Из третьего уравнения получаем $$X_2 = a^\ast(b \cdot b^\ast \cdot a \cdot X_1 + b\cdot b^\ast)$$ и подставляем в остальные уравнения: $$\eqa*{ X_0 = (a\cdot b^\ast \cdot a + b) \cdot X_1 + a \cdot b^\ast,\\ X_1 = a \cdot b^\ast \cdot a \cdot X_1 + b \cdot a^\ast \cdot (b \cdot b^\ast \cdot a \cdot X_1 + b \cdot b^\ast) + a\cdot b^\ast. } $$
Преобразуем второе уравнение к стандартному виду
$$\eq*{ X_1= (a \cdot b^\ast \cdot a + b \cdot a^\ast \cdot b \cdot b^\ast \cdot a) \cdot X_1 + b \cdot a^\ast \cdot b\cdot b^\ast + a \cdot b^\ast }$$и получаем из него
$$\eq*{ X_1 = (a \cdot b^\ast \cdot a + b \cdot a^\ast \cdot b \cdot b^\ast \cdot a)^\ast (b \cdot a^\ast \cdot b \cdot b^\ast + a \cdot b^\ast). } $$Наконец, получаем ответ
$$\eq*{ X_0 = (a\cdot b^\ast \cdot a + b)(a \cdot b^\ast a + b \cdot a^\ast \cdot b \cdot b^\ast \cdot a)^\ast (b \cdot a^\ast \cdot b\cdot b^\ast + a \cdot b^\ast) + a \cdot b^\ast. }$$Задача. По заданному регулярному выражению $$\al$$ над алфавитом $$A = \{a_1, a_2\dts a_n\}$$ найти в тексте $$x$$ наименьший префикс, содержащий слово из $$L(\al)$$.
Решение. Строится регулярное выражение $$\beta = (a_1 \vee a_2 \vee \ldots \vee a_n)^\ast \al$$ и для него — недетерминированный конечный автомат с $$\varepsilon$$ -переходами. Пусть это будет автомат $$\Re = (Q, A, q_0, F, \varphi)$$. Если при чтении текста $$x$$ построенным автоматом мы приходим в финальное состояние, то это означает, что мы прочитали префикс текста $$x$$, содержащий слово из языка $$L(\al)$$.
Алгоритм, моделирующий работу недетерминированного конечного автомата $$\Re$$ с $$\varepsilon$$ -переходами на входном слове $$x = x_1 x_2 \ldots x_n \in A^\ast$$.
$$\formula{ Q_0:= \{q_0\};\\ \t for\ i := 1\ \t to\ n\ \t do\ Q_i:= \bigcup_{q\in Q_{i-1}}\varphi (q,x_{i});\\ \t{Пометить все состояния из}\ Q_i\ \t{как рассмотренные};\\ \t{Пометить все состояния из}\ Q \backslash Q_i\ \t{как нерассмотренные};\\ \t{Все состояния из}\ Q_i\ \t{поместить в очередь};\\ \t While\ \t{Очередь не пуста}\ \t do\\ \mbox{}\qq \{t :=\ \t{головной элемент из очереди (с удалением)};\\ \mbox{}\qq \t For\ u \in \varphi(t, \varepsilon) \ u\t{ — не рассмотрен}\ \t do\\ \mbox{}\qq\qq \{\t{Пометить}\ u\ \t{как рассмотренное};\\ \mbox{}\qq\qq \t{Поместить}\ u\ \t{в хвост очереди и в}\ Q_i\}\} }$$
Оценим трудоемкость приведенного алгоритма. Пусть $$|Q| = m, |\varphi(q, a)| \le e$$, тогда тело цикла $$while$$ оценивается как $$O(e)$$, а тело цикла " $$for i := 1 to n do$$ " как $$O(e\cdot m)$$ и весь алгоритм имеет трудоемкость $$O(e \cdot m \cdot n)$$.
Анализируя алгоритм построения автомата $$\Re = (Q, A, q_0, \{f\}, \varphi)$$ с $$\varepsilon$$ -переходами по регулярному выражению $$\beta$$, легко установить следующие свойства:
Учитывая приведенные свойства, можем теперь оценить алгоритм, моделирующий работу автомата $$\Re$$, величиной $$O(n \cdot |\beta|)$$.
Рассмотрим теперь задачу, частную по отношению к рассмотренной выше, полагая, что вместо регулярного выражения $$\al$$ задано одно слово-образец $$y$$.
Задача. Требуется найти вхождение заданного слова-образца $$y = y_1 y_2 \ldots y_n$$ в слово-текст $$x = x_1 x_2 \ldots x_m$$ или установить, что такого вхождения нет.
Определение. По данному образцу $$y$$ определим функцию $${S_y\colon A^\ast \!\to\! A^\ast}$$ следующим образом: $$(\forall x \in A^\ast)S_y(x)$$ — наибольший префикс слова $$y$$, являющийся суффиксом слова $$x$$.
Очевидно, что $$(\forall x \in A^\ast)\,|\,S_y(x)| = \max\{k\,|\,{\rm pref}_k y = {\rm suff}_k x\}$$.
Утверждение 4. Для любой строки $$x$$ и любого символа $$a$$ $$|S_y(xa)| \le |S_y (x)| +1$$.
Действительно, предположим, что $$|S_y(xa)| > |S_y(x)| + 1$$ и $$S_y(xa) = ua$$, тогда $$|ua| > |S_y(x)| + 1$$, а $$u$$ будет префиксом и суффиксом строки $$x$$, причем $$|u| > |S_y(x)|$$, что противоречит определению $$|S_y(x)|$$.
Утверждение 5. Пусть $$q = |S_y(x)|$$, тогда для любого символа $$a$$ $$|S_y(xa)| = |S_y(y_1 y_2 \ldots y_q a)|$$.
Действительно, по предыдущему утверждению, $$|S_y(xa)| \le q + 1$$, поэтому значение $$|S_y(xa)|$$ не изменится, если от строки $$xa$$ оставить последние $$q + 1$$ символов, а именно $$y_1 y_2 \ldots y_q a$$. Построим по слову-образцу $$y = y_1 y_2 \ldots y_n$$ конечный автомат$$\eq*{ \Re = (Q, A, q_0, \{f\}, \varphi), }$$ где $$Q = \{0, 1\dts n\}$$, $$q_0 = 0$$, $$f = n$$, а переходную функцию $$\varphi$$ определим следующим образом:$$\eq*{ (\forall q \in Q)(\forall a \in A) \varphi (q, a) = |S_y (y_1 y_2 \ldots y_q a)|. }$$ Для построенного автомата, очевидно, будет справедливо следующее утверждение.
Утверждение 6. Прочитав текст $$x$$, автомат $$\Re = (Q, A, q_0, \{f\}, \varphi)$$ будет находиться в состоянии $$|S_y(x)|$$.
Алгоритм вычисления функции переходов:
$$\formula{ n := {\rm length}(y);\\ \t for\ q:= 0\ \t to\ n\ \t do for\ a \in A\ \t do\ k := \min\{n + 1,\ q + 2\};\\ \t repeat\ k := k - 1\ \t until\ y_1 y_2\ldots y_q = {\rm suff}(y_1 y_2 \ldots y_q\ a);\\ \varphi (q, a) := k }$$ Время работы этого алгоритма $$O(n^3 |A|)$$.
Пример. Пусть алфавит $$A = \{a, b\}$$ и $$Y = aabbaab$$. Допустим, что, читая текст $$x$$, мы обнаружили некоторый префикс $$x_1 x_2\ldots x_i$$ слова $$x$$, заканчивающийся фрагментом $$aabbaa$$, который является префиксом слова $$Y$$, а следующий символ $$x_{i+1}$$ в тексте $$x$$ не равен $$b$$, то есть не совпадает с очередным символом слова $$Y$$. Считаем, что потерпели неудачу, но при этом заметим, что суффикс $$aa$$ этого фрагмента является его префиксом и, возможно, он является префиксом некоторого вхождения слова $$Y$$ в $$x$$.
Делая такое предположение, продолжаем читать $$x$$, сравнивая очередные символы слова $$x$$ с соответствующими, начиная с третьего, символами слова $$Y$$ в надежде на этот раз обнаружить его вхождение в $$x$$.
Таким образом, читая $$x$$, будем считать, что мы в каждый момент находимся в некотором состоянии $$j$$, если только что прочитан префикс $$Y'$$ слова $$Y$$ длины $$j$$. Если при чтении следующего символа мы терпим неудачу, то переходим в новое состояние $$j'$$, такое, что $$j'$$ — максимальный префикс слова $$Y'$$, являющийся его суффиксом. Функцию, которая состоянию $$j$$ ставит в соответствие $$j'$$, называют функцией откатов. В нашем примере ее можно изобразить следующей диаграммой.
(рис 13.3) Введем необходимые обозначения. Пусть $$Y$$ — непустое слово в некотором алфавите, а $$L(Y)$$ — наибольший собственный префикс слова $$Y$$, являющийся его суффиксом. Тогда справедливы следующие утверждения:
Пример. Пусть $$Y = abbabbabbacabbab$$. Тогда $$\eqa*{ L(Y) = abbab,\\ L^2(Y) = ab,\\ L^3 (Y) = \lm. }$$
Определение. Функцией откатов для слова $$Y = Y_1 Y_2 \ldots Y_n$$ называют функцию $$f\colon \{1, 2\dts n\} \to \{0, 1, 2\dts n - 1\}$$, определяемую соотношением $$f(i) = |L({\rm pref}_i Y)|$$, где $${\rm pref}_i Y$$ — префикс длины $$i$$ слова $$Y$$.
В нашем примере функция $$f(i)$$ задается следующей таблицей:
| $$i$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$8$$ | $$9$$ | $$10$$ | $$11$$ | $$12$$ | $$13$$ | $$14$$ | $$15$$ | $$16$$ |
| $$f(i)$$ | $$0$$ | $$0$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ |
$$\formula{ f(1) := 0;\\ \t for\ i :=1\ \t to\ n - 1\ \t do\\ \mbox{}\q \t begin\ j := f(i);\\ \mbox{}\q\q \t while\ (Y[j + 1] \ne Y[i + 1]) \ (j > 0)\ \t do\ j := f[j];\\ \mbox{}\q\q \t if\ Y[j + 1] = Y[i + 1]\ \t then\ f[i + 1] := j + 1\ \t else\ f[i +1] := 0;\\ \mbox{}\q\t end }$$
Для разъяснения работы алгоритма рассмотрим ситуацию, возникшую при обработке слова $$Y$$ на шаге $$i = 9$$. К этому моменту вычислены значения $$f(i)$$ при $$i = 1, 2\dts 9$$:
| $$i$$ | ||||||||||||||||
| $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$8$$ | $$9$$ | $$10$$ | $$11$$ | $$12$$ | $$13$$ | $$14$$ | $$15$$ | $$16$$ | |
| $$Y =$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$c$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ |
| $$f(i) =$$ | $$0$$ | $$0$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ |
Выполняем $$j:= f[i]$$ $$(f[i] = 6)$$. Видим, что условие во внутреннем цикле не выполняется из-за первого сомножителя, так как $$Y[i + 1] = Y [j + 1]$$, поэтому тело внутреннего цикла не выполняется, и далее в соответствии с алгоритмом вычисляем $$f[i + 1] := j + 1 (j + 1 = 7)$$ и $$i := i + 1$$.
Пришли к следующей ситуации $$i = 10$$:
| $$i$$ | ||||||||||||||||
| $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$8$$ | $$9$$ | $$10$$ | $$11$$ | $$12$$ | $$13$$ | $$14$$ | $$15$$ | $$16$$ | |
| $$Y =$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$c$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ |
| $$f(i) =$$ | $$0$$ | $$0$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ |
Вычисляем $$j:= f [i]$$ $$(f[i] = 7)$$. Видим, что условие $$(Y[i + 1] \ne Y[j + 1] \ j > 0$$ ) во внутреннем цикле выполняется. Следовательно, вычисляется новое значение $$j := f[j] (= 4)$$ ; условие опять выполнено, вычисляем новое $$j := f[j] = 1$$ и на этот раз условие выполняется, снова вычисляем $$j := f[j] (= 0)$$. Наконец внутренний цикл завершается, причиной завершения является невыполнение условия $$(j > 0)$$ и поэтому $$f[i + 1] := 0$$. Итак, вычислено $$f[11] = 0$$.
Оценим трудоемкость алгоритма. Обработка очередной буквы $$Y[i + 1]$$ может потребовать многих итераций во внутреннем цикле. Обозначим их число через $$N_i$$. Заметим, что каждая итерация внутреннего цикла уменьшает $$j$$ по крайней мере на $$1$$. С другой стороны, переход к следующему значению $$i$$ увеличивает $$j$$ не более чем на $$1$$. Таким образом, имеем неравенства
$$\eq*{ f[i + 1] \le f[i] - N_i + 1 }$$или
$$\eq*{ N_i \le f[i] - f[i + 1] + 1. }$$Суммируя последнее неравенство по $$i$$ от $$1$$ до $$n - 1$$, получим$$\eq*{ \suml_{i=1}^{n-1}N_{i} = f[1]-f[n] + n - 1\le n.\vspace{-1mm} }$$ Отсюда трудоемкость оценивается сверху величиной $$O(n)$$.
Построение детерминированного конечного автомата по функции откатов. Задача заключается в том, чтобы построить конечный автомат, который, читая произвольный текст, приходил бы в финальное состояние, обнаружив фрагмент, совпадающий с заданным словом $$Y = Y_1 Y_2 \ldots Y_n$$.
Изложенный ниже алгоритм строит переходную функцию $$\varphi$$ автомата$$\eq*{ \Re = (Q, A, q_0, \{f\}, \varphi), }$$ где $$Q = \{0, 1, 2\dts n\}$$, $$q_0 = 0$$, $$f = n$$. Предполагаем, что функция откатов $$f$$ уже построена.
$$\formula{ \t for\ j := 1\ \t to\ n\ \t do\ \varphi[j - 1, Y_j]:=j;\\ \t for\ a \in A,\ a \ne Y_1\ \t do\ \varphi[0, a]:= 0;\\ \t for\ j :=1\ \t to\ n\ \t do for\ a \in A,\ a \ne Y_{j+1}\ \t do\ \varphi[j, a] := \varphi [f[j], a]; }$$
Для слова $$Y = aabbaab$$ получим автомат, заданный диаграммой, изображенной на рис. 13.4.
(рис 13.4) Слово длины $$k$$ ( $$k > 0$$ ) можно отождествить с элементом декартова произведения ( $$A \x A \x \ldots \x A)$$, в котором $$k$$ сомножителей, обозначаемого $$A^k$$. При $$k = 0$$ имеем $$A^0$$, состоящее из одного пустого слова; не путать с пустым множеством, обозначаемым знаком $$\varnothing$$.
Замечание. При отождествлении элемента декартова произведения со словом полагаем, что слово составлено из входящих в него символов в соответствующем порядке.
Множество всех слов в алфавите $$A$$ обозначают
$$\eq*{ A^{*} =A^{0} \cup A^{1} \cup A^{2} \cup \ldots= \bigcup_{i=0}^{\infty } A^i. }$$
Множество всех непустых слов в алфавите $$A$$ обозначают
$$\eq*{ A^{+} =A^{1} \cup A^{2} \cup \ldots=\bigcup_{i=1}^{\infty}A^{i}. }$$
Если $$k < |u|$$, то префикс и суффикс называются собственными. Заметим, что при нашем определении пустое слово $$\lm$$ будет и собственным префиксом, и собственным суффиксом любого слова $$u$$.
Операции над формальными языками. Поскольку формальные языки
являются множествами, то к ним применяются обычные теоретико-множественные
операции: объединение, пересечение, дополнение (до множества всех слов в
рассматриваемом алфавите). Кроме перечисленных, применяются специфические
операции — это конкатенация двух языков и
Результатом конкатенации языков $$L_1$$ и $$L_2$$ является язык $$L = \{uv \,|\, u \in L_1, v \in L_2\}$$, обозначаемый также $$L_1\cdot L_2$$. Результат конкатенации $$k$$ экземпляров языка $$L$$ обозначим через $$L^k$$.
Результатом
Замечание. При работе с формальными языками операцию объединения часто обозначают знаком " $$+$$ ". В следующих тождествах используется именно это соглашение.
Основные тождества. Пусть $$\al$$, $$\beta$$, $$\gamma$$ — произвольные формальные языки над некоторым фиксированным алфавитом, тогда справедливы следующие тождества:
$$\begin{gather*} (\al + \beta) + \gamma = \al + (\beta+ \gamma),\\ (\al \cdot \beta)\cdot \gamma = \al \cdot (\beta \cdot \gamma),\\ \al + \beta = \beta+ \al,\\ \al \cdot (\beta + \gamma) = \al \cdot \beta + \al \cdot \gamma,\\ (\al + \beta)\cdot \gamma = \al \cdot \gamma+ \beta \cdot \gamma,\\ \al \cdot \varnothing^\ast = \al,\\ \al \cdot \varnothing = \varnothing,\\ \al^\ast = \al \cdot \al^\ast + \varnothing^\ast,\\ \al^\ast = (\al + \varnothing^\ast)^\ast. \end{gather*}$$Прежде всего, для задания формального языка может подойти любое
математически корректное определение множества слов в заданном алфавите.
Однако если иметь в виду задание, при котором возможно алгоритмическое
решение вопроса о принадлежности слова языку, то нужны средства более
ограниченные. Наиболее общим из конструктивных способов задания языков
является способ, использующий так называемые
Правило $$\varphi \to \psi$$ применимо к слову $$u$$, если $$\varphi$$ является фрагментом слова $$u$$. Результатом применения этого правила к слову $$u$$ называется слово $$v$$, полученное заменой любого фрагмента $$\varphi$$ в слове $$u$$ на слово $$u \Rightarrow v$$.
Если $$v$$ — результат применения некоторого правила к слову $$u$$, то пишем $$u \Rightarrow v$$.
Если $$u \Rightarrow v_1 \Rightarrow v_2 \Rightarrow \ldots \Rightarrow v_n \Rightarrow v$$, то пишем $$u \Rightarrow \Rightarrow v$$.
Язык $$L(G)$$, порождаемый грамматикой $$G$$, определяется следующим образом:$$\eq*{ L(G) = \{v\, |\, v \in A^\ast,\ S \Rightarrow\Rightarrow v\}. }$$ Другими словами, $$L(G)$$ — множество слов в основном алфавите, которые могут быть получены из стартового символа $$S$$ путем конечного числа применений правил грамматики.
Известно, что класс языков, задаваемых грамматиками типа $$0$$, является классом рекурсивно перечислимых языков, не совпадающим с классом рекурсивных языков. На языке теории алгоритмов это означает, что не существует алгоритма, который по любой грамматике $$G$$ типа 0 и любому слову $$u$$ отвечает на вопрос " $$u \in L(G)$$?". С другой стороны, существует алгоритм, который, получив на входе грамматику $$G$$ и слово $$u$$, ответит "да", если $$u \in L(G)$$, в противном случае он либо ответит "нет", либо будет работать бесконечно.
Классы языков, задаваемых грамматиками типа $$1$$, $$2$$, $$3$$, являются классами рекурсивных языков.
Альтернативный способ задания формальных языков — их описание с
помощью различных видов автоматов. Одним из простейших классов языков, имеющих
большое прикладное значение, является класс
Регулярные выражения — это аналитический (формульный) способ задания
Определение. Регулярным выражением над алфавитом $$A$$ называется выражение, построенное по следующим правилам:
Регулярное выражение $$R$$ задает язык $$L(R)$$ в соответствии со следующими правилами:
Пример. Рассмотрим регулярное выражение $$R = (ab \vee ac)^\ast (a \vee \lm)$$ над алфавитом $$A = \{a, b, c\}$$. Язык $$L(R)$$ состоит из слов, в которых на нечетных местах стоит символ $$a$$, а на четных $$b$$ или $$c$$.
Замечание 1. В регулярных выражениях вместо знака " $$\vee$$ " часто используют знак " $$+$$ ".
Замечание 2. Если дополнить правила построения регулярных выражений еще двумя правилами
то получим так называемые расширенные регулярные выражения. Здесь дополнение берется до множества всех слов в алфавите $$A$$. Если не использовать дополнение, то получим полурасширенное регулярное выражение.
Как увидим в дальнейшем, использование
Замечание 3. Используя описанную выше интерпретацию регулярных выражений, мы будем вместо соотношения $$u \in L(R)$$ писать $$u \in R$$.
Рассмотрим уравнение вида $$X = \al \cdot X + \beta$$, где $$\al$$ и $$\beta$$ — формальные языки над некоторым алфавитом $$A$$.
Теорема. Если $$\lm \not \in \al$$, то уравнение $$X = \al X + \beta$$ имеет единственное решение $$X= \al^\ast \bt$$. Если $$\lm \in \al$$, то $$X = \al^\ast (\beta+ \gamma)$$ будет решением уравнения $$X = \al X + \beta$$ при любом $$\gamma \in A^\ast$$.
Доказательство. Пусть $$\lm \not \in \al$$ и $$X_0$$ — решение, тогда, подставляя его в уравнение, получим$$\eq*{ X_0 = \al X_0 + \beta = \al(\al X_0 + \beta) + \beta = \al(\al(\al X_0 + \beta) + \beta) + \beta = \al^3X_0 + \al^2 \beta + \al \beta + \beta. }$$
Продолжая выполнять подстановки, видим, что при любом $$k = 0, 1, 2,\ldots$$ выполняется равенство$$\eq{ X_0 = \al_{k+1}X_0 + (\al^k\beta + \al^{k-1}\cdot \beta + \ldots + \al \beta + \beta). }$$
Покажем сначала, что $$\al^\ast \cdot \beta \subseteq X_0$$. Действительно, пусть $$u \in \al^\ast \cdot \beta$$, тогда при некотором значении $$k$$ получим $$u \in (\al^k \beta +\al^{k-1}\beta + \ldots + \al \beta + \beta)$$ и из (1) при таком значении $$k$$ получаем $$u \in X_0$$.
Осталось показать, что $$X_0 \subseteq \al^\ast\beta$$. Действительно, пусть $$u \in X_0$$, тогда при любом $$k$$$$\eq*{ u \in \al^{k+1} \cdot X_0 + (\al^{k}\beta +\al^{k-1}\beta + \ldots + \al \beta + \beta). }$$
Но так как $$\lm \not \in \al$$, то при достаточно больших значениях $$k$$ каждое слово в множестве $$\al^{k+1}\cdot X_0$$ будет длиннее слова $$u$$ и, следовательно, $${u \not \in \al^{k+1} \cdot X_0}$$, но тогда при таких $$k$$$$\eq*{ u \in (\al^k \beta +\al^{k-1}\beta + \ldots + \al \beta + \beta) \subseteq \al^\ast\beta. }$$
Следовательно, $$u \in \al^\ast\beta$$. Итак, мы показали, что если $$X_0$$ — решение, то оно задается формулой $$X_0 = \al^\ast \beta$$, то есть является единственным. Тот факт, что $$\al ^\ast \beta$$ на самом деле — решение, проверяется простой подстановкой. Второе утверждение теоремы предоставляем доказать читателю.
Замечание. Если в уравнении $$X = \al X + \beta$$ под $$\al$$ и $$\beta$$ понимать регулярные выражения, то в случае $$\lm \not \in L(\al)$$ его единственным решением будет регулярное выражение $$\al^\ast \beta$$.
В случае, когда $$L(\al)$$ содержит $$\lm$$, уравнение имеет бесконечно много решений вида $$X = \al^\ast(\beta + \gamma)$$, но здесь под $$\gamma$$ можно понимать не только регулярные выражения, но и выражения в каком-либо формализме, задающие произвольный язык. Часто в таком случае интересуются наименьшим по включению решением, так называемой "наименьшей неподвижной точкой".
Системы линейных уравнений с регулярными коэффициентми. Под стандартной системой понимают систему вида
$$\eq*{ \left\{\begin{aligned} X_{1} =\alpha_{11} X_{1} +\alpha_{12} X_{2} +\ldots +\alpha_{1n} X_{n} +\beta_{1}, \\ X_{2} =\alpha_{21} X_{1} +\alpha_{22} X_{2} +\ldots +\alpha_{2n} X_{n} +\beta_{2}, \\ \mdots{6cm} \\ X_{n} =\alpha_{1n} X_{1} +\alpha_{1n} X_{2} +\ldots +\alpha_{nn} X_{n} +\beta_{n}, \end{aligned}\right. }$$где $$\al_{ij}$$, $$\beta_i$$ — регулярные выражения, $$X_i$$ — переменные ( $$i, j = 1, 2\dts n$$ ).
Решением системы называется набор $$(L(X_1), L(X_2)\dts L(X_n))$$ формальных языков, которые при подстановке вместо соответствующих переменных в уравнения обращают их в равенства. Удобно на решение смотреть как на отображение $$L$$, которое каждой переменной $$X_i$$ ставит в соответствие язык $$L(X_i)$$. Решение $$L^1$$ называется наименьшей неподвижной точкой системы, если для любого другого решения $$L$$ выполняются соотношения $$L^1(X_i) \subseteq L(X_i)$$ при $$i = 1, 2\dts n$$.
Теорема. Каждая стандартная система уравнений имеет единственную неподвижную точку.
Доказательство. Действительно, нетрудно видеть, что отображение $$L^1$$, определяемое по формулам $$L^{1} (X_{i})=\bigcap\limits_{L} L(X_{i})$$, где пересечение берется по всем решениям $$L$$ ( $$i = 1, 2\dts n)$$, является искомой неподвижной точкой системы.
Решаются такие системы уравнений методом исключения неизвестных. Если, например, $$\al_{11} \ne \varnothing$$, то первое уравнение можно представить в виде $$X_1 = \al_{11}X_1 + \beta$$, где $$\beta = \al_{12}X_2 + \ldots +\al_{1n}X_n + \beta_1$$, записать его решение описанным выше способом в виде $$(\al_{11})^\ast \beta$$ и подставить в остальные уравнения. Получим систему с меньшим числом неизвестных и так далее.
Недетерминированные конечные автоматы с $$\varepsilon$$ -переходами. Недетерминированным конечным автоматом с $$\varepsilon$$ -переходами над алфавитом $$A$$ называется набор
$$\eq*{ {\Re} = (Q, A, q_0, F, \varphi), }$$где $$Q$$ — множество состояний, $$A$$ — алфавит, $$q_0$$ — начальное состояние $$(q_0 \in Q)$$, $$F$$ — множество финальных состояний ( $$F \subseteq Q)$$ и $$\varphi\colon Q \x (A\cap \{\varepsilon\}) \to 2^Q$$ — переходная функция.
Такой автомат можно представить нагруженным ориентированным
Язык $$L(\Re)$$, порождаемый автоматом $$\Re$$, состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния $$q_0$$, по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества $$F$$ не обязательно при первом попадании туда. При чтении символов следует воспринимать $$\varepsilon$$ как пустое слово.
Пример. Пусть алфавит $$A = \{a, b, c\}$$, $$Q = \{q_0, q_1, q_2\}$$, $$F = \{q_1\}$$ и переходная функция $$\varphi$$ задана таблицей
| $$\varepsilon$$ | $$a$$ | $$b$$ | $$c$$ | |
| $$q_0$$ | $$\{q_1\}$$ | $$\{q_1,q_2\}$$ | $$\varnothing$$ | $$\varnothing$$ |
| $$q_1$$ | $$\varnothing$$ | $$\varnothing$$ | $$\{q_0\}$$ | $$\{q_0\}$$ |
| $$q_2$$ | $$\{q_1\}$$ | $$\varnothing$$ | $$\varnothing$$ | $$\varnothing$$ |
(рис 13.1) Недетерминированные конечные автоматы без $$\varepsilon$$ -переходов. Недетерминированным конечным автоматом без $$\varepsilon$$ -переходов над алфавитом $$A$$ называется набор
$$\eq*{ \Re = (Q, A, q_0, F, \varphi), }$$где $$Q$$ — множество состояний, $$A$$ —
алфавит, $$q_0$$ — начальное
состояние $$(q_0 \in Q)$$, $$F$$ — множество финальных
состояний $$(F \subseteq Q)$$ и $${\varphi\colon Q \x A \to 2^Q}$$
— переходная функция. Такой автомат также можно представить нагруженным ориентированным
Язык $$L(\Re)$$, порождаемый таким автоматом $$\Re$$, состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния $$q_0$$, по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества $$F$$ не обязательно при первом попадании туда.
Детерминированные конечные автоматы. Детерминированным конечным автоматом над алфавитом $$A$$ называется набор$$\eq*{ \Re = (Q, A, q_0, F, \varphi), }$$ где $$Q$$ — множество состояний, $$A$$ — алфавит, $$q_0$$ — начальное состояние $$(q_0 \in Q)$$, $$F$$ — множество финальных состояний $$(F \subseteq Q)$$ и $$\varphi\colon Q \x A \to Q$$ — переходная функция.
Такой автомат также можно представить нагруженным ориентированным
Язык $$L(\Re)$$, порождаемый таким автоматом $$\Re$$, определяется аналогично тому, как это было для недетерминированных автоматов.
Теорема. Классы языков, задаваемые детерминированными конечными автоматами, недетерминированными конечными автоматами с $$\varepsilon$$ -переходами, недетерминированными конечными автоматами без $$\varepsilon$$ -переходов, регулярными выражениями совпадают.
Доказательство. Для доказательства достаточно по регулярному выражению научиться строить равносильный недетерминированный конечный автомат с $$\varepsilon$$ -переходами (синтез), затем избавляться от $$\varepsilon$$ -переходов, затем детерминировать и, наконец, по детерминированному автомату строить регулярное выражение (анализ).
Регулярное выражение $$\lm$$ представляется автоматом $$\Re {=} (Q{,} A{,} q_0{,} F{,} \varphi)$$, где $$Q = \{q_0, q_1\}$$, алфавит $$A$$ — произволен, $$q_0$$ — начальное состояние, $$F = \{q_1\}$$ — множество финальных состояний и переходная функция $$\varphi$$ задается соотношениями $$\varphi(q_0, \varepsilon) = \{q_1\}, \varphi(q_1, \varepsilon) = \varnothing$$ и $${(\forall x \in A) \varphi (q_0, x) = \varnothing}$$, $$\varphi (q_1, x) = \varnothing$$.
Регулярное выражение $$a$$ $$(a \in A)$$ представляется автоматом $$\Re = (Q, A, q_0, F, \varphi)$$, где $$Q = \{q_0, q_1\}$$, $$q_0$$ — начальное состояние, $$F = \{q_1\}$$ — множество финальных состояний и переходная функция $$\varphi$$ задается соотношениями $$\varphi(q_0, a) = \{q_1\},\ (\forall x \in (A \cup \{\varepsilon \})\backslash \{a\}) \varphi (q_0, x) = \varnothing$$ и $$(\forall x \in (A \cup \{\varepsilon\})) \varphi (q_1, x) = \varnothing$$.
Для регулярного выражения $$(P \vee S)$$, где $$P$$ и $$S$$ — регулярные выражения, можно построить задающий автомат $$\Re = (Q, A, q_0, F, \varphi)$$ следующим образом. Пусть автомат $$\Re_1 = (Q_1, A, q_1, F_1, \varphi_1)$$ задает $$L(P)$$, а автомат $$\Re_2 = (Q_2, A, q_2, F_2, \varphi_2)$$ задает $$L(S)$$. Не уменьшая общности, можно считать, что $$F_1 = \{f_1\}$$ и $$F_2 = \{f_2\}$$ — одноэлементные и что $$q_1 \ne f_1$$, $$q_2 \ne f_2$$. Положим $$Q = Q_1 \cup Q_2 \cup \{q_0, f\}$$, где $$q_0$$, $$f$$ — новые состояния, и поясним построение автомата $$\Re$$ на языке диаграмм. Состояние $$q_0$$ соединим дугами со стартовыми состояниями $$q_1$$, $$q_2$$ автоматов $$\Re_1$$, $$\Re_2$$ и пометим их символом $$\varepsilon$$. Состояния $$f_1$$ и $$f_2$$ автоматов $$\Re_1$$, $$\Re_2$$ соединим дугами с новым состоянием $$f$$ и также пометим их символом $$\varepsilon$$. Начальным состоянием построенного автомата объявим $$q_0$$, а финальным — $$f$$.
Для регулярного выражения $$P\cdot S$$, где $$P$$ и $$S$$ — регулярные выражения, можно построить задающий автомат $$\Re = (Q, A, q_0, F, \varphi)$$ следующим образом. Пусть автомат $$\Re_1 = (Q_1, A, q_1, F_1, \varphi_1)$$ задает $$L(P)$$, а автомат $$\Re_2 = (Q_2, A, q_2, F_2, \varphi_2)$$ задает $$L(S)$$. Не уменьшая общности, опять считаем, что $$F_1 = \{f_1\}$$ и $$F_2 = \{f_2\}$$ — одноэлементные и что $$q_1 \ne f_1$$, $$q_2 \ne f_2$$. Положим $$Q = Q_1 \cup Q_2$$ и поясним построение автомата $$\Re$$ на языке диаграмм. Финальное состояние автомата $$\Re_1$$ соединим дугой со стартовым состоянием автомата $$\Re_2$$ и пометим ее символом $$\varepsilon$$. В качестве $$q_0$$ возьмем стартовое состояние автомата $$\Re_1$$, а в качестве финального состояния $$f$$ возьмем финальное состояние $$f_2$$ автомата $$\Re_2$$.
Для регулярного выражения $$P^\ast$$, где $$P$$ — регулярное выражение, можно построить задающий автомат $$\Re_\t{new} = (Q, A, q_0, \{f_0\}, \varphi)$$ следующим образом. Пусть автомат $$\Re_1 = (Q_1, A, q_1, \{f_1\}, \varphi_1)$$ задает $$L(P)$$. Опять не уменьшая общности, считаем, что $$F_1 = \{f_1\}$$ — одноэлементное и что $$q_1 \ne f_1$$. Добавляем к множеству $$Q_1$$ два новых состояния — $$q_0$$ и $$f_0$$. Соединяем $$\varepsilon$$ -переходами пары состояний $$(q_0, q_1)$$, $$(f_1, f_0)$$, $$(q_0, f_0)$$ и $$(f_1, q_1)$$.
В завершение заметим, что изложенные приемы, очевидно, позволяют по любому регулярному выражению $$R$$ построить недетерминированный автомат $$\Re$$ с $$\varepsilon$$ -переходами, с одним стартовым и одним финальным состоянием, причем стартовое состояние отлично от финального, и при этом такой, что $$L(R) = L(\Re)$$.
Таким образом, задача синтеза решена.
Избавление от $$\varepsilon$$ -переходов.
Покажем, как по недетерминированному автомату $$\Re = (Q, A, q_0, F, \varphi)$$
с $$\varepsilon$$ -переходами построить недетерминированный
автомат $$\Re_1 = (Q, A, q_0, F_1, \varphi_1$$ ) без $$\varepsilon$$ -переходов,
такой, что $$L(\Re_1) = L(\Re)$$. Назовем $$\varepsilon$$ -путем путь
в
Положим $$F_1 = \{q\,|\,\t{существует \varepsilon-путь из}\ q\ \t{в}\ F\}$$. Переходную функцию $$\varphi_1$$ построим следующим образом $$\eq*{ \varphi_{1}(q,a)=\bigcup_{q^{1} \in \lambda (q)}\varphi (q^{1},a). }$$ Заметим, что в полученном автомате множество финальных состояний может быть не одноэлементным.
Детерминизация.Покажем, как по недетерминированному автомату $$\Re = (Q, A, q_0, F, \varphi)$$ без $$\varepsilon$$ -переходов построить детерминированный автомат $$\Re_1 = (Q_1, A, q_1, F_1, \varphi_1)$$, такой, что $$L(\Re_1) = L(\Re)$$. Положим $$Q_1 = 2^Q$$, $$q_1 = \{q_0\}$$, $$F_1= \{q\,|\,(q \subseteq Q) \ (q \cap F \ne \varnothing)\}$$, а $$\varphi_1\colon Q_1 \x A \to Q_1$$ определим следующим образом: $$\eq*{ (\forall q\in Q_{1})(\forall a\in A) \varphi_{1} (q,a)=\bigcup_{s\in q}\varphi(s,a). }$$ Нетрудно видеть, что построенный таким образом автомат $$\Re_1$$ удовлетворяет условию $$L(\Re_1) = L(\Re)$$.
Анализ. Для завершения доказательства теоремы покажем, как по заданному детерминированному конечному автомату ( построить регулярное выражение $$\Re$$, такое, что $$L(R) = L(\Re)$$. Именно это и называют задачей анализа. Правда, метод, который мы используем, можно применить и к недетерминированным автоматам. Метод заключается в том, что мы сводим задачу к решению стандартной системы уравнений. Итак, рассмотрим автомат $$\Re = (Q, A, q_0, F, \varphi)$$.
Пусть $$Q = \{q_0, q_1\dts q_n\}$$, $$A = \{a_1, a_2\dts a_m\}$$. Введем переменные $$X(q_0)$$, $$X(q_1)\dts X(q_n)$$. Переменную $$X(q_i)$$ для каждого $$i = 0, 1\dts n$$ будем интерпретировать как множество слов, которые можно прочитать, начиная от состояния $$q_i$$ и заканчивая в финальном состоянии, тогда $$X(q_i)$$ должна удовлетворять уравнению$$\eq*{ X(q_i) = a_1 \cdot X(\varphi(q_i, a_1)) + a_2\cdot X(\varphi(q_i, a_2)) + \ldots + a_m \cdot X(\varphi(q_i, a_m)) + \bt_i, }$$ где $$\beta_i = \lm$$, если $$q_i \in F$$, $$\beta_i = \varnothing$$, если $$q_i \not \in F$$. Решив систему, берем в качестве ответа значение переменной $$X(q_0)$$.
Задача. Построить регулярное выражение в алфавите $$\{a, b\}$$, задающее язык, порождаемый автоматом $$\Re = (Q, A, q_0, F, \varphi)$$, где $$Q = \{q_0, q_1, q_2, q_3\}$$, $$A = \{a, b\}$$, $$F = \{q_3\}$$ и переходная функция $$\varphi$$ задана таблицей
| $$a$$ | $$b$$ | |
| $$q_0^{}$$ | $$q_3^{}$$ | $$q_1^{}$$ |
| $$q_1^{}$$ | $$q_3^{}$$ | $$q_2^{}$$ |
| $$q_2^{}$$ | $$q_2^{}$$ | $$q_3^{}$$ |
| $$q_3^{}$$ | $$q_1^{}$$ | $$q_3^{}$$ |
(рис 13.2) Решение. Запишем систему уравнений $$\eqa*{ X_0 = a X_3 + b X_1,\\ X_1 = a\cdot X_3 + b \cdot X_2,\\ X_2 = a \cdot X_2 + b \cdot X_3,\\ X_3 = a \cdot X_1 + b \cdot X_3 + \lm. }$$ Заметим, что при записи системы мы упростили обозначения переменных, используя индексы.
Из четвертого уравнения получаем $$X_3 = b^\ast (a\cdot X_1+\lm)$$. Подставляя полученное выражение во все остальные уравнения, получим систему из трех уравнений: $$\eqa*{ X_0 = a\cdot b^\ast (a \cdot X_1 + \lm) + b \cdot X_1,\\* X_1 = a\cdot b^\ast (a \cdot X_1 + \lm) + b \cdot X_2,\\* X_2 = a\cdot X_2 + b\cdot b^\ast (a\cdot X_1 + \lm). }$$ Перепишем ее в стандартном виде: $$\eqa*{ X_0 = (a\cdot b^\ast \cdot a + b) X_1+ a\cdot b^\ast,\\ X_1 = a\cdot b^\ast \cdot a\cdot X_1 + b\cdot X_2 + a\cdot b^\ast,\\ X_2 = b \cdot b^\ast \cdot a \cdot X_1 + a\cdot X_2 + b\cdot b^\ast. }$$ Из третьего уравнения получаем $$X_2 = a^\ast(b \cdot b^\ast \cdot a \cdot X_1 + b\cdot b^\ast)$$ и подставляем в остальные уравнения: $$\eqa*{ X_0 = (a\cdot b^\ast \cdot a + b) \cdot X_1 + a \cdot b^\ast,\\ X_1 = a \cdot b^\ast \cdot a \cdot X_1 + b \cdot a^\ast \cdot (b \cdot b^\ast \cdot a \cdot X_1 + b \cdot b^\ast) + a\cdot b^\ast. } $$
Преобразуем второе уравнение к стандартному виду
$$\eq*{ X_1= (a \cdot b^\ast \cdot a + b \cdot a^\ast \cdot b \cdot b^\ast \cdot a) \cdot X_1 + b \cdot a^\ast \cdot b\cdot b^\ast + a \cdot b^\ast }$$и получаем из него
$$\eq*{ X_1 = (a \cdot b^\ast \cdot a + b \cdot a^\ast \cdot b \cdot b^\ast \cdot a)^\ast (b \cdot a^\ast \cdot b \cdot b^\ast + a \cdot b^\ast). } $$Наконец, получаем ответ
$$\eq*{ X_0 = (a\cdot b^\ast \cdot a + b)(a \cdot b^\ast a + b \cdot a^\ast \cdot b \cdot b^\ast \cdot a)^\ast (b \cdot a^\ast \cdot b\cdot b^\ast + a \cdot b^\ast) + a \cdot b^\ast. }$$Задача. По заданному регулярному выражению $$\al$$ над алфавитом $$A = \{a_1, a_2\dts a_n\}$$ найти в тексте $$x$$ наименьший префикс, содержащий слово из $$L(\al)$$.
Решение. Строится регулярное выражение $$\beta = (a_1 \vee a_2 \vee \ldots \vee a_n)^\ast \al$$ и для него — недетерминированный конечный автомат с $$\varepsilon$$ -переходами. Пусть это будет автомат $$\Re = (Q, A, q_0, F, \varphi)$$. Если при чтении текста $$x$$ построенным автоматом мы приходим в финальное состояние, то это означает, что мы прочитали префикс текста $$x$$, содержащий слово из языка $$L(\al)$$.
Алгоритм, моделирующий работу недетерминированного конечного автомата $$\Re$$ с $$\varepsilon$$ -переходами на входном слове $$x = x_1 x_2 \ldots x_n \in A^\ast$$.
$$\formula{ Q_0:= \{q_0\};\\ \t for\ i := 1\ \t to\ n\ \t do\ Q_i:= \bigcup_{q\in Q_{i-1}}\varphi (q,x_{i});\\ \t{Пометить все состояния из}\ Q_i\ \t{как рассмотренные};\\ \t{Пометить все состояния из}\ Q \backslash Q_i\ \t{как нерассмотренные};\\ \t{Все состояния из}\ Q_i\ \t{поместить в очередь};\\ \t While\ \t{Очередь не пуста}\ \t do\\ \mbox{}\qq \{t :=\ \t{головной элемент из очереди (с удалением)};\\ \mbox{}\qq \t For\ u \in \varphi(t, \varepsilon) \ u\t{ — не рассмотрен}\ \t do\\ \mbox{}\qq\qq \{\t{Пометить}\ u\ \t{как рассмотренное};\\ \mbox{}\qq\qq \t{Поместить}\ u\ \t{в хвост очереди и в}\ Q_i\}\} }$$
Оценим трудоемкость приведенного алгоритма. Пусть $$|Q| = m, |\varphi(q, a)| \le e$$, тогда тело цикла $$while$$ оценивается как $$O(e)$$, а тело цикла " $$for i := 1 to n do$$ " как $$O(e\cdot m)$$ и весь алгоритм имеет трудоемкость $$O(e \cdot m \cdot n)$$.
Анализируя алгоритм построения автомата $$\Re = (Q, A, q_0, \{f\}, \varphi)$$ с $$\varepsilon$$ -переходами по регулярному выражению $$\beta$$, легко установить следующие свойства:
Учитывая приведенные свойства, можем теперь оценить алгоритм, моделирующий работу автомата $$\Re$$, величиной $$O(n \cdot |\beta|)$$.
Рассмотрим теперь задачу, частную по отношению к рассмотренной выше, полагая, что вместо регулярного выражения $$\al$$ задано одно слово-образец $$y$$.
Задача. Требуется найти вхождение заданного слова-образца $$y = y_1 y_2 \ldots y_n$$ в слово-текст $$x = x_1 x_2 \ldots x_m$$ или установить, что такого вхождения нет.
Определение. По данному образцу $$y$$ определим функцию $${S_y\colon A^\ast \!\to\! A^\ast}$$ следующим образом: $$(\forall x \in A^\ast)S_y(x)$$ — наибольший префикс слова $$y$$, являющийся суффиксом слова $$x$$.
Очевидно, что $$(\forall x \in A^\ast)\,|\,S_y(x)| = \max\{k\,|\,{\rm pref}_k y = {\rm suff}_k x\}$$.
Утверждение 4. Для любой строки $$x$$ и любого символа $$a$$ $$|S_y(xa)| \le |S_y (x)| +1$$.
Действительно, предположим, что $$|S_y(xa)| > |S_y(x)| + 1$$ и $$S_y(xa) = ua$$, тогда $$|ua| > |S_y(x)| + 1$$, а $$u$$ будет префиксом и суффиксом строки $$x$$, причем $$|u| > |S_y(x)|$$, что противоречит определению $$|S_y(x)|$$.
Утверждение 5. Пусть $$q = |S_y(x)|$$, тогда для любого символа $$a$$ $$|S_y(xa)| = |S_y(y_1 y_2 \ldots y_q a)|$$.
Действительно, по предыдущему утверждению, $$|S_y(xa)| \le q + 1$$, поэтому значение $$|S_y(xa)|$$ не изменится, если от строки $$xa$$ оставить последние $$q + 1$$ символов, а именно $$y_1 y_2 \ldots y_q a$$. Построим по слову-образцу $$y = y_1 y_2 \ldots y_n$$ конечный автомат$$\eq*{ \Re = (Q, A, q_0, \{f\}, \varphi), }$$ где $$Q = \{0, 1\dts n\}$$, $$q_0 = 0$$, $$f = n$$, а переходную функцию $$\varphi$$ определим следующим образом:$$\eq*{ (\forall q \in Q)(\forall a \in A) \varphi (q, a) = |S_y (y_1 y_2 \ldots y_q a)|. }$$ Для построенного автомата, очевидно, будет справедливо следующее утверждение.
Утверждение 6. Прочитав текст $$x$$, автомат $$\Re = (Q, A, q_0, \{f\}, \varphi)$$ будет находиться в состоянии $$|S_y(x)|$$.
Алгоритм вычисления функции переходов:
$$\formula{ n := {\rm length}(y);\\ \t for\ q:= 0\ \t to\ n\ \t do for\ a \in A\ \t do\ k := \min\{n + 1,\ q + 2\};\\ \t repeat\ k := k - 1\ \t until\ y_1 y_2\ldots y_q = {\rm suff}(y_1 y_2 \ldots y_q\ a);\\ \varphi (q, a) := k }$$ Время работы этого алгоритма $$O(n^3 |A|)$$.
Пример. Пусть алфавит $$A = \{a, b\}$$ и $$Y = aabbaab$$. Допустим, что, читая текст $$x$$, мы обнаружили некоторый префикс $$x_1 x_2\ldots x_i$$ слова $$x$$, заканчивающийся фрагментом $$aabbaa$$, который является префиксом слова $$Y$$, а следующий символ $$x_{i+1}$$ в тексте $$x$$ не равен $$b$$, то есть не совпадает с очередным символом слова $$Y$$. Считаем, что потерпели неудачу, но при этом заметим, что суффикс $$aa$$ этого фрагмента является его префиксом и, возможно, он является префиксом некоторого вхождения слова $$Y$$ в $$x$$.
Делая такое предположение, продолжаем читать $$x$$, сравнивая очередные символы слова $$x$$ с соответствующими, начиная с третьего, символами слова $$Y$$ в надежде на этот раз обнаружить его вхождение в $$x$$.
Таким образом, читая $$x$$, будем считать, что мы в каждый момент находимся в некотором состоянии $$j$$, если только что прочитан префикс $$Y'$$ слова $$Y$$ длины $$j$$. Если при чтении следующего символа мы терпим неудачу, то переходим в новое состояние $$j'$$, такое, что $$j'$$ — максимальный префикс слова $$Y'$$, являющийся его суффиксом. Функцию, которая состоянию $$j$$ ставит в соответствие $$j'$$, называют функцией откатов. В нашем примере ее можно изобразить следующей диаграммой.
(рис 13.3) Введем необходимые обозначения. Пусть $$Y$$ — непустое слово в некотором алфавите, а $$L(Y)$$ — наибольший собственный префикс слова $$Y$$, являющийся его суффиксом. Тогда справедливы следующие утверждения:
Пример. Пусть $$Y = abbabbabbacabbab$$. Тогда $$\eqa*{ L(Y) = abbab,\\ L^2(Y) = ab,\\ L^3 (Y) = \lm. }$$
Определение. Функцией откатов для слова $$Y = Y_1 Y_2 \ldots Y_n$$ называют функцию $$f\colon \{1, 2\dts n\} \to \{0, 1, 2\dts n - 1\}$$, определяемую соотношением $$f(i) = |L({\rm pref}_i Y)|$$, где $${\rm pref}_i Y$$ — префикс длины $$i$$ слова $$Y$$.
В нашем примере функция $$f(i)$$ задается следующей таблицей:
| $$i$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$8$$ | $$9$$ | $$10$$ | $$11$$ | $$12$$ | $$13$$ | $$14$$ | $$15$$ | $$16$$ |
| $$f(i)$$ | $$0$$ | $$0$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ |
$$\formula{ f(1) := 0;\\ \t for\ i :=1\ \t to\ n - 1\ \t do\\ \mbox{}\q \t begin\ j := f(i);\\ \mbox{}\q\q \t while\ (Y[j + 1] \ne Y[i + 1]) \ (j > 0)\ \t do\ j := f[j];\\ \mbox{}\q\q \t if\ Y[j + 1] = Y[i + 1]\ \t then\ f[i + 1] := j + 1\ \t else\ f[i +1] := 0;\\ \mbox{}\q\t end }$$
Для разъяснения работы алгоритма рассмотрим ситуацию, возникшую при обработке слова $$Y$$ на шаге $$i = 9$$. К этому моменту вычислены значения $$f(i)$$ при $$i = 1, 2\dts 9$$:
| $$i$$ | ||||||||||||||||
| $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$8$$ | $$9$$ | $$10$$ | $$11$$ | $$12$$ | $$13$$ | $$14$$ | $$15$$ | $$16$$ | |
| $$Y =$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$c$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ |
| $$f(i) =$$ | $$0$$ | $$0$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ |
Выполняем $$j:= f[i]$$ $$(f[i] = 6)$$. Видим, что условие во внутреннем цикле не выполняется из-за первого сомножителя, так как $$Y[i + 1] = Y [j + 1]$$, поэтому тело внутреннего цикла не выполняется, и далее в соответствии с алгоритмом вычисляем $$f[i + 1] := j + 1 (j + 1 = 7)$$ и $$i := i + 1$$.
Пришли к следующей ситуации $$i = 10$$:
| $$i$$ | ||||||||||||||||
| $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | $$8$$ | $$9$$ | $$10$$ | $$11$$ | $$12$$ | $$13$$ | $$14$$ | $$15$$ | $$16$$ | |
| $$Y =$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$c$$ | $$a$$ | $$b$$ | $$b$$ | $$a$$ | $$b$$ |
| $$f(i) =$$ | $$0$$ | $$0$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ |
Вычисляем $$j:= f [i]$$ $$(f[i] = 7)$$. Видим, что условие $$(Y[i + 1] \ne Y[j + 1] \ j > 0$$ ) во внутреннем цикле выполняется. Следовательно, вычисляется новое значение $$j := f[j] (= 4)$$ ; условие опять выполнено, вычисляем новое $$j := f[j] = 1$$ и на этот раз условие выполняется, снова вычисляем $$j := f[j] (= 0)$$. Наконец внутренний цикл завершается, причиной завершения является невыполнение условия $$(j > 0)$$ и поэтому $$f[i + 1] := 0$$. Итак, вычислено $$f[11] = 0$$.
Оценим трудоемкость алгоритма. Обработка очередной буквы $$Y[i + 1]$$ может потребовать многих итераций во внутреннем цикле. Обозначим их число через $$N_i$$. Заметим, что каждая итерация внутреннего цикла уменьшает $$j$$ по крайней мере на $$1$$. С другой стороны, переход к следующему значению $$i$$ увеличивает $$j$$ не более чем на $$1$$. Таким образом, имеем неравенства
$$\eq*{ f[i + 1] \le f[i] - N_i + 1 }$$или
$$\eq*{ N_i \le f[i] - f[i + 1] + 1. }$$Суммируя последнее неравенство по $$i$$ от $$1$$ до $$n - 1$$, получим$$\eq*{ \suml_{i=1}^{n-1}N_{i} = f[1]-f[n] + n - 1\le n.\vspace{-1mm} }$$ Отсюда трудоемкость оценивается сверху величиной $$O(n)$$.
Построение детерминированного конечного автомата по функции откатов. Задача заключается в том, чтобы построить конечный автомат, который, читая произвольный текст, приходил бы в финальное состояние, обнаружив фрагмент, совпадающий с заданным словом $$Y = Y_1 Y_2 \ldots Y_n$$.
Изложенный ниже алгоритм строит переходную функцию $$\varphi$$ автомата$$\eq*{ \Re = (Q, A, q_0, \{f\}, \varphi), }$$ где $$Q = \{0, 1, 2\dts n\}$$, $$q_0 = 0$$, $$f = n$$. Предполагаем, что функция откатов $$f$$ уже построена.
$$\formula{ \t for\ j := 1\ \t to\ n\ \t do\ \varphi[j - 1, Y_j]:=j;\\ \t for\ a \in A,\ a \ne Y_1\ \t do\ \varphi[0, a]:= 0;\\ \t for\ j :=1\ \t to\ n\ \t do for\ a \in A,\ a \ne Y_{j+1}\ \t do\ \varphi[j, a] := \varphi [f[j], a]; }$$
Для слова $$Y = aabbaab$$ получим автомат, заданный диаграммой, изображенной на рис. 13.4.
(рис 13.4) 
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.