Теория алгоритмов и формальных языков. Мелихов А.Н - 70 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

PPvP =
{}
{}
{}
*
*
*
PP =
идемпотентность v и
{
}
*
{} {}
**
PvPP = - дизъюнктивное поглощение
{
}
*
{} {} {}
***
PPP =⋅ - мультипликативное поглощение
{
}
*
.
При отсутствии обычных скобок в регулярных выражениях первыми выполняются
итерации, затем умножения и потом дизъюнкции.
Рассмотрим некоторые примеры регулярных событий в алфавите
{}
.,,
321
xxxV
x
=
1)
Событие называемое универсальным, которое состоит из всех слов алфавита
x
V ,
записывается в виде
{}
*
321
,, xxxP = .
2)
Событие, которое содержит только трех буквенные слова в
x
V :
)()()(
321321321
vxvxxvxvxxvxvxxR
⋅
⋅= .
3) Событие, состоящие из всех слов, в которых хотя бы один раз встречается отрезок
321
xxx :
{}
{
}
*
321321
*
321
vxvxxxxxvxvxxT ⋅⋅= .
4) Событие, состоящие из всех слов, которые начинаются буквой
3
x или
1
x , а
оканчиваются отрезком
21
xx :
{}
21
*
32131
)( xxvxvxxvxxQ ⋅⋅= .
5)
Событие, состоящие из слов, начало которых есть любая цепочка из букв
1
x или
2
x
, затем следует двухбуквенная цепочка из
2
x
или
3
x и, наконец, окончание
содержит, по крайней мере, одну букву
1
x
:
{}
{
}
.)()(
*
113232
*
21
xxvxxvxxvxxW ⋅⋅⋅⋅=
Из рассмотрения операций
{
}
*
,,⋅v алгебры событий вытекает, что все конечные
события регулярны. Это следует из того, что любая цепочка выражается произведением
букв, а любое конечное событие – дизъюнкцией образующих его цепочек.
Применение итерации приводит к появлению бесконечных, регулярных событий.
Это бесконечные, в конечном счете, повторяющиеся цепочки. Однако, как легко заметить,
большинство бесконечных событий являются нерегулярными
событиями. Примерами
таких событий являются цепочки, в которых длина слов
KK ,,,,
21 i
nnn такова, что
разности ),2,1(
1
K==
+
inn
ii
не ограничены в совокупности. (Допустим, увеличивается в
два раза, в квадрат, в куб и т.д.).
Фундаментальную роль в анализе и синтезе конечных автоматов сыграла теорема
Клини.
Класс событий, представленных в конечных автоматах, совпадает с классом
регулярных событий.
Конструктивное доказательство этой теоремы приводит к построению алгоритмов
анализа и синтеза
произвольных конечных автоматов.
3.7 Взаимосвязь автоматов и языков
В предыдущих разделах мы рассмотрели три класса автоматов: машина Тьюринга,
автоматы с магазинной памятью и конечные автоматы. Какова взаимосвязь между этими
автоматами и классами языков, которые они определяют? Вообще говоря, следуя *******
Хомского, формальные языки можно охарактеризовать следующим образом:

Страницы