Методическая разработка предназначена для самостоятельной работы студентов специальности «Прикладная информатика»

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

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

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

Построить конечный автомат, распознающий дополнение к языку, заданному недетерминированным конечным автоматом, диаграмма которого представлена на рис. 3.8

Построить недетерминированный конечный автомат, распознающий объединение языков, заданных конечными автоматами, диаграммы которых представлены на рис. 3.9

Построить недетерминированный конечный автомат, распознающий множество чисел, делящихся на 25.

Сначала предположим, что q¹₀F¹; выполнение данного условия будем именовать общим случаем. Через М обозначим совокупность тех дуг (вместе с надписанными над ними буквами) в диаграмме переходов автомата К¹, которые своими концами имеют вершины подмножества F¹. Специально отметим, что (в случае их присутствия в диаграмме автомата К¹) в М входят и петли, т.е. дуги вида (q¹_j, q¹_j), где q¹_jF¹. Для каждой принадлежащей множеству М дуги (q¹_i,q¹_j) с надписанной над ней буквой х входного алфавита строим дугу-дубликат (q¹_i,q²₀) с той же надписанной буквой. Так реализуется «сцепка» диаграмм переходов конечных автоматов К₁ и К₂, результатом которой является диаграмма переходов конструируемого недетерминированного конечного автомата К; начальным состоянием автомата К объявляется состояние q¹₀, совокупность F «хороших» состояний автомата К считается совпадающей с F². Согласно выполненному построению, до перехода по некоторой дуге-дубликату в состояние q²₀, конечный автомат К функционирует как автомат К₁, после перехода в q²₀ и до завершения работы – как К₂.

Сконструированный конечный автомат проверяет, можно ли входное слово , А*, разбить на две последовательные части ₁ и ₂ так, что ₁L₁ и ₂L₂ (указанное разбиение оказывается возможным тогда и только тогда, когда существует способ работы данного автомата такой, что, обработав тестируемое слово , автомат оказывается в состоянии из F).

Действительно, конечный автомат К, начиная работу из состояния q₀¹, начальную часть произвольного входного слова  обрабатывает в режиме автомата К₁. Пусть на некотором такте работы автомата K в данном режиме поступила буква х. Предположение о том, что она является последней в принадлежащей L₁ части ₁ входного слова , возникает тогда, когда под воздействием х автомат К₁ может перейти в свое «хорошее» состояние. На данном такте для недетерминированного автомата К по его построению имеем две возможности:

1) выполнить переход в соответствии с диаграммой автомата К₁ (при этом считается, что данной буквой х начальная часть ₁, ₁L₁, входного слова не заканчивается);

2) под воздействием х по соответствующей дуге-дубликату перейти в состояние q²₀ (здесь считается, что буквой х завершается первая часть ₁, ₁L₁, входного слова ). Далее автомат К будет функционировать как автомат К₂; его работа должна завершиться в состоянии, принадлежащем подмножеству F², если оставшаяся часть ₂ тестируемого слова  принадлежит языку L₂.

За счет своей недетерминированности, автомат К может по-разному разбивать входное слово  на части ₁, ₁L₁, и ₂. Слово  принадлежит языку, распознаваемому автоматом К тогда и только тогда, когда его можно представить в виде =₁₂, где ₁L₁ и ₂L₂; отметим, что из условия q¹₀F¹ следует ₁.

Первым специальным случаем назовем следующую ситуацию: q¹₀F¹ и q²₀F². Специфика ситуации заключается в том, что в язык L₁ входит и пустое слово. В силу возможного равенства ₁=, следует конструировать автомат К таким образом, чтобы для любой буквы х входного алфавита А имелась дополнительная возможность перехода автомата из начального состояния q¹₀ в состояние, в которое по данной букве из своего начального состояния переходит автомат К₂.

Для первого специального случая «сцепка» диаграмм переходов конечных автоматов К₁ и К₂, результатом которой является диаграмма переходов конструируемого недетерминированного конечного автомата К, реализуется в два этапа:

1) идентично тому, как это делается в общем случае, проводятся все дуги-дубликаты;

2) для каждой буквы х входного алфавита проводится дополнительная дуга (q¹₀, g²(q²₀,х)) с надписанной над ней буквой х. Как и ранее, начальным состоянием автомата К объявляется состояние q¹₀, совокупность F «хороших» состояний автомата К считается совпадающей с F².

Вторым специальным случаем назовем следующую ситуацию: q¹₀F¹ и q²₀F². Специфика ситуации заключается в том, что как в язык L₁, так и в язык L₂ входит пустое слово; следовательно, пустое слово принадлежит и конкатенации языков L₁L₂. Отличие алгоритма построения недетерминированного автомата К в данной ситуации от первого специального случая только в назначении множества «хороших» его состояний. В данном случае считается F=F²{q¹₀}.

Отметим, что процедура синтеза автомата, распознающего конкатенацию языков, определяемых недетерминированными конечными автоматами К*₁ и К*₂, реализуется идентичным изложенному образом.

