Регулярные множества и их представления
В разделе 3.3.3 приведен алгоритм построения детерминированного конечного автомата по регулярному выражению. Рассмотрим теперь как по описанию конечного автомата построить регулярное множество, совпадающее с языком, допускаемым конечным автоматом.
Теорема3.1. Язык, допускаемый детерминированным конечным автоматом, является регулярным множеством.
Доказательство. Пусть L - язык допускаемый детерминированным
конечным автоматом M = ({q1, ..., qn}, T, D, q1, F). Введем De - расширенную функцию переходов автомата M: De(q, w) = p, где w


Обозначим Rijk множество всех слов x таких, что De(qi, x) = qj и если De(qi, y) = qs
для любой цепочки y - префикса x, отличного от x и e, то s

Иными словами, Rijk есть множество всех слов, которые переводят конечный автомат из состояния qi
в состояние qj, не проходя ни через какое состояние qs
для s > k. Однако, i и j могут быть больше k.
Rijk может быть определено рекурсивно следующим образом:


Rikk-1(Rkkk-1)*Rkjk-1, где 1


Таким образом, определение Rijk означает, что для входной цепочки w, переводящей M из qi в qj без перехода через состояния с номерами, большими k, справедливо ровно одно из следующих двух утверждений:

M сначала в qk), w2


![]()
|
Тогда L =

qj

Таким образом, для всякого регулярного множества имеется конечный автомат, допускающий в точности это регулярное множество, и наоборот - язык, допускаемый конечным автоматом есть регулярное множество.
Рассмотрим теперь соотношение между языками, порождаемыми праволинейными грамматиками и допускаемыми конечными автоматами.
Праволинейная грамматика G = (N, T, P, S) называется регулярной,
если
- каждое ее правило, кроме S e, имеет вид либо AaB, либо Aa, где A, BN, aT;
- в том случае, когда S eP, начальный символ S не встречается в правых частях правил.
Лемма. Пусть G - праволинейная грамматика. Существует регулярная грамматика G' такая, что L(G) = L(G').
Доказательство. Предоставляется читателю в качестве упражнения. __
Теорема 3.2. Пусть G = (N, T, P, S) - праволинейная грамматика. Тогда существует конечный автомат M = (Q, T, D, q0, F) для которого L(M) = L(G).
Доказательство. На основании приведенной выше леммы, без ограничения общности можно считать, что G - регулярная грамматика.
Построим недетерминированный конечный автомат M следующим образом:
- состояниями M будут нетерминалы G плюс новое состояние R, не принадлежащее N. Так что Q = N
{R}; - в качестве начального состояния M примем S, т.е. q0 = S;
- если P содержит правило S
e, то F = {S, R}, иначе F = {R}. Напомним, что S не встречается в правых частях правил, если SeP; - состояние R D(A, a), если AaP. Кроме
того, D(A, a) содержит все B такие, что AaBP. D(R, a) =для каждого a
T.
M, читая вход w, моделирует вывод w в грамматике G. Покажем, что L(M) = L(G). Пусть w = a1a2...an








Аналогично, если w = a1a2...an


D(S, a1) содержит A1, D(A1, a2) содержит A2, и т.д. Поэтому

- вывод в G и x






Теорема 3.3. Для каждого конечного автомата M = (Q, T, D, q0, F) существует праволинейная грамматика G = (N, T, P, S) такая, что L(G) = L(M).
Доказательство. Без потери общности можно считать, что автомат M - детерминированный. Определим грамматику G следующим образом:
- нетерминалами грамматики
G будут состояния автомата M. Так что N = Q; - в качестве начального символа грамматики G примем q0, т.е. S = q0;
- A aBP, если D(A, a) = B;
- A aP, если D(A, a) = B и BF;
- S eP, если q0F.
Доказательство того, что S

