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

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

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

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

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


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

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


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


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


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

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


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


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


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

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


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


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




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


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

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

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


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


[math]\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}[/math]

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


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

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


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


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


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


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

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


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


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


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


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


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




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


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

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

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


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

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


[math]\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}[/math]

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


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


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


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

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