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



жүктеу 397.98 Kb.
бет1/3
Дата17.04.2016
өлшемі397.98 Kb.
түріМетодическая разработка
  1   2   3
: books -> met files
books -> Европа Америка Австралия Литературно-библиографический справочник
books -> 100 великих спортсменов
met files -> Н. И. Лобачевского Использование проектного метода обучения на примере преподавания курса «Микроэкономика» Методическое пособие
met files -> Н. И. Лобачевского История стран запада на рубеже XIX-XX веков Планы практических занятий и рекомендованная литература
met files -> Участие почвенных микроорганизмов
met files -> Конфликты в тропической африке
met files -> Н. И. Лобачевского Крылова Е. В., Таламанова М. Н
met files -> Тема Введение в курс
met files -> Е. В. Крылова С. В. Копылова анатомия человека спланхнология
met files -> Программа курса " основы религиоведения"
Министерство образования Российской Федерации

Нижегородский государственный университет

им. Н.И. Лобачевского

Факультет вычислительной математики и кибернетики

Учебно-методическая разработка для самостоятельной работы студентов

по курсу «Теория алгоритмов и математическая логика»

при изучении темы «Концепции конечного автомата и регулярного языка. Операции над регулярными языками»


Нижний Новгород 2000 г.


УДК 518.5

Методическая разработка предназначена для самостоятельной работы студентов специальности «Прикладная информатика» над материалом темы «Концепции конечного автомата и регулярного языка. Операции над регулярными языками», входящей в состав учебного курса «Теория алгоритмов и математическая логика». Вводятся понятие формального языка и действия над формальными языками, включая основные теоретико-множественные операции. Излагается концепция конечного автомата (в детерминированном и недетерминированном вариантах); регулярные языки представляют собой класс языков, распознаваемых конечными автоматами. Показывается, что операции, объединения, пересечения, дополнения, конкатенации и итерации не выводят из класса регулярных языков. Приводятся соответствующие алгоритмы синтеза конечных автоматов.

Составители:

преподаватели кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ доцент, д.т.н. Коган Д.И. и ассистент Бабкина Т.С.




1. Понятие языка, примеры языков, операции над языками.
Алфавитом именуем произвольное непустое конечное множество символов; символы произвольного алфавита называем его буквами. В качестве примеров укажем русский алфавит (с включением или невключением в него знаков препинания), латинский алфавит, объединение указанных алфавитов, множество цифр десятичной или двоичной систем счисления. В общем виде алфавит определяем как совокупность А={a1, a2, ..., an}; в числе букв алфавита А может быть и специальный символ пробела (пустой буквы), этот символ обычно обозначается e (сокращение английского «empty» – пустой).

Словом в алфавите А называем произвольную конечную последовательность его букв; одна и та же буква в этой последовательности может встречаться многократно. Длиной слова (обозначение l()) называем количество букв в этом слове. Специальным символом будем обозначать единственное слово, имеющее нулевую длину (пустое слово); следует различать пустое слово и слово е, состоящее из одной пустой буквы; длина слова е (пробела) равна единице. В алфавите А={a1, a2, ..., an} можно записать nl различных слов длины l, где l=0, 1, 2, ... . Множество всех слов алфавита А будем обозначать А*. Специально отметим, что в совокупность А* входит и пустое слово. Мощность множества всех слов алфавита А счетна.

Если и – два произвольных слова в алфавите А, то  – результат приписывания справа слова к слову . Для любых слов и считаем, что ==, =.



Языком в алфавите А называем произвольное подмножество слов L из А*. Язык L именуем конечным, если в его составе конечное множество слов; язык L бесконечен, если в его составе бесконечное множество слов. Совокупности всех слов русского, всех слов английского языка представляют собой примеры конечных языков. Множество записей всех простых чисел в десятичной или двоичной системе счисления является бесконечным языком. Множество всех языков алфавита А имеет континуальную мощность.

Язык L в алфавите А называем универсальным, если L*. Язык L называем пустым, если множество L пусто (L=).

Пусть L1 и L2 – языки в алфавите А. Через L1L2 и L1L2 будем

обозначать объединение и пересечение этих языков соответственно. Слово принадлежит объединению двух языков, если оно принадлежит по меньшей мере одному из них; слово принадлежит пересечению двух языков, если оно принадлежит как одному, так и другому языку. Пусть L – язык в алфавите А; через Lс будем обозначать дополнение этого языка. Язык Lс образуют слова алфавита А, не входящие в состав языка L: Lс=А*\L. Операции объединения, пересечения и дополнения – основные теоретико-множественные операции.

Пусть L1 и L2 – языки в алфавите А. Через L1\L2 будем обозначать разность языков L1 и L2 . Слово из А* считается принадлежащим L1\L2 тогда и только тогда, когда оно принадлежит языку L1, но не принадлежит языку L2. Очевидно, что операция разности представима через основные теоретико-множественные операции: L1\L2=L1(L2)с.

Дополнительно введем несколько специальных операций над языками. Пусть L1 и L2 – языки в алфавите А. Через L1L2 обозначим язык, определяемый следующим образом: слово принадлежит языку L1L2 тогда и только тогда, когда это слово можно разбить на две последовательные части (т.е. представить в виде =12) так, что первая часть является словом языка L1, а вторая часть – словом языка L2. Операция  называется конкатенацией (сцепкой) языков. Знак  нередко будет опускаться, тогда конкатенация языков L1 и L2 записывается L1L2. Язык L1L2 получается приписыванием к словам языка L1 слов языка L2 в качестве окончаний. Отметим, что если к произвольному слову приписать в качестве окончания пустое слово, то результатом будет слово . Если языки L1 и L2 конечны, причем в составе первого языка m слов, а в составе второго n слов, то язык L1L2 состоит максимум из mn слов. Если один из языков L1, L2 пуст, то L1L2 – также пустой язык.

Введем операцию возведения языка в степень. Полагаем:

L0={};

L1=L;

L2=LL;

Ln+1=LnL, n=2, 3, ...;

таким образом, понятие степени Li языка L определено для любого i=0, 1, 2, 3, ... .

Далее через L* обозначим объединение всех степеней языка L:

L*=Li.

Введенную операцию именуем итерацией. Отметим, что пустое слово принадлежит итерации любого языка. Непустое слово принадлежит итерации языка L тогда и только тогда, когда это слово можно разбить на некоторое количество последовательных частей (подслов) так, что каждая часть принадлежит языку L. Если язык L состоит из всех однобуквенных слов алфавита А, то итерацией этого языка является универсальный язык А*. Отметим, что для любого языка L имеет место (L*)*=L*.

На множестве языков иногда рассматривают и следующую одноместную операцию ( )+:

(L)+=Li.

Языки L* и L+ отличаются один от другого разве что пустым словом. Слово всегда принадлежит языку L*. Языку L+ оно принадлежит тогда и только тогда, когда принадлежит языку L.


2. Концепции конечного автомата и регулярного языка.
В кибернетике автоматами называют технически или программно реализованные модули, предназначенные для переработки поступающей информации. Конечный автомат – это модуль, имеющий конечное число возможных состояний и функционирующий в дискретном времени. В данном пособии конечные автоматы изучаются как абстрактные алгоритмические устройства, предназначенные для обработки слов фиксированного входного алфавита. Считаем, что обработку произвольного слова во входном алфавите А автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние; состояние, в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины l автомат работает l тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.

Формально конечный автомат К определяем как совокупность



К={Q, A, q0, g, F},

где Q={q0, q1, q2, ..., qm} – множество состояний автомата; А={а1, а2, ..., аn} – входной алфавит; q0 – специально выделенное состояние автомата, именуемое начальным состоянием; g – функция переходов конечного автомата, представляющая собой отображение типа QxАQ (если g(qi,аj)=qk, то автомат из состояния qi под воздействием буквы аj должен перейти в состояние qk); F – специально выделенное подмножество состояний автомата, которые мы условно будем именовать «хорошими», F Q.

Пусть – входное слово, l()=р. Через q(t) обозначим состояние, в котором оказывается автомат К через t тактов работы над этим словом (здесь t=0, 1, 2, ..., р):

q

(0)=q0;

. . .

Будем говорить, что слово принимается автоматом К, если q(р)F. Введем в рассмотрение язык L(К): слово принадлежит языку L(К), если данное слово принимается автоматом К. Язык L(К) именуем языком, распознаваемым данным конечным автоматом. Язык L назовем регулярным, если для него можно построить распознающий конечный автомат.

Конечный автомат удобно задавать диаграммой его переходов. Диаграмма представляет собой ориентированный граф, вершины которого одноименны состояниям автомата; дуга из вершины qi, в вершину qk с надписанной над ней буквой аj проводится тогда и только тогда, когда g(qi,аj)=qk. В случае, когда переход из qi в qk осуществляется под воздействием любой из букв некоторого подмножества S, SА, все буквы этого подмножества подписываются над соответствующей дугой (вместо перечня всех букв допускается сокращенная запись «xS» или просто «S»). Если произвольное состояние qi входит в F, то данный факт на диаграмме отмечается жирным кружком, выделяющим вершину qi.

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

диаграммы его переходов.

На рис. 2.1 показана диаграмма автомата K1, работающего над словами алфавита A={a,b,c}. Автомат имеет два состояния, q0 и q1, причем «хорошим» является только состояние q1. Начав работу в состоянии q0, автомат под воздействием букв a, b из этого состояния не выходит; под воздействием буквы с реализуется переход в состояние q1; любая далее поступающая буква оставляет автомат в том же состоянии. Таким образом, автомат K1 распознает язык L1, состоящий из слов, имеющих в своем составе букву с. Данный язык является регулярным.





Приведем еще несколько примеров регулярных языков в том же алфавите: L2 - множество слов, в которых буква а встречается четное число раз; L3 - множество слов, начинающихся и заканчивающихся одинаковой буквой; L4 - множество слов, содержащих подслово =abbc; L5 - множество слов, при чтении которых слева направо разность между числом встреченных букв a и b никогда не превосходит 2. Диаграммы конечных автоматов K2 - K5, распознающих языки L2 L5 соответственно, представлены на рисунках 2.2 – 2.5. Информацию об обработанной части входного слова автомат “помнит” своим состоянием. Так, например, автомат K5, обработав некоторую часть входного слова, оказывается в состоянии qx, если в прочитанной им части входного слова число встреченных букв а превышает число встреченных букв b на x; здесь x{-2, -1, 0, 1, 2}; автомат оказывается в состоянии qплох, если в некоторый момент работы автомата абсолютная величина разности между числом обработанных букв а и числом обработанных букв b превысила 2.

















Состояние конечного автомата назовем поглощающим, если любая входная буква не выводит автомат из этого состояния. Поглощающее состояние назовем положительно поглощающим, если оно принадлежит F, и отрицательно поглощающим в противном случае. В автоматах K1 и K4 полижительно поглощающими являются состояния q1 и q4 соответственно, в автомате K5 отрицательно поглощающим является состояние qплох.

Можно считать, что каждый автомат имеет не более одного положительно поглощающего и не более одного отрицательно поглощающего состояния (если положительно или отрицательно поглощающих состояний несколько, то они легко могут быть заменены одним). Обычно в диаграмме переходов отрицательно поглощающее состояние не изображается; если из некоторого состояния по некоторой букве переход не указан, то предполагается, что он ведет в отрицательно поглощающее состояние. Представленный на рисунке 2.6 конечный автомат распознает в алфавите А язык, состоящий из слов, в которые буква с входит ровно один раз. Этот автомат имеет 3 состояния, отрицательно поглощающее состояние qплох (в него автомат переходит из состояния q1 по букве с) в диаграмме не указано.




Введем алфавит B={0, 1, 2, …, 9}, каждое слово в этом алфавите трактуем как целое неотрицательное число. Пусть L(p) обозначает множество слов – записей в десятичной системе счисления всех целых неотрицательных чисел, кратных натуральной константе p; будем считать, что языку L(p) дополнительно принадлежит также пустое слово . Покажем, что L(p) – регулярный язык. Распознающий L(p) конечный автомат К(p) можно построить следующим образом. Состояниями автомата считаем q0, q1, q2, qp–1; из произвольного состояния qi по цифре х, х{0, 1, 2, ... ,9}, автомат переходит в состояние qj, если остаток от деления числа iх (т.е. числа, получаемого приписыванием к числу i цифры х справа) на p равен j. Благодаря указанной структуре переходов автомат, обработавший, начиная от начального состояния q0, записанное в десятичной системе счисления целое неотрицательное число , оказывается в состоянии qy тогда и только тогда, когда остаток от деления на p равен у. Единственным «хорошим» состоянием автомата К(p) следует считать q0. На рис. 2.7 и 2.8 представлены диаграммы конечных автоматов, распознающих числа, делящиеся на 2 и на 3 соответственно.




Отметим, что в ряде случаев, исходя из иных принципов, можно построить распознающие делимость на p автоматы c меньшим числом состояний. На рис. 2.9 представлен имеющий два состояния конечный автомат, распознающий числа, кратные пяти (используется тот факт, что кратное пяти число имеет своей последней цифрой 0 или 5).




По конечному автомату К(p) легко строится автомат К(p)[], распознающий язык L(p)\{}. Для получения диаграммы переходов автомата К(p)[] в имеющейся диаграмме переходов автомата К(p) делаются следующие изменения: начальное состояние q0 автомата К(p) переименовываем в q0; вводим новое начальное состояние q0; по произвольной цифре х из q0 автомат К(p)[] реализует переход в то же состояние, что и автомат К(p) из своего начального состояния (при этом вместо перехода в q0 всегда реализуется переход в q0); единственным «хорошим» состоянием автомата К(p)[] следует считать q0. Согласно изложенному, начальное состояние автомата К(p)[] является невозвратным – в процессе обработки любого входного слова, выйдя из этого состояния, автомат в него никогда не вернется. На рис.2.10 представлен конечный автомат К(3)[], распознающий числа, кратные трем (пустое слово, в язык, распознаваемый данным автоматом, не входит).




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



Теорема 2.1. Пустой язык, универсальный язык, любой конечный язык в произвольном фиксированном алфавите А={а1, а2, ... , аn} являются регулярными языками.

Любой конечный автомат с пустым множеством «хороших» состояний F распознает пустой язык. Любой конечный автомат, в котором каждое состояние «хорошее», распознает универсальный язык. Конечные автоматы, распознающие пустой и универсальный языки и имеющие только одно состояние, представлены на рис. 2.11 и 2.12 соответственно (x- произвольная буква алфавита A).




Сейчас предположим, что язык L конечен, пусть L={1, 2, ... , p}. Диаграмму конечного автомата К(L), распознающего слова языка L, строим в виде дерева, корнем которого является вершина q0, образующая нулевой уровень. В вершине q0 реализуем ветвление (далее эта операция будет выполняться и для других вершин): проводим из данной вершины n дуг, над первой надписываем а1, над второй – а2, ... , над n-ой – аn, концами этих дуг являются n вершин следующего (в данном случае – первого) уровня. Выполнив ветвление в каждой из вершин первого уровня, получаем n2 вершин второго уровня; выполнив ветвление в каждой из вершин второго уровня, получаем n3 вершин третьего уровня, и т.д. Процесс продолжается до тех пор, пока не будут построены вершины r-го уровня, где r – число букв в самом длинном слове языка L. Операции ветвления в вершинах r-го уровня не выполняются; если на вход автомата, находящегося в некотором состоянии из r-го уровня, поступает еще одна буква, он переходит в неотображенное диаграммой отрицательно поглощающее состояние qплох. Между вершинами-состояниями построенного r-уровневого дерева и имеющими длину не больше, чем r, словами алфавита А существует взаимно однозначное соответствие – каждому такому слову сопоставляется состояние, в котором оказывается автомат, обработавший, начиная от q0, данное слово. Каждое отображенное в дереве состояние автомата К(L) называем именем соответствующего ему слова (состояние q0 получает при этом имя пустого слова). Множество F «хороших» состояний автомата К(L) считаем следующим: 1, 2, ... p. Построение распознающего язык L конечного автомата закончено. Теорема доказана полностью.

В приведенном доказательстве изложен универсальный алгоритм синтеза автомата, распознающего конечное множество слов. Отметим, что в конкретных задачах автоматы, распознающие те или иные конечные языки, нередко строятся существенно проще. На рис. 2.13 представлен автомат, распознающий конечный язык A={0, 01, 10, 001, 101, 1100}.


0




  1   2   3


©netref.ru 2017
әкімшілігінің қараңыз

    Басты бет