Рассмотрим ряд примеров.

Диаграммами переходов, представленными на рис. 4.1, заданы конечные автоматы, распознающие языки L₁ и L₂ (отметим, что автомат, распознающий язык L₁, недетерминированный). На рис. 4.2 представлена диаграмма переходов недетерминированного конечного автомата, распознающего язык L₁L₂.

После того, как установлена замкнутость класса регулярных языков относительно операции конкатенации, легко доказать замкнутость этого класса и относительно операции возведения в любую целую неотрицательную степень. Пусть L – произвольный регулярный язык. Так как по определению степени языка L¹=L, получаем, что L¹ – регулярный язык. Предположим, что язык L^k регулярен, здесь k – произвольная натуральная константа. Так как язык L^k+1=L^kL является результатом конкатенации регулярных языков L^k и L, то L^k+1 – также регулярный язык. Таким образом, регулярность языка Lⁿ при любом n=1, 2, 3, ... следует из принципа математической индукции. Язык L⁰ также регулярен, ибо он конечен, имеет в своем составе только пустое слово .

Рассмотрение проблемы синтеза по распознающему язык L конечному автомату К конечного автомата К* (вообще говоря, недетерминированного), распознающего язык L*, начнем с частного случая, когда в диаграмме автомата К нет дуг, входящих в вершину q₀; состояние q₀ в такой ситуации является невозвратным – выйдя из q₀ на первом такте работы над любым словом , автомат К в него никогда уже не вернется. Алгоритм построения по имеющейся диаграмме переходов конечного автомата К диаграммы переходов недетерминированного конечного автомата К*, распознающего язык L*, в данном частном случае (назовем его алгоритмом А) достаточно прост. Через М обозначим совокупность тех дуг (вместе с надписанными над ними буквами) в диаграмме переходов автомата К, которые своими концами имеют вершины из подмножества F данного автомата. Специально отметим, что (в случае их присутствия в диаграмме автомата К) в М входят и петли, т.е. дуги вида (q_j, q_j), где q_jF. Реализуя алгоритм А, для каждой принадлежащей множеству М дуги (q_i, q_j) с надписанной над ней буквой х входного алфавита строим дугу-дубликат (q_i, q₀) с той же надписанной буквой. Начальным состоянием конструируемого автомата считаем q₀, это же состояние считаем единственным «хорошим» состоянием в К*. Построение диаграммы переходов автомата К* закончено.

Автомат К* проверяет, принадлежит ли произвольное входное слово  языку L*, т.е. можно ли разбить данное слово на некоторое число р последовательных частей ₁, ₂,…, _р так, что каждое подслово _i, принадлежит L (указанное разбиение оказывается возможным тогда и только тогда, когда существует способ работы данного автомата такой, что обработав тестируемое слово , автомат оказывается в «хорошем» состоянии).

Действительно, начальную часть произвольного непустого входного слова  конечный автомат К*, начиная работу из состояния q₀, обрабатывает в режиме автомата К. Предположение о том, что поступающая на некотором такте произвольная буква х является последней в принадлежащей L первой части входного слова, возникает тогда, когда под воздействием х автомат К может перейти в свое «хорошее» состояние. На данном такте для недетерминированного автомата К* по его построению имеем две возможности:

1. 
   выполнить переход в соответствии с диаграммой автомата К (при этом считается, что данной буквой х часть ₁, ₁L, входного слова не заканчивается);
   
2. 
   под воздействием х по соответствующей дуге-дубликату перейти в состояние q₀ (здесь считается, что буквой х завершается часть ₁, ₁L, входного слова ). Если данная буква х оказалась в слове  последней, автомат работу заканчивает, его заключительное состояние оказывается «хорошим», слово  языку L* принадлежит.
   

Представление входного слова  в виде =₁₂..._р, где каждое подслово _i, принадлежит L, оказывается возможным тогда и только тогда, когда существует способ работы автомата К* такой, что, обработав тестируемое слово , он оказывается в «хорошем» состоянии q₀.

Заметим, что, если множество «хороших» состояний автомата К* изменить, считать его совпадающим с множеством F исходного автомата К, то получаемый автомат распознает язык L⁺.

Применим алгоритм А к диаграмме конечного автомата К, представленной на рис. 4.7. В результате получим диаграмму конечного автомата К* (рис 4.8). Автомат К функционирует в алфавите {a,b,c}и распознает язык L, состоящий из слов, которые начинаются на букву с и в каждом из которых буква с встречается ровно два раза. Автомат К* распознает итерацию языка L. Непустое слово  принимается автоматом К* тогда и только тогда, когда буква с встречается в нем любое четное, отличное от нуля число раз.

