Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32



страница8/22
Дата07.11.2012
Размер1.2 Mb.
ТипКонспект
1   ...   4   5   6   7   8   9   10   11   ...   22

6.4. Автоматы с -переходами


Автоматы с -переходами естественно возникают в различных приложениях и позволяют представить любой автомат в виде двухполюсников с одним входом и одним выходом, а так же строить сети из таких автоматов, сохраняя в них единственный вход и единственный выход. От рассмотренных ранее автоматов они отличаются тем, что в них присутствуют переходы, осуществляемые без чтения входной цепочки (на диаграмме такие переходы обозначаются стрелками, помеченными символом , рис.6).



Рис. 6

Например, рассмотрим автомат с двумя выходами, представленный на рис. 7. Если просто объединить две выходные вершины автомата, то получившийся автомат не будет эквивалентен исходному, т.к. после построения символа b в результирующем автомате возможно будет построить символы а, что было невозможно в исходном автомате. Автомат, эквивалентный исходному, и являющийся двухполюсником, представлен на рис. 8.





Рис.7

Рис.8


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

Детерминизация автоматов с -переходами


Процедура детерминизации автоматов с -переходами задаётся следующей теоремой.

Теорема 4. Классы языков, допускаемых детерминированными автоматами и автоматами с -переходами, совпадают.

Доказательство.

Пусть автомат А = <Q, VT, q0, F, K> – автомат с -переходами. Построим соответствующий детерминированный автомат А’= <Q’, VT, q0’, F’, K’>, такой, что L(A)=L(A’).
Определим F’(q,a) и K следующим образом:

F’(q,a)={p / (q,ax) ├+ (p,x)}

K’ = K {q / (q, ) ├* ( p, )& pK}

Несложно показать, с использованием математической индукции по числу символов в распознаваемой цепочке, что получаемый таким образом автомат А’ переходит при распознавании цепочки x в конечное состояние тогда и только тогда, когда существует последовательность переходов в конечное состояние автомата А при распознавании этой же цепочки символов.

Очевидно, что если L – А-язык, то ему можно сопоставить некоторый двухполюсник.

Пусть языкам L1 и L2 сопоставлены соответствующие двухполюсники (рис.9,а). Тогда их объединению, конкатенации и итерации языка L1 будут, соответственно, сопоставлены двухполюсники на рис. 9,б, 9,в и 9,г.



Рис.9
Сопоставляя доказанные ранее утверждения, получаем следующую теорему.

Теорема 5. Класс А-языков замкнут относительно операций объединения, конкатенации и итерации.

Оптимизация автоматов с -переходами


  1. Если из состояния А исходит единственная дуга и это -дуга в состояние В, то вершины А и В можно слить.

  2. Если из вершины А выходит -дуга в вершину В, являющуюся начальной вершиной некоторой дуги( не петли) или последовательности дуг, а С – конечная вершина этой дуги (последовательности дуг), и единственная дуга из С-дуга в вершину А, то вершины А, В и С можно слить (примеры такого слияния приводятся на рис. 10 ( для одной дуги – а, б; для последовательности – в, г).



Рис.10

Пример. Пусть автомат SB представлен диаграммой на рис. 11,а. Объединим по правилу 1 упрощения автоматов с -переходами состояния 4 и 5 и переобозначим состояния, как показано на рис. 11,б.



Рис.11

Построим функцию переходов детерминированного автомата SB.

F(A, a) = [B,C, D, F],

F(A, b) = [E],

F(A,c) = ,

F([B, C, D, F], a) = [C,D, F],

F([B, C, D, F], b) = [D, E],

F([B, C, D, F], c) = ,

F([E], a) = ,

F([E], b) = ,

F([E], c) = [D],


F([D, E], a) = [D, F],

F([D, E], b) = [E],

F([D, E],c) = [D],


F([D, F], a) = [D, F],

F([D, F], b) = [E],

F([D, F], c) = ,


F([D], a) = [D, F],

F([D], b) = [E],

F([D], c) = ,


F([C, D, F], a) = [C, D, F],

F([C, D, F], b) = [E],

F([C, D, F],c) =  .



Диаграмма детерминированного автомата SB представлена на рис. 12. Для него K’ = { [B, C, D, F] , [ D, F], [C, D, F]}.



Рис.12

Тот же автомат после переобозначения состояний представлен на рис. 13.



Рис.13
1   ...   4   5   6   7   8   9   10   11   ...   22

Похожие:

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconМетодические указания к практическим занятиям Рязань 2004 удк 519. 713 (075)
Теория автоматов в задачах. Ч1: Методические указания к практическим занятиям/ Рязан гос радиотехн акад. Сост.: Н. И. Иопа. Рязань,...
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60
Калинина В. Н., Соловьев В. И. Введение в многомерный статистический анализ: Учебное пособие / гуу. – М., 2003. – 92 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций москва 2003 ббк вкб / 075 : 378 я 14
История экономики России XX века (1900 – 1917 гг.) : Конспект лекций. – М.: Мгту "Станкин", 2003. – 45 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций санкт-петербург 2009 удк 532. 6(075. 8) Ббк в334я73 а 65 Рецензент И. П. Арешев
Охватывает ток (рис. 16), то
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций м осква 2000 ббк ВКП / 075 : 378 я 14
История экономики России XIX века: Конспект лекций. М.: Мгту "Станкин", 2000. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций по философии Часть 1 Античная философия Новосибирск 2007 удк 101. 8 (075) ббк ю3я73-1
Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты
С32 Ведение в теорию графов: учеб пособие. Саратов: Сарат гос техн ун-т, 2009. 36с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций Таганрог 2001 удк 621. 382. 019. 3 (075. 8) Механцев Е. Б
Обеспечение надежности электронных средств: конспект лекций. Таганрог: Изд-во трту, 2001
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКурс лекций Для студентов вузов Кемерово 2006 удк 113/119(075) ббк 87я7 М42 Рецензенты

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие Москва 2006 удк 341. 645: 347. 922(075) ббк 67. 412. 2 О 23

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org