Допустимость языка конечным автоматом

О языке [cbm]L(M)[/cbm] говорят, что он допускается (или воспринимается) конечным автоматом [cbm]M[/cbm] . О любой цепочке, принадлежащей языку [cbm]L(M)[/cbm] , говорят, что она допускается (или воспринимается) конечным автоматом [cbm]M[/cbm] . Такую цепочку называют также допустимой цепочкой данного конечного автомата.

Определение 7.10. Два конечных автомата [cbm]M_1[/cbm] и [cbm]M_2[/cbm] называют эквивалентными, если их языки совпадают:

[cbm]L(M_1)=L(M_2).[/cbm]

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

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

Чтобы доказать теорему, нужно:

1) указать способ построения регулярной грамматики [cbm]G[/cbm] по заданному конечному автомату [cbm]M[/cbm] , такой, чтобы язык, порождаемый грамматикой [cbm]G[/cbm] , совпадал с языком, допускаемым автоматом [cbm]M\colon\,L(G)=L(M)[/cbm] ;

2) указать способ построения конечного автомата [cbm]M[/cbm] по заданной регулярной грамматике [cbm]G[/cbm] , такой, чтобы язык, допускаемый автоматом [cbm]M[/cbm] , совпадал с языком, порождаемым грамматикой [cbm]G\colon\,L(M)=L(G)[/cbm] .

Замечание 7.9. Регулярную грамматику [cbm]G[/cbm] и конечный автомат [cbm]M[/cbm] , такие, что [cbm]L(G)=L(M)[/cbm] , иногда называют эквивалентными.

Рассмотрим эти построения по очереди.


Построение регулярной грамматики по конечному автомату

Пусть дан конечный автомат

[cbm]M=(V,Q,q_0,F,\delta).[/cbm]

Определим регулярную грамматику [cbm]G=(V,N,S,P)[/cbm] следующим образом: терминальный алфавит [cbm]V[/cbm] совпадает с входным алфавитом автомата [cbm]M[/cbm] ; нетерминальный алфавит [cbm]N[/cbm] находится во взаимно однозначном соответствии с множеством состояний [cbm]Q[/cbm] автомата [cbm]M[/cbm] , причем состоянию [cbm]q\in Q[/cbm] сопоставлен нетерминал [cbm]S_q\in N[/cbm] и аксиома сопоставлена начальному состоянию [cbm]q_0[/cbm] , то есть [cbm]S=S_{q_0}[/cbm] ; множество правил вывода [cbm]P[/cbm] строится по системе команд [cbm]\delta[/cbm] так: правило вывода [cbm]S_q\to aS_r[/cbm] , где [cbm]a\in V\cup\{\lambda\}[/cbm] , принадлежит [cbm]P[/cbm] тогда и только тогда, когда в [cbm]\delta[/cbm] есть команда [cbm]qa\to r[/cbm] ; кроме того, если (и только если) состояние [cbm]r[/cbm] заключительное [cbm](r\in F)[/cbm] , то в [cbm]P[/cbm] добавляется правило вывода [cbm]S_q\to a[/cbm] . Если же [cbm]q_0\in F[/cbm] (и только в этом случае), то в [cbm]P[/cbm] помещаем правило вывода [cbm]S_{q_0}\to\lambda[/cbm] .

Для конечного автомата на рис. 7.5 получим следующую регулярную грамматику:

[cbm]\begin{aligned}& S_{q_0}\to 0 S_{q_0}\mid 1 S_{q_0}\mid 0 S_{q_1},\\ & S_{q_1}\to 0 S_{q_2}\mid0,\\ & S_{q_2}\to 0 S_{q_2}\mid 1 S_{q_2}\mid0\mid1. \end{aligned}[/cbm]

Заметим, что, читая цепочку в автомате, в грамматике мы ее выводим (порождаем). Например,

[cbm]q_0\to_{0}q_1\to_{0}q_2\to_{1}q_2[/cbm] и [cbm]S_{q_0}\vdash 0 S_{q_1}\vdash 00 S_{q_2}\vdash 001.[/cbm] .