Сейчас рассмотрим определяемый представленной на рис. 4.9 диаграммой конечный автомат К, распознающий язык L. Слово  в алфавите {a,b,c} принадлежит языку L тогда и только тогда, когда оно имеет вид аⁱbc, здесь i – произвольное целое неотрицательное число. Если не обратить внимание на тот факт, что начальное состояние автомата К не является невозвратным, и непосредственно к диаграмме данного автомата применить алгоритм А, то получим в результате автомат, который распознает язык, являющийся расширением языка (L)*. В частности, этому языку будут принадлежать не входящие в (L)* слова а, аа, ааа и т.д. Для того, чтобы построить автомат, распознающий язык (L)*, перед применением алгоритма А выполним преобразование автомата К, обеспечивающее невозвратность начального состояния. Диаграмму переходов автомата К (см. рис. 4.10) по диаграмме автомата К строим следующим образом: вводим дублирующее для q₀ состояние q₀¹; считаем, что по букве а автомат не остается в состоянии q₀, а переходит в состояние q₀¹; из состояния q₀¹ по букве а реализуется петля, по букве b – переход в состояние q₁. Легко видеть, что автоматы К и К распознают один и тот же язык L, но для построения автомата, распознающего (L)*, к автомату К (его начальное состояние является невозвратным) можно применить алгоритм А. В результате получаем автомат (К)*, диаграмма переходов которого представлена на рис.4.11. (Заметим, что состояние q₂ в автомате (K)* становится отрицательно поглощающим, поэтому на диаграмме его можно не изображать.)

Изложим общий алгоритм А₀ преобразования произвольного конечного автомата К, в котором состояние q₀ не является невозвратным, к распознающему тот же язык автомату К с невозвратным начальным состоянием. С этой целью: для начального состояния q₀ автомата К вводим дублирующее состояние q₀¹; все дуги (с надписанными над ними буквами), которые в диаграмме исходного автомата входят в вершину q₀, переориентируем в q₀¹ (при этом каждая петля (q₀, q₀) преобразуется в дугу (q₀, q₀¹)); по каждой имеющейся дуге (q₀, q_i) с надписанной над ней буквой, здесь q_i – произвольное состояние автомата К, проводим дугу (q₀¹, q_i) с той же надписанной буквой (при этом для каждой ранее имевшейся петли (q₀, q₀) проводится, с той же надписанной буквой, петля (q₀¹, q₀¹)); множество «хороших» состояний автомата К считаем совпадающим с множеством «хороших» состояний исходного автомата К; если q₀F, то q₀¹ также принадлежит F.

Синтез по заданной диаграмме переходов конечного автомата К, распознающего язык L, диаграммы переходов конечного автомата К*, распознающего язык L*, в общем случае выполняется следующим образом: сначала применяется алгоритм А₀, обеспечивающий невозвратность начального состояния q₀, затем – алгоритм А.

Предварительное применение алгоритма А₀ излишне, когда состояние q₀ в исходном автомате К – невозвратное. Легко показать, что оно излишне и тогда, когда это состояние в автомате К является «хорошим». Действительно, в случае, когда начальное состояние исходного автомата не является невозвратным, автомат, конструируемый применением алгоритма А, может определять расширение языка L* только за счет того, что состояние q₀ объявляется «хорошим» (данное состояние непременно должно стать «хорошим», ибо L*). Но если оно уже в исходном автомате К было «хорошим», то для получения требуемого результата достаточно непосредственное применение алгоритма А. На рис. 4.12 представлена диаграмма конечного автомата, который определяет язык, состоящий из слов, в которых буква с не встречается или встречается два раза. Т.к. начальное состояние является «хорошим», то для построения итерации можно сразу применить алгоритм А (рис. 4.13).

Построить конечный автомат, распознающий конкатенацию языков, заданных конечными автоматами, диаграммы которых представлены на рис. 4.14, в случаях, когда подмножества «хороших» состояний этих автоматов определяются следующим образом:

1. 
   F₁={q₁}, F₂={q₃};
   
2. 
   F₁={q₀}, F₂={q₁, q₂};
   
3. 
   F₁={q₀}, F₂={q₀, q₃}.
   

Построить конечный автомат, распознающий конкатенацию языков, заданных конечными автоматами, диаграммы которых представлены на рис. 4.15, в случаях, когда подмножества «хороших» состояний этих автоматов определяются следующим образом:

1. 
   F₁={q₁, q₂}, F₂={q₀};
   
2. 
   F₁={q₀}, F₂={q₃};
   
3. 
   F₁={q₀, q₁}, F₂={q₀}.
   

Построить конечный автомат, распознающий итерацию языка, заданного конечным автоматом, диаграмма которого представлена на рис. 4.16, в случаях, когда подмножество «хороших» состояний этого автомата определяется следующим образом:

1. 
   F={q₁, q₂};
   
2. 
   F={q₀, q₄};
   
3. 
   F={q₃, q₄}.
   

Построить конечный автомат, распознающий итерацию языка, заданного конечным автоматом, диаграмма которого представлена на рис. 4.17, в случаях, когда подмножество «хороших» состояний этого автомата определяется следующим образом:

1. 
   F={q₁, q₂};
   
2. 
   F={q₀, q₄};
   
3. 
   F={q₃, q₄}.