Големина на текста:
2.3. ДИАГРАМА НА ПРЕХОДИТЕ
1. Определение за краен автомат като идентификатор на низове
Краен автомат А над
{}
,,...,,
21n
aaa=? е краен ориентиран граф, от всеки
връх на който излизат n насочени дъги, всяка обозначена с етикет . Всяка
дума се дефинира с - път от връх i до връх j в А и представлява
конкатенацията на етикетите на насочените рамена, през които преминава.
Думата се разпознава от крайния автомат А, ако w пътят от началния
връх води до крайния връх. Празната дума
?
се разпознава от A точно тогава,
когато началният връх е и краен връх. Множеството от думи, разпознавани от
крайния автомат А е крайно и се бележи с
i
a
*??w
w
*??w
A
~
. Едно множество е регулярно над
?
точно тогава, когато се разпознава от краен автомат над
?
.
Пример:
За краен автомат над
{}
ba,=?
са в сила следните означения.
Дъга от вида
се означава с
No
A
- автомат
A
~
- множество от думи
1
?
2
?
*
3
Всички думи над
?
, съдържащи две последователни
а или две последователни b.
4
Всички думи над
?
, съдържащи четен брой а и
четен брой b.
1
С всеки връх i се свързва множеството от всички думи w, за които w-
пътят от началния връх води до i. На множество се съпоставя множество
на онези върхове
i
S
i
S
j
S
j
, от които се стига до i по една единствена дъга.
Обединението на всички множества за крайните върхове е
i
S
A
~
За автомата (4) се получава:
1
S
: Всички думи с четен брой а и четен брой b;
2
S : Всички думи с четен брой а и нечетен брой b;
3
S
: Всички думи с нечетен брой а и четен брой b;
4
S : Всички думи с нечетен брой а и четен брой b.
Диаграма на преходите T над
?
е краен ориентиран граф, всяка насочена
дъга на който е белязана с дума
*??w
(евентуално празната дума
?
), наричана
етикет. Има поне един връх (начален), белязан с “-” и множество (евентуално
празно) от върхове, белязани с “+” (крайни върхове). Даден връх може да бъде
едновременно начален и краен.
Ако думата , - път от връх i до връх j е краен път от i до j,
конкатенацията на етикетите на насочените дъги на който представлява думата
(празните думи
?
се пренебрегват). Думата
*??w
w
w
*??w
се разпознава от Т, ако
съществува път от начален до краен връх. Празната дума се разпознава от T,
ако съществува връх в Т, който е едновременно начален и краен или има
?
-
път, който води от начален до краен връх. Множеството от думи, разпознавани
от Т, се означават с
w
T
~
.
Диаграмата на преходите е обобщено понятие на краен автомат. Макар
класът на крайните автомати е същински подклас на диаграмите на преходите,
всяко регулярно множество, което е разпознава от диаграмите на преходите, се
разпознава и от някакъв краен автомат. Всеки краен автомат е диаграма на
преходите. Обратното не винаги е вярно. Крайният автомат е детерминиран, т.е.
?
и връх i
?
единствен път с начало i. Диаграмата на преходите е
недетерминирана. Тя съдържа повече от един (или нито един) -път с начало i.
*??w
w
Теорема на Клини
: 1) За всяка диаграма на преходите Т над
?
съществува
регулярен израз R над
?
, за който
TR
~~
=
;2) За всеки регулярен израз
R над ?
съществува краен автомат А над ?, за който
RA
~
~
=
. Следствие: 1) едно
множество е регулярно над ? точно тогава, когато се разпознава от някакъв
краен автомат над ?; 2) едно множество е регулярно над ? точно тогава, когато
се разпознава от някаква диаграма на преходите над ?.
Диаграмата на преходите Т и множеството от думи
T
~
над
{}
ba,=?
,
разпознавани от нея са представени в таблица -1.
2
Таблица- 1
No
T
-диаграма на
преходите
T
~
- множество от думи
1
?
2
{?}
3
?
4
{?, a, b}
5
Всички думи над ?, започващи с b, последвано
само от ата.
6
Всички думи над ?, съдържащи две
последователни а - та и две последователни b
та.
7
Всички думи над ?, съдържащи четен брой ата
и четен брой bта.
8
Всички думи над ?, които започват с а или
съдържат аа.
Обобщената диаграма на преходите
представлява диаграма на преходите,
чиито насочени дъги са белязани с регулярни изрази
2. Метод на подмножествата за конструиране на краен автомат
Да се конструира краен автомат А по зададен регулярен израз R над ?,
така, че
RA
~
~
=
.
Алгоритъм:
1.
Конструира се Т, за която RT
~~
= . Започва се от обобщената диаграма на
преходите, съставена от начален връх x и краен връх y, с дъга между тях
обозначена с регулярен израз R.
2.
Последователно се разклонява R, като се прибавя нови върхове и дъги,
докато всяка дъга се бележи само с буква от ? или ?, като се прилагат
следните правила:
3

Това е само предварителен преглед

За да разгледате всички страници от този документ натиснете тук.

Диаграма на преходите

Диаграмата на преходите е обобщено понятие на краен автомат. Макар класът на крайните автомати е същински подклас на диаграмите на преходите, всяко регулярно множество...
Изпратен от:
pioneer14
на 2011-12-09
Добавен в:
Лекции
по Математически анализ
Статистика:
14 сваляния
виж още
 
Домашни по темата на материала
намерете асимптотите на функцията
добавена от steisi_345 11.11.2013
2
5
 

Диаграма на преходите

Материал № 770857, от 09 дек 2011
Свален: 14 пъти
Прегледан: 60 пъти
Предмет: Математически анализ, Математика
Тип: Лекция
Брой страници: 5
Брой думи: 940
Брой символи: 5,411

Потърси помощ за своята домашна:

Имаш домашна за "Диаграма на преходите"?
Намери бързо решение, с помощтта на потребители на Pomagalo.com:

Намери частен учител

Павлина Йорданова
преподава по Математически анализ
в град Варна
с опит от  5 години
278 33

Любомир Янакиев
преподава по Математически анализ
в град София
с опит от  40 години
2 204 10

виж още преподаватели...
Последно видяха материала