Элементы теории алгоритмов - 47 стр.

UptoLike

ВУЗ: 

ЯрГУ | Ярославль

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

Рубрика: 

§6
Q
M
= {[w] |w ∈ Σ
∗
}
≡
L
;
s
M
=[ε] ;
F
M
= {[u] |u ∈ L }.
[w] ∈ Q
M
a ∈ Σ δ
M
([w],a)=[wa]
L
M
≡
L(M
)
≈
M
≈
M
s
M
M
M
δ
M
δ
M
([w],a)=[wa] w ≡ u wa ≡ ua
L = L(M)
|u| u w u Σ
∗
[w]u
∗
M
[wu]ε u
[w]au
M
[wa]u
∗
M
[(wa)u]ε =[w(au)]ε.
δ
∗
M
([w],u)=[wu]
δ
∗
M
([ε],u)=[εu]=[u]
u ∈ L(M) ⇐⇒ δ
∗
M
([ε],u) ∈ F
M
⇐⇒ [u] ∈ F
M
⇐⇒ u ∈ L.
L(M)=L
L
M L
M
L
L
≡
L
L
M
≡
L
≡
L
≡
L
M
L
L

Страницы