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

UptoLike

ВУЗ: 

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

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

Рубрика: 

e
π
L n w L |w|≥n
w = xyz y = ε |xy|≤n
k ≥ 0 xy
k
z ∈ L
L
M n
M q
0
w |w| = m ≥ n L
M w
q
0
w
1
w
2
...w
m
M
q
1
w
2
...w
m
M
...
M
q
m
ε,
w
1
w
m
w q
m
∈ F
M
M n
m +1 q
i
w
i+1
...w
m
m +1>n
i j 0 ≤ i<j≤ n q
i
= q
j
y = w
i+1
...w
j
M q
i
q
i
i<j
x = w
1
...w
i
z = w
j+1
...w
m
xz = w
1
...w
i
w
j+1
...w
m
M q
0
q
m
w = xyz xz ∈ L
k ≥ 1
xy
k
z = w
1
...w
i
· w
i+1
...w
j
· w
i+1
...w
j
...· w
i+1
...w
j
· w
j+1
...w
m
M q
0
q
m
w = xyz xy
k
z ∈ L
L
1
= {a
k
b
k
|k ≥ 0}
n
w = a
n
b
n
w = xyz
y = ε k ≥ 0 xy
k
z ∈ L
y = a
i
i>0 xz = a
n−i
b
n
∈ L

Страницы