1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 5
Текст из файла (страница 5)
Для этихцелей нам понадобятся следующие определение и лемма.Определение. Говорят, что д.к.а. A = hQ, A, δ, q0 , F i обладает свойством вахтера,если для любых q ∈ Q, a ∈ A имеет место δ(q, a) 6= q0 , т. е. автомат находится вначальном состоянии только в самом начале своей работы.Лемма 4 (о вахтере). Для любого д.к.а. A = hQ, A, δ, q0 , F i существует д.к.а. A0 =hQ0 , A, δ 0 , q0 , F 0 i такой, что T (A) = T (A0 ) и A0 обладает свойством вахтера.Доказательство. Мы дадим неформальное доказательство, описав процесс преобразования графической диаграммы автомата A в графическую диаграмму искомогоавтомата A0 (см.
схему преобразования на рисунке):A:c¨¥? a - iH i©}q0Zq1ZZbZZiq2A0 :HH©©H i©q0ca - i½>a½½ q1½½¨- ?c § i¾q̃0biq2§ 6. Свойства автоматных языков19а) Добавим в автомат A новое состояние q̃0 . Если q0 было выделенным, то q̃0 тожесделаем выделенным.б) Для каждой стрелки из q0 в q1 6= q0 добавим в автомат новую стрелку из q̃0 вq1 и пометим ее той же буквой.в) Для каждой стрелки из q0 в q0 добавим в автомат новую стрелку из q̃0 в q̃0 ипометим ее той же буквой.г) Перенаправим все стрелки, приходящие в q0 из q2 (включая стрелки из q0 в q0 )так, чтобы они приходили из q2 в q̃0 .Построенный таким образом автомат обозначим как A0 =hQ0 , A, δ 0 , q0 , F 0 i.
Нетрудно видеть, что A0 детерминированный. В силу пункта (г) автомат A0 обладает свойством вахтера. Равенство T (A) = T (A0 ) следует из того, что если слово w ∈ A∗ читается вдоль пути в автомате A, начинающегося в q0 и заканчивающегося в некоторомr ∈ F , то, преобразовав этот путь в соответствии с пунктами (а)–(г), мы получимпуть в автомате A0 , начинающийся в q0 , заканчивающийся в некотором r0 ∈ F 0 , вдолькоторого читается то же самое слово w, и наоборот, если w читается вдоль пути вавтомате A0 , начинающегося в q0 и заканчивающегося в некотором r0 ∈ F 0 , то, сделавобратное преобразование, мы получим путь в автомате A, который начинается в q0 ,заканчивается в r ∈ F , и вдоль которого читается w.Определение.
Говорят, что подмножество X множества A замкнуто относительнооперации f : An → A, если для любых x1 , . . . , xn ∈ X имеет место f (x1 , . . . , xn ) ∈ X.Теорема 5. Автоматные языки замкнуты относительно объединения, пересечения, дополнения, конкатенации и звездочки Клини.Доказательство. Для каждой из пяти операций мы неформально опишем, как позаданым автоматам, распознающим исходные языки, построить автомат, распознающий результат применения данной операции к исходным языкам. Заметим, что всилу теоремы 3 для каждого из случаев достаточно строить недетерминированныйавтомат.Объединение. Пусть A1 , A2 — детерминированные конечные автоматы над алфавитом A.
Нам необходимо определить автомат A такой, что T (A) = T (A1 ) ∪ T (A2 ).В силу Леммы о вахтере можно считать, что A1 и A2 обладают свойством вахтера.Кроме этого, можно считать, что множества состояний A1 и A2 не пересекаются, впротивном случае следует переименовать состояния.Автомат A строится следующим образом (см. схему построения на рисунке):а) Соединим графические диаграммы автоматов A1 и A2 в одну диаграмму, отождествив их начальные состояния. Объявим полученное таким отождествлением состояние начальным в A. Поскольку множества состояний автоматов не пересекались,никакие другие состояния (кроме начальных) не склеиваются.б) Множеством выделенных состояний A будет объединение множеств выделенных состояний автоматов A1 и A2 .в) Начальное состояние A будет выделенным тогда и только тогда, когда оноявляется выделенным хотя бы в одном из исходных автоматов.idA1i©HH i©A2diHH©©diA1i¢AA2di20Глава II.
Конечные автоматы и формальные грамматикиТакое описание полностью задает автомат A. Поскольку A1 и A2 обладают свойством вахтера, то любой путь по дугам автомата A, который начинается в начальномсостоянии и заканчивается в выделенном состоянии, будет полностью расположенвнутри A1 или внутри A2 . Следовательно, любое слово, распознаваемое A, — этослово, распознаваемое A1 или A2 . С другой стороны, любое слово, распознаваемоеA1 или A2 , очевидно, распознается автоматом A.
Таким образом, автомат A — искомый.Дополнение. Пусть д.к.а. A = hQ, A, δ, q0 , F i распознает язык L, т. е. для любогослова w ∈ A∗ имеет место эквивалентность w ∈ L ⇐⇒ δ ∗ (q0 , w) ∈ F . Отсюдавытекает эквивалентность w ∈/ L ⇐⇒ δ ∗ (q0 , w) ∈/ F . Другими словами, имеет∗место условие w ∈ A \ L ⇐⇒ δ ∗ (q0 , w) ∈ Q \ F . Отсюда следует, что д.к.а A0 =hQ, A, δ, q0 , Q \ F i распознает дополнение L = A∗ \ L.Пересечение. Замкнутость автоматных языков относительно пересечения следует из замкнутости относительно объединения и дополнения, а также из теоретикомножественного тождества A ∩ B = A ∪ B.Конкатенация.
Пусть A1 , A2 — детерминированные конечные автоматы над алфавитом A. Можно считать, что A2 обладает свойством вахтера. Построим автоматA, распознающий язык T (A1 )T (A2 ), следующим образом (см. схему построения нарисунке):а) К каждому выделенному состоянию автомата A1 подвесим копию автомата A2 ,отождествив данное выделенное состояние с начальным состоянием копии.
При этомсчитаем, что остальные состояния автоматов не склеиваются (этого можно добитьсяпутем переименования состояний).б) Начальным состоянием полученного автомата объявляется начальное состояние A1 .в) Выделенными состояниями полученного автомата объявляются все выделенные состояния всех копий автомата A2 . Других выделенных состояний нет.idH i©A1ididH i©A2diHH©©H i©A1iA2diiA2diiA2diВ силу Леммы о вахтере любой путь вдоль дуг нового автомата, начинающийсяв начальном состоянии и заканчивающийся в выделенном состоянии, разбивается надва участка. Первый участок состоит только из дуг автомата A1 и заканчиваетсяв одном из (бывших) выделенных состояний A1 .
Второй участок состоит только издуг соответствующей копии автомата A2 и заканчивается в одном из выделенныхсостояний нового автомата. Отсюда следует, что T (A) = T (A1 )T (A2 ).Звездочка Клини. Пусть A — д.к.а., обладающий свойством вахтера. Построимавтомат A0 , распознающий язык (T (A))∗ , следующим образом (см. схему построенияна рисунке):а) Для каждой дуги автомата A, выходящей из начального состояния, входящей всостояние q и помеченной символом a, проделаем следующее: для каждого выделенного состояния добавим дугу, выходящую из этого выделенного состояния, входящую§ 6. Свойства автоматных языков21в q и помеченную буквой a (если такая дуга уже есть в автомате A, то не добавляемее).б) Начальным состоянием автомата A0 объявляется начальное состояние A.в) Выделенными состояниями автомата A0 объявляются все выделенные состояния A.
Кроме этого, сделаем начальное состояние выделенным (если оно уже небыло таковым).AH© ia - iqdiHH©©A0Hd© ia - i¾ aqdiДокажем, что (T (A))∗ = T (A0 ). Для этого сначала установим справедливостьвключения (T (A))∗ ⊆ T (A0 ). Пусть слово w ∈ (T (A))∗ . Если w = Λ, то w ∈ T (A0 ) всилу пункта (в). Если же w 6= Λ, то слово w представимо в виде w = w1 . . . wn , гдеwi ∈ T (A) для каждого 1 6 i 6 n. Следовательно, для каждого 1 6 i 6 n слово wiчитается вдоль следующего пути в автомате A:q0 =r0isiki isi1 i si2−→ r1 −→ . . . −−→ rki ∈ F,в котором последнее состояние rki i является выделенным. Поэтому в силу пункта (а),для каждого 2 6 i 6 n в новом автомате A0 существует дуга, выходящая из rki−1i−1iiвходящая в r1 и помеченная буквой s1 .
Таким образом, для каждого 2 6 i 6 n словоwi будет читаться вдоль следующего пути в автомате A0 :siki isi1 i si2rki−1−→r−→...−−→ rki ∈ F.1i−1Соединив последовательно все такие пути в одну цепочку, мы получим путь в автомате A0 , который начинается в начальном состоянии, заканчивается в выделенномсостоянии, и вдоль дуг которого читается w. Следовательно, w ∈ T (A0 ).Теперь установим обратное включение T (A0 ) ⊆ (T (A))∗ . Пусть w ∈ T (A0 ). Можносчитать, что w 6= Λ (случай пустого слова тривиален). Следовательно, w читаетсявдоль пути в автомате A0 , который начинается в начальном состоянии q0 и заканчивается в некотором выделенном состоянии q 0 . Заметим, что в силу свойства вахтераq0 6= q 0 , поэтому состояние q 0 является выделенным и в исходном автомате A.
Пустьв данном пути встречается ровно k новых дуг, т. е. дуг, добавленных по пункту (а).Для 1 6 i 6 k введем следующие обозначения. Пусть i-ая новая дуга, встретившаясяsiв данном пути, имеет вид pi −→ri , т. е. выходит из состояния pi , входит в состояниеri и помечена символом si . В частности, pi является выделенным. Обозначим черезw0 слово, которое читается вдоль участка нашего пути, начинающегося в состоянииq0 и заканчивающегося в p1 . Для 1 6 i 6 k − 1 обозначим через wi слово, которое читается вдоль участка пути, начинающегося в pi и заканчивающегося в pi+1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