Докажем, что описанное построение корректно, т.е. [cbm]L(G)=L(M)[/cbm] . Для этого сначала, используя индукцию по длине [cbm]n[/cbm] пути в конечном автомате [cbm]M[/cbm] , докажем, что из факта достижимости [cbm]q\Rightarrow_{x}^{n}r[/cbm] в автомате [cbm]M[/cbm] (для любого [cbm]n\geqslant0[/cbm] ) следует выводимость [cbm]S_q\vdash_{G}^{\ast}xS_r[/cbm] в грамматике [cbm]G[/cbm] для любых [cbm]q,r\in Q[/cbm] и [cbm]x\in V^{\ast}[/cbm] .

Пусть длина пути [cbm]n=0[/cbm] , то есть [cbm]q\Rightarrow_{x}^{0}r[/cbm] и [cbm]r=q[/cbm] . Так как метка пути нулевой длины в ориентированном графе, размеченном над полукольцом [cbm]\mathcal{R}(V)[/cbm] , равна единице полукольца — регулярному выражению [cbm]\lambda[/cbm] , то [cbm]q\Rightarrow_{\lambda}^{0}q[/cbm] при [cbm]x=\lambda[/cbm] . Но [cbm]S_q\vdash_{G}^{0}S_q[/cbm] выполняется тривиально.

Пусть для любого [cbm]k \leqslant m-1[/cbm] из достижимости [cbm]q\Rightarrow_{x}^{k}r[/cbm] следует выводимость [cbm]S_q\vdash^{\ast}xS_r[/cbm] , и пусть в автомате [cbm]M[/cbm] существует путь [cbm]W[/cbm] длины [cbm]m[/cbm] , ведущий из вершины [cbm]g[/cbm] в вершину [cbm]r[/cbm] , на котором читается цепочка [cbm]x[/cbm] , то есть [cbm]q\Rightarrow_{x}^{m}r[/cbm] . Так как длина пути [cbm]W[/cbm] не меньше 1, то в нем есть по крайней мере одна дуга и существуют такая вершина [cbm]q'[/cbm] и такое [cbm]a\in V\cup \{\lambda\}[/cbm] , что [cbm]q\to_{a}q'\Rightarrow_{y}^{m-1}r[/cbm] , где [cbm]ay=x[/cbm] (мы выделили первую дугу пути [cbm]W[/cbm] ). Тогда, согласно построению множества [cbm]P[/cbm] правил вывода грамматики [cbm]G[/cbm] , в [cbm]P[/cbm] содержится правило [cbm]S_q\to aS_{q'}[/cbm] , а, по предположению индукции, из того, что в [cbm]M[/cbm] имеется [cbm]q'\Rightarrow_{y}^{m-1}r[/cbm] , следует, что [cbm]S_{q'}\vdash_{G}^{\ast} yS_r[/cbm] . В итоге получаем [cbm]S_q\vdash_{G} aS_{q'}\vdash_{G}^{\ast} ayS_r=xS_r[/cbm] , то есть [cbm]S_q\vdash_{G}^{\ast}xS_r[/cbm] , что и требовалось.

Теперь если цепочка [cbm]x\in L(M)[/cbm] , то в [cbm]M[/cbm] существует путь, ведущий из начального состояния [cbm]q_0[/cbm] в одно из заключительных состояний [cbm]q_f[/cbm] , на котором читается цепочка [cbm]x[/cbm] , то есть [cbm]q_0\Rightarrow_{x}^{\ast}q_f[/cbm] некоторого [cbm]q_f\in F[/cbm] . Если [cbm]q_f=q_0[/cbm] и тогда [cbm]x=\lambda\in L(M)[/cbm] , то в множестве [cbm]P[/cbm] правил вывода есть правило [cbm]S_{q_0}\to\lambda[/cbm] и [cbm]\lambda\in L(G)[/cbm] . Если же [cbm]q_f[/cbm] отлично от [cbm]q_0[/cbm] , то, какова бы ни была цепочка [cbm]x[/cbm] , путь из [cbm]q_0[/cbm] в [cbm]q_f[/cbm] , на котором она читается, имеет длину, не меньшую единицы. Выделяя в этом пути последнюю дугу, получим [cbm]q_0\Rightarrow_{y}^{\ast}q'\to_{a}q_f[/cbm] , где [cbm]ya=x[/cbm] . Но тогда, во-первых, как мы только что доказали, в грамматике [cbm]G[/cbm] имеет место выводимость [cbm]S_{q_0}\vdash_{G}^{\ast}yS_{q'}[/cbm] , а, во-вторых, из того, что [cbm]q'\to_{a}q_f[/cbm] , согласно построению множества правил вывода грамматики [cbm]G[/cbm] , следует, что в ней есть правило [cbm]S_{q'}\to a[/cbm] , и окончательно получим

[cbm]S_{q_0}\vdash_{G}^{\ast}yS_{q'}\vdash ya=x[/cbm] , то есть [cbm]x\in L(G)[/cbm] .

Таким образом, мы полностью доказали, что для каждой цепочки [cbm]x\in V^{\ast}[/cbm] из того, что [cbm]x\in L(M)[/cbm] , следует [cbm]x\in L(G)[/cbm] , т.е. имеет место включение [cbm]L(M)\subseteq L(G)[/cbm] .

Чтобы доказать обратное включение, используя индукцию по длине [cbm]n[/cbm] вывода в грамматике [cbm]G[/cbm] , покажем сначала, что из факта выводимости [cbm]S_q\vdash_{G}^{n} xS_r[/cbm] (для любого [cbm]n\geqslant0[/cbm] ) следует достижимость [cbm]q\Rightarrow_{x}^{\ast}r[/cbm] в автомате [cbm]M[/cbm] для любых [cbm]q,r\in Q[/cbm] и [cbm]x\in V^{\ast}[/cbm] .

При [cbm]n=0[/cbm] имеем [cbm]S_q\vdash_{G}^{0}S_q,~x=\lambda[/cbm] и тривиально выполняется [cbm]q\Rightarrow_{\lambda}^{0}q[/cbm] .

Пусть для любого [cbm]k\leqslant m-1[/cbm] из выводимости [cbm]S_q\vdash_{G}^{k}xS_r[/cbm] следует достижимость [cbm]q\Rightarrow_{x}^{\ast}r[/cbm] (в автомате [cbm]M[/cbm] ), и пусть в грамматике [cbm]G[/cbm] существует вывод [cbm]D[/cbm] длины [cbm]m[/cbm] цепочки [cbm]xS_r[/cbm] из цепочки [cbm]S_q[/cbm] , то есть [cbm]S_q\vdash_{G}^{m}xS_r[/cbm] . Так как длина вывода [cbm]D[/cbm] не меньше 1, то найдется такой нетерминал [cbm]S_{q'}[/cbm] и такое [cbm]a\in V\cup\{\lambda\}[/cbm] , что [cbm]S_q\vdash_{G}aS_{q'}\vdash_{G}^{m-1} xS_r[/cbm] , где [cbm]ay=x[/cbm] (мы выделили первый шаг вывода [cbm]D[/cbm] ). Непосредственная выводимость [cbm]S_q\vdash_{G}aS_{q'}[/cbm] означает, что в множестве правил вывода грамматики [cbm]G[/cbm] содержится правило [cbm]S_q\vdash aS_{q'}[/cbm] и, следовательно, в системе команд [cbm]\delta[/cbm] конечного автомата [cbm]M[/cbm] есть команда [cbm]qa\to q'[/cbm] и тогда [cbm]q\to_{a}q'[/cbm] . Согласно предположению индукции, из того, что [cbm]S_{q'}\vdash_{G}^{m-1}yS_r[/cbm] , следует, что [cbm]q'\Rightarrow_{y}^{\ast}r[/cbm] в [cbm]M[/cbm] . В итоге получаем [cbm]q\to_{a} q'\Rightarrow_{y}^{\ast}r[/cbm] , т.е., так как [cbm]ay=x,~q\Rightarrow_{x}^{\ast}r[/cbm] , что и требовалось.

Если теперь [cbm]x\in L(G)[/cbm] , то в грамматике [cbm]G[/cbm] существует вывод цепочки [cbm]x[/cbm] из аксиомы [cbm]S_{q_0}[/cbm] , то есть [cbm]S_{q_0}\vdash_{G}^{\ast}x[/cbm] . На последнем шаге этого вывода применяется некоторое правило, правая часть которого не содержит вхождений нетерминалов, т.е. правило вида [cbm]S_{q'}\to a[/cbm] . Поскольку любая цепочка в выводе в регулярной грамматике может содержать нетерминал только как последний символ, то [cbm]S_{q_0}\vdash_{G}^{\ast}yS_{q'}\vdash_{G}ya=x[/cbm] . Отсюда следует, что [cbm]q_0\Rightarrow_{y}^{\ast}q'[/cbm] . Кроме того, правило вывода [cbm]S_{q'}\to a[/cbm] может принадлежать множеству [cbm]P[/cbm] тогда и только тогда (по построению [cbm]P[/cbm] ), когда в системе команд автомата [cbm]M[/cbm] есть команда [cbm]q'a\to q_f,~q_f\in F[/cbm] . Следовательно, [cbm]q_0\Rightarrow_{y}^{\ast}q'\to_{a}q_f[/cbm] , что и означает [cbm]q_0\Rightarrow_{x}^{\ast}q_f[/cbm] , то есть [cbm]x\in L(M)[/cbm] .

Итак, доказано включение [cbm]L(G)\subseteq L(M)[/cbm] , и [cbm]L(G)=L(M)[/cbm] , т.е. регулярная грамматика [cbm]G[/cbm] , построенная, как описано выше, по конечному автомату [cbm]M[/cbm] , эквивалентна ему.


Построение конечного автомата по регулярной грамматике

По заданной регулярной грамматике

[cbm]G=(V,N,S,P)[/cbm]

построим конечный автомат [cbm]M=(V,Q,q_0,F,\delta)[/cbm] так, что входной алфавит автомата [cbm]M[/cbm] совпадает с терминальным алфавитом грамматики [cbm]G[/cbm] , множество состояний [cbm]Q[/cbm] совпадает с нетерминальным алфавитом грамматики [cbm]G[/cbm] , пополненным новым состоянием [cbm]f[/cbm] , не принадлежащим объединенному алфавиту грамматики [cbm]G[/cbm] , то есть [cbm]Q=N\cup\{f\}[/cbm] ; начальное состояние [cbm]q_0[/cbm] совпадает с аксиомой [cbm]S[/cbm] , множество заключительных состояний [cbm]F=\{f\}[/cbm] }. Система команд [cbm]\delta[/cbm] определяется следующим образом: команда [cbm]Aa\to B[/cbm] принадлежит [cbm]\delta[/cbm] тогда и только тогда, когда в множестве [cbm]P[/cbm] правил вывода есть правило [cbm]A\to aB[/cbm] , а команда [cbm]Aa\to f[/cbm] принадлежит [cbm]\delta[/cbm] тогда и только тогда, когда правило вывода [cbm]A\to a[/cbm] принадлежит множеству [cbm]P[/cbm] .

Допустимость языка конечным автоматом

Например, по регулярной грамматике [cbm]G_2[/cbm] из примера 7.5 строится конечный автомат с входным алфавитом [cbm]\{a,b,0,1\}[/cbm] , множеством состояний [cbm]\{I,D,f\}[/cbm] , начальным состоянием [cbm]I[/cbm] , единственным заключительным состоянием [cbm]f[/cbm] и такой системой команд (рис. 7.6):

[cbm]\begin{array}{llll}Ia\to D, &\qquad Ib\to D, &\qquad Da\to D, &\qquad Db\to D,\\ D0\to D, &\qquad D1\to D, &\qquad Da\to f, &\qquad Db\to f,\\ D0\to f, &\qquad D1\to f, &\qquad Ia\to f, &\qquad Ib\to f. \end{array}[/cbm]

Обоснование корректности этого построения может быть проведено так же, как и построения регулярной грамматики по конечному автомату ("двойной" индукцией по длине вывода в грамматике и по длине пути в автомате), и мы его опускаем.

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: