Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 38 стр.

UptoLike

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

В результате имеем: A = A
1
.
Теорема. Множество регулярных языков замкнуто относительно операций итерации,
усеченной итерации, объединения, произведения, пересечения, дополнения и разности.
Доказательство. Для доказательства необходимо выполнить операции над
соответствующими конечными автоматами и показать, что в результате таких
преобразований построенный автомат допускает требуемый язык. Предполагается, что в
автомате удалены циклы из начальных и заключительных состояний. Для выполнения
перечисленных в теореме операций необходимо выполнить соответствующие
преобразования над заданными автоматами.
1. Операция итерации реализуется удалением циклов из начальных и заключительных
состояний и объединения полученных состояний. Объединение начального и
заключительного состояний означает, что построенный автомат допускает пустую цепочку.
Однократный переход из начального в заключительное состояние исходного автомата
соответствует допуску цепочек языка L. Поскольку эти состояния объединены, автомат
допускает цепочки языков LL, LLL и т.д., т.е. он распознает язык {ε}LL
2
. . . =L
*
.
2. Операция произведения над L(A
1
) и L(A
2
) выполняется с помощью двух
преобразований: а) удаляются циклы из начального состояния A
2
и заключительного
состояния A
1
; б) каждому заключительному состоянию
A
1
ставим в соответствие свой
экземпляр A
2
и объединяем заключительные состояния A
1
с начальным состоянием
соответствующего экземпляра A
2
.
3. Объединение L(A
1
) и L(A
2
) строится с помощью удаления циклов в начальных
состояниях A
1
и A
2
и объединения полученных начальных состояний.
4. Усеченная итерация может быть построена двумя способами:
а) L(A
1
)
+
= L(A
1
)
*
L(A
1
),
б) L(A
1
)
+
= L(A
1
) L(A
1
)
*
.
5. Рассмотрим дополнение L(A
1
) до Σ
*
. Пусть автомат A
1
детерминированный, тогда
любая цепочка x=a
1
a
2
. . a
n
распознается по единственному маршруту:
p
0
a
1
p
1
p
1
a
2
p
2
. . .
p
n-1
a
n
p
n
, p
n
F.
Автомат не распознает только те цепочки, которые:
1) либо представляют собой начальную часть цепочки a
1
a
2
. . a
j
, при чтении которой
автомат переходит в состояние, не являющееся заключительным;
2) либо имеют вид y = a
1
a
2
. . a
k
bc
1
c
2
. . c
m
(k < n), где начало цепочки a
1
a
2
. . a
k
совпадает с
началом цепочки xL(A
1
), но за символом a
k
стоит такой символ b, что автомат A
1
его
прочитать не может.
Поэтому для того чтобы построить автомат, распознающий дополнение языка,
необходимо:
а) все заключительные состояния сделать незаключительными, а незаключительные
состояния - заключительными;
б) ввести дополнительное состояние, сделать его заключительным и из каждого
состояния провести в это состояние такие дуги, каждая из которых соответствует символам
алфавита, не читаемым в этом состоянии;
в) в построенном дополнительном состоянии построить петли для всех символов
алфавита, чтобы обеспечить чтение произвольного окончания цепочки c
1
c
2
. . c
m
.
6. Разность L(A
1
) и L(A
2
) строится в соответствии со следующим преобразованием:
L(A
1
) \ L(A
2
) = L(A
1
) L(A
2
) .