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

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

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

Рубрика: 

В результате имеем: A = A
1
.
Теорема. Множество регулярных языков замкнуто относительно операций итерации,
усеченной итерации, объединения, произведения, пересечения, дополнения и разности.
Доказательство. Для доказательства необходимо выполнить операции над
соответствующими конечными автоматами и показать, что в результате таких
преобразований построенный автомат допускает требуемый язык. Предполагается, что в
автомате удалены циклы из начальных и заключительных состояний. Для выполнения
перечисленных в теореме операций необходимо выполнить соответствующие
преобразования над заданными автоматами.
1. Операция итерации реализуется удалением циклов из начальных и заключительных
состояний и объединения полученных состояний. Объединение начального и
заключительного состояний означает, что построенный автомат допускает пустую цепочку.
Однократный переход из начального в заключительное состояние исходного автомата
соответствует допуску цепочек языка L. Поскольку эти состояния объединены, автомат
допускает цепочки языков LL, LLL и т.д., т.е. он распознает язык {ε}∪L∪L
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
совпадает с
началом цепочки x∈L(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
) . 
    В результате имеем: A = A1.
    Теорема. Множество регулярных языков замкнуто относительно операций итерации,
усеченной итерации, объединения, произведения, пересечения, дополнения и разности.
    Доказательство. Для доказательства необходимо выполнить операции                  над
соответствующими конечными автоматами и показать, что в результате таких
преобразований построенный автомат допускает требуемый язык. Предполагается, что в
автомате удалены циклы из начальных и заключительных состояний. Для выполнения
перечисленных в теореме операций               необходимо выполнить соответствующие
преобразования над заданными автоматами.
    1. Операция итерации реализуется удалением циклов из начальных и заключительных
состояний и объединения полученных состояний. Объединение начального и
заключительного состояний означает, что построенный автомат допускает пустую цепочку.
Однократный переход из начального в заключительное состояние исходного автомата
соответствует допуску цепочек языка L. Поскольку эти состояния объединены, автомат
допускает цепочки языков LL, LLL и т.д., т.е. он распознает язык {ε}∪L∪L2∪ . . . =L*.
    2. Операция произведения над L(A1) и L(A2) выполняется с помощью двух
преобразований: а) удаляются циклы из начального состояния A2 и заключительного
состояния A1; б) каждому заключительному состоянию A1          ставим в соответствие свой
экземпляр A2 и объединяем заключительные состояния A1 с начальным состоянием
соответствующего экземпляра A2.
    3. Объединение L(A1) и L(A2) строится с помощью удаления циклов в начальных
состояниях A1 и A2 и объединения полученных начальных состояний.
    4. Усеченная итерация может быть построена двумя способами:

       а) L(A1)+ = L(A1)* L(A1),
       б) L(A1)+ = L(A1) L(A1)*.

   5. Рассмотрим дополнение L(A1) до Σ*. Пусть автомат A1 детерминированный, тогда
любая цепочка x=a1a2 . . an распознается по единственному маршруту:
        p0a1 → p1
        p1a2 → p2
          . . .
         pn-1an → pn, pn∈ F.
    Автомат не распознает только те цепочки, которые:
    1) либо представляют собой начальную часть цепочки a1a2 . . aj, при чтении которой
автомат переходит в состояние, не являющееся заключительным;
    2) либо имеют вид y = a1a2 . . akbc1c2 . . cm (k < n), где начало цепочки a1a2 . . ak совпадает с
началом цепочки x∈L(A1), но за символом ak стоит такой символ b, что автомат A1 его
прочитать не может.
    Поэтому для того чтобы построить автомат, распознающий дополнение языка,
необходимо:
    а) все заключительные состояния сделать незаключительными, а незаключительные
состояния - заключительными;
    б) ввести дополнительное состояние, сделать его заключительным и из каждого
состояния провести в это состояние такие дуги, каждая из которых соответствует символам
алфавита, не читаемым в этом состоянии;
    в) в построенном дополнительном состоянии построить петли для всех символов
алфавита, чтобы обеспечить чтение произвольного окончания цепочки c1c2 . . cm.
    6. Разность L(A1) и L(A2) строится в соответствии со следующим преобразованием:

                                     L(A1) \ L(A2) = L(A1) ∩ L(A2) .

Страницы