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

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

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

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


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

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


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


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


L(M_1)=L(M_2).

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


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


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


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

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


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


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




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


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

M=(V,Q,q_0,F,\delta).

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


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


\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}

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


q_0\to_{0}q_1\to_{0}q_2\to_{1}q_2 и S_{q_0}\vdash 0 S_{q_1}\vdash 00 S_{q_2}\vdash 001..

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


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


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


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


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

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


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


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


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


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


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




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


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

G=(V,N,S,P)

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


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

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


\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}

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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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