Языки и трансляции. Мартыненко Б.К. - 39 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

38
Теперь мы используем построения теоремы 3.4, чтобы найти dfa
M
1
,
эквивалентный автомату
M.
Положим
M
’
= (Q
’
, {0, 1}, δ
’
, [S], F
’
), где Q
’
= {ϕ, [S], [B], [A], [S, B], [S, A],
[
B, A], [S, B, A]}, F
’
= {[A], [S, A], [B, A], [S, B, A]}; δ
’
определяется следующим
образом:
1) δ
’
([S], 0) = [B],
2) δ
’
([S], 1) = ϕ,
3) δ
’
([B], 0) = [B, A], 4) δ
’
([B],1) = [S],
5) δ
’
([B, A], 0) =[B, A], 6) δ
’
([B, A], 1) = [S],
7) δ
’
(ϕ, 0) = ϕ, 8) δ
’
(ϕ, 1) = ϕ.
Здесь указаны только те значения δ
’
, которые относятся к достижимым
состояниям
ϕ, [S], [B], [B, A]. Во все другие состояния, представленные в мно-
жествах
Q
’
и F
’
, в которые автомат M
’
никогда не входит, могут быть удалены
из них как бесполезные.
Теперь согласно построениям теоремы 3.6 по автомату
M
’
построим
грамматику типа 3:
G
1
= (V
N
, V
T
, P, S), где V
N
= {ϕ, [S], [B], [B, A]}, V
T
= {0, 1}, S = [S],
P = { (1) [S] → 0[B], (2) [S] → 1ϕ, (3) [B] → 0[B, A], (4) [B] → 1[S], (5) [B] → 0,
(6) [
B, A] → 0[B, A], (7) [B, A] → 1[S], (8) [B, A] → 0, (9) ϕ → 0ϕ, (10) ϕ →1ϕ}.
Грамматика
G
1
значительно сложнее грамматики G, но L(G
1
) = L(G).
Действительно, грамматику
G
1
можно упростить, если заметить, что правила
для [
B, A] порождают в точности те же цепочки, что и правила для [B].
Поэтому нетерминал [
B, A] можно заменить всюду на [B] и исключить появив-
шиеся дубликаты правил для [
B]. Кроме того, отметим, что нетерминал ϕ не
порождает ни одной терминальной цепочки. Поэтому он может быть исключен
вместе с правилами, в которые он входит. В результате получим грамматику
G
2
= ({[S], [B]}, {0, 1}, P
2
, [S]), где P
2
= {(1) [S] → 0[B], (2) [B] → 0[B],
(3) [
B] → 1[S], (4) [B] → 0}.
Очевидно, что полученная грамматика
G
2
отличается от исходной грам-
матики
G лишь обозначениями нетерминалов. Другими словами, L(G
2
) = L(G).
§ 3.5. Свойства языков типа 3
Поскольку класс языков, порождаемых грамматиками типа 3, равен классу
множеств, принимаемых конечными автоматами, мы будем использовать обе
формулировки при описании свойств класса языков типа 3. Прежде всего
покажем, что языки типа 3 образуют
булеву алгебру.
Определение 3.9. Булева алгебра множеств есть совокупность множеств,
замкнутая относительно объединения, дополнения и пересечения.
Определение 3.10. Пусть L ⊆ Σ
1
*
— некоторый язык и Σ
1
⊆ Σ
2
. Под допол-
нением L языка L подразумевается множество Σ
2
*
\ L.
Лемма 3.1. Класс языков типа 3 замкнут относительно объединения.
Доказательство.
Возможны два подхода: один использует недетерми-
нированные конечные автоматы, другой основывается на грамматиках. Мы
будем пользоваться вторым подходом.

Страницы