Файл: Методические указания к выполнению контрольной работы по дисциплине Дискретная математика для обучающихся 2 курса.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 101
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
1 x2 x4 x3)
А и В содержат одинаковый сомножитель (подчеркнуты). Поэтому осуществляет операцию приведения подобных членов: в А или В заменяем его на 1 или, что то же самое, вычеркиваем его из А или из В.
Окончательно имеем с.к.н.ф.
F = АВ= (x1 x3 x2 x4) (x1 x3 x2 x4) (x1 x2 x4 x3).
Глава 4. РАСПОЗНАЮЩИЕ КОНЕЧНЫЕ АВТОМАТЫ
Распознающими конечными автоматами являются конечные автоматы, результатом работы которых является обнаружение некоторого свойства в заданном тексте. Обработку произвольного слова
во входном алфавите 
автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние; состояние в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины 
автомат работает тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.
Формально конечный автомат
определяется как совокупность
,
где
– множество состояний автомата; 
– входной алфавит; 
– специально выделенное состояние автомата, именуемое начальным состоянием; 
– функция переходов конечного автомата, представляющая собой отображение типа 
(если 
, то автомат из состояния 
под воздействием буквы 
должен перейти в состояние 
);
– специально выделенное подмножество состояний автомата, которые условно называются «хорошими», 
. (соответственно «плохими» называются состояния из множества 
).
Пусть
– входное слово, 
. Через 
обозначим состояние, в котором оказывается автомат 
через 
тактов работы над этим словом (здесь 
): 
, 
, 
, …, 
.
Слово
принимается автоматов , если 
. Введем в рассмотрение язык 
: слово принадлежит языку , если данное слово принимается автоматом . Язык называется языком, распознаваемым данным конечным автоматом.
Определение 1. Язык
называется регулярным, если для него можно построить распознающий конечный автомат.
Конечный автомат удобно задавать диаграммой его переходов. Диаграмма представляет собой ориентированный граф, вершины которого одноименны состояниям автомата; дуга из вершины
в вершину 
с надписанной над ней буквой 
проводится тогда и только тогда, когда 
. В случае, когда переход из в осуществляется под воздействием любой из букв некоторого подмножества 
, 
, все буквы этого подмножества подписываются над соответствующей дугой (вместо перечня всех букв допускается сокращенная запись «
» или « ». Если произвольное состояние входит в 
, то данный факт на диаграмме отмечается жирным кружком, выделяющим вершину .
На рис.1 примера 1 показана диаграмма автомата
, работающего над словами алфавита 
. Автомат имеет два состояния: 
и 
, причем «хорошим» является только состояние . Начав работу в состоянии , автомат под воздействием букв 
из этого состояния не выходит; под воздействием буквы
реализуется переход в состояние 
; любая далее поступающая буква оставляет автомат в том же состоянии. Таким образом, автомат 
распознает язык 
, состоящий из слов, имеющих в своем составе букву .
П
ример 1.
Рисунок 1.
Класс регулярных языков замкнут относительно основных теоретико-множественных операций – объединения, пересечения, разности.
Пусть
и 
- регулярные языки, распознаваемые конечными автоматами 
и 
соответственно. Считаем, что 
и 
. Автомат 
, распознающий язык 
строим следующим образом. Полагаем 
; каждое состояние конструируемого автомата содержит две компоненты, левую и правую. Начальным состоянием нового автомата считаем 
, а функцию переходов g определяем следующим образом:
.
Очевидно, по первой компоненте автомат
моделирует действия автомата 
А и В содержат одинаковый сомножитель (подчеркнуты). Поэтому осуществляет операцию приведения подобных членов: в А или В заменяем его на 1 или, что то же самое, вычеркиваем его из А или из В.
Окончательно имеем с.к.н.ф.
F = АВ= (x1 x3 x2 x4) (x1 x3 x2 x4) (x1 x2 x4 x3).
Глава 4. РАСПОЗНАЮЩИЕ КОНЕЧНЫЕ АВТОМАТЫ
Распознающими конечными автоматами являются конечные автоматы, результатом работы которых является обнаружение некоторого свойства в заданном тексте. Обработку произвольного слова
во входном алфавите автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние; состояние в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины автомат работает тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.Формально конечный автомат
определяется как совокупность ,где
– множество состояний автомата; – входной алфавит; – специально выделенное состояние автомата, именуемое начальным состоянием; – функция переходов конечного автомата, представляющая собой отображение типа (если , то автомат из состояния под воздействием буквы должен перейти в состояние
);
– специально выделенное подмножество состояний автомата, которые условно называются «хорошими», . (соответственно «плохими» называются состояния из множества ).Пусть
– входное слово, . Через обозначим состояние, в котором оказывается автомат через тактов работы над этим словом (здесь ): , , , …, .Слово
принимается автоматов , если . Введем в рассмотрение язык : слово принадлежит языку , если данное слово принимается автоматом . Язык называется языком, распознаваемым данным конечным автоматом. Определение 1. Язык
называется регулярным, если для него можно построить распознающий конечный автомат.
Конечный автомат удобно задавать диаграммой его переходов. Диаграмма представляет собой ориентированный граф, вершины которого одноименны состояниям автомата; дуга из вершины
в вершину с надписанной над ней буквой проводится тогда и только тогда, когда . В случае, когда переход из в осуществляется под воздействием любой из букв некоторого подмножества , , все буквы этого подмножества подписываются над соответствующей дугой (вместо перечня всех букв допускается сокращенная запись « » или « ». Если произвольное состояние входит в , то данный факт на диаграмме отмечается жирным кружком, выделяющим вершину .На рис.1 примера 1 показана диаграмма автомата
, работающего над словами алфавита . Автомат имеет два состояния: и , причем «хорошим» является только состояние . Начав работу в состоянии , автомат под воздействием букв
из этого состояния не выходит; под воздействием буквы
реализуется переход в состояние ; любая далее поступающая буква оставляет автомат в том же состоянии. Таким образом, автомат распознает язык , состоящий из слов, имеющих в своем составе букву .П
ример 1.Рисунок 1.
Класс регулярных языков замкнут относительно основных теоретико-множественных операций – объединения, пересечения, разности.
Пусть
и - регулярные языки, распознаваемые конечными автоматами и соответственно. Считаем, что и . Автомат , распознающий язык строим следующим образом. Полагаем ; каждое состояние конструируемого автомата содержит две компоненты, левую и правую. Начальным состоянием нового автомата считаем , а функцию переходов g определяем следующим образом: .Очевидно, по первой компоненте автомат
моделирует действия автомата