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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§3
w Σ
q
0
a
0
wa
0
,
T p(|w|)
p(|w|)
u
1
q
0
a
j
1
v
1
w ∈ L q
0
a
0
wa
0
T p(|w|)
q
0
a
0
a
1
a
0
...a
0
w/∈ L q
0
a
0
wa
0
T
q
0
a
0
a
1
a
0
...a
0
∗ A
T
A
T
∪{∗}
T (x, y)
w v A
T
∪ {∗} T (w,v)
w Σ
v v
0
∗v
1
∗...∗v
s
v
t
0 ≤ t ≤ s
T v
0
q
1
a
0
wa
0
v
s
q
0
a
0
a
1
a
0
...a
0
t 0 ≤ t ≤ s − 1 v
t
T
v
t+1
w
T
v
s ≤ p(|w|) t 0 ≤ t ≤ s |v
t
|≤|w|+1+s ≤|w|+1+p(|w|)
|v|≤s +(s +1)(|w|+1+s) ≤ p(|w|)+(p(|w|)+1)(|w| +1+p(|w|)) ≤ q(|w|),
q(n)
v

Страницы