Теория и реализация языков программирования




Связь регулярных множеств, конечных автоматов и регулярных грамматик


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

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

Доказательство. Пусть L - язык, допускаемый детерминированным конечным автоматом

 M=(\{q_1, \ldots , q_n\},T,D,q_1,F).

Введем De - расширенную функцию переходов автомата M: De(q, w) = p, где

w \in T^*
, тогда и только тогда, когда
(q, w)\vdash^* (p, e)
.

Обозначим посредством

R^k_{ij}
множество всех слов x таких, что De(qi, x) = qj и если De(qi, y) = qs для любой цепочки y - префикса x, отличного от x и e, то s
k.

Иными словами,

R^k_{ij}
есть множество всех слов, которые переводят конечный автомат из состояния qi в состояние qj , не проходя ни через какое состояние qs для s > k. Однако, i и j могут быть больше k.

R^k_{ij}
может быть определено рекурсивно следующим образом:

\begin{align*} & \text{$R^0_{ij}=\{a \mid a \in T,D(q_i,a)=q_j\},$} \\ & \text{$R^k_{ij}=R^{k-1}_{ij}\bigcup R^{k-1}_{ik}(R^{k-1}_{kk})*R^{k-1}_{kj}$, где $1 \leq k \leq n$} \end{align*}

Таким образом, определение

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

  1. Цепочка w принадлежит
    R^{k-1}_{ij}
    , то есть при анализе цепочки w автомат никогда не достигает состояний с номерами, большими или равными k.
  2. Цепочка w может быть представлена как w = w1w2w3, где
    w_1 \in R^{k-1}_{ik}
    (подцепочка w1 переводит M сначала в qk),
    w_2 \in (R^{k-1}_{kk} )^*
    (подцепочка w2 переводит M из qk обратно в qk, не проходя через состояния с номерами, большими или равными k), и
    w_3 \in R^{k-1}_{kj}
    (подцепочка w3 переводит M из состояния qk в qj) - рис. 3.16.


Рис. 3.16. 

Тогда

L= \bigcup\limits_{q_j\in F} R^n_{1j}
. Индукцией по k можно показать, что это множество является регулярным.

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

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

Праволинейная грамматика G = (N, T, P, S) называется регулярной, если




Содержание  Назад  Вперед