Дехтярь М.И. Конечные автоматы (Лекции по дискретной математике)
Подождите немного. Документ загружается.
w = w
1
w
2
. . . w
k
(w
i
∈ Σ, i = 1, . . . , k)
w
−1
= w
k
. . . w
2
w
1
L
L
−1
= {w
−1
| w ∈ L}
L Σ
(L) = {w | x ∈ Σ
∗
, wx ∈ L}
(L) = {w | x ∈ Σ
∗
, xw ∈ L}
(L) = {w | x, y ∈ Σ
∗
, xwy ∈ L}
L Σ = {a
1
, . . . , a
m
} L
1
, . . . , L
m
∆
(L) L a
i
L
i
(L) = {w | u = a
i
1
a
i
2
. . . a
i
n
∈ L w
1
, w
2
, . . . , w
n
∈
∆
∗
, w = w
1
w
2
. . . w
n
w
j
∈ L
i
j
j = 1, 2, . . . n}
L Σ k
φ Σ
k
Σ
L
1
= {φ(a
1
a
2
. . . a
k
) . . . φ(a
(n−1)k+1
a
(n−1)k+2
. . . a
nk
) | a
1
a
2
. . . a
nk
∈ L}
L
n w ∈ L |w| > n x, y z
w = xyz
|xy| ≤ n
|y| > 0
m ≥ 0 w
m
= xy
m
z L
y
0
= ε, y
1
= y, y
i+1
= y
i
y
L A =< Σ, Q, q
0
, F, Φ >
L |Q| = n w = w
1
w
2
. . . w
k
∈ L k > n
p = (q
0
= q
i
0
, q
i
1
, . . . , q
i
k
) A w.
(n + 1)
q ∈ Q
l < j ≤ n q
i
l
= q
i
j
= q x = w
1
w
2
. . . w
l
w
q
0
q
i
l
= q y = w
i+1
. . . w
j
w q
i
l
= q
q
i
j
= q z = w
j+1
. . . w
k
w q
i
j
= q q
i
k
∈ F x
z |y| = j − l ≥ 1. |xy| = j ≤ n
p q
i
l
= q, . . . , q
i
j
, p
0
q
0
q
i
k
∈ F
xz m p
0
q
0
q
i
k
∈ F
xy
m
z. m ≥ 0 w
m
= xy
m
z ∈ L. 2
L
L n
n w L > n
w = xyz
k ≥ 0 w
k
= xy
k
z L
L
w k ≥ 0 w
k
/∈ L,
k = 0 k = 2.
L
1
= {w = 0
i
1
i
| i ≥ 1}
n
w = 0
n
1
n
w ∈ L
1
w = xyz
|xy| ≤ n y = 0
i
i > 0 w
0
= xz = 0
n−i
1
n
/∈ L
1
L
1
{(, )}
w =
(
n
)
n
w = xyz
|xy| ≤ n y = (
i
i > 0
w
0
= xz = (
n−i
)
n
/∈
L
2
= {w = 0
i
1
j
| i ≤ 2j + 1}
L
2
n
w = 0
2n+1
1
n
∈ L
2
w = xyz
|xy| ≤ n y = 0
i
i > 0 w
2
= xy
2
z =
0
2n+1+i
1
n
2n + 1 + i ≥ 2n + 2 6≤ 2n + 1 w
2
/∈ L
2
L
2
{|}
L
3
= {|
i
2
| i ≥ 0}
L
3
n
w = |
n
2
w = xyz
|xy| ≤ n y = |
i
0 < i ≤ n w
0
= xz = |
n
2
−i
n
2
− i ≥ n
2
− n > n
2
− 2n + 1 = (n − 1)
2
n
2
− i
w
0
/∈ L
3
L
3
{|}
L
pr
= {|
p
| p − }
L
pr
n p > n w = |
p
w = xyz w |xy| ≤ n
0 < i ≤ n y = |
i
xz = |
p−i
k = p − i w
k
= xy
k
z
p
0
|x| + k|y| + |z| = (p − i)(i + 1) 1 ≤ i < n + 1 ≤ p p
0
w
k
/∈ L
pr
L
pr
k n
L
L L
0
= op(L, L
1
, . . . , L
k
) L
L
1
, . . . , L
k
op
L
0
L
L
4
= {0
i
1
j
| i 6= j}
L
5
= {0
i
1
j
| i ≥ 1, j ≥ 1} L
5
L
4
L
1
L
1
= L
5
∩ L
4
L
1
L
4
L
6
= {c
r
a
i
b
i
| r ≥ 1, i ≥ 0} L
7
= {a
i
b
j
| i ≥ 0, j ≥ 0}
L
8
= L
6
∪ L
7
n w L
8
L
6
L
7
w = c
r
a
i
b
i
∈ L
6
xyz
x = ε, y = c, z = c
r−1
a
i
b
i
(r ≥ 1, i ≥ 0) w
0
= z = c
r−1
a
i
b
i
(r ≥ 1, i ≥ 1)
r = 1 w
0
= a
i
b
i
∈ L
7
r > 1 w
0
∈ L
6
k ≥ 1
w
k
= c
r+k−1
a
i
b
i
∈ L
6
w = a
i
b
j
∈ L
7
i ≥ 1
xyz x = ε, y = a, z = a
i−1
b
j
(i ≥ 1, j ≥ 0) k ≥ 0
w
k
= a
k
a
i−1
b
j
∈ L
7
i = 0, w = b
j
(j ≥ 1)
x = ε, y = b, z = b
j−1
(j ≥ 1) k ≥ 0 w
k
= b
k
b
j−1
∈ L
7
w
k
∈ L
8
L
8
φ : {a, b, c}
∗
→ {0, 1}
∗
φ(a) = 0, φ(b) = 1, φ(c) = ε φ(L
8
\ L
7
) = φ(L
6
) = L
1
L
7
L
1
L
8
|xy| ≤ n 1
0
) |yz| ≤ n
y w ≤ n
Σ = {a, b, c}
a b
L = {a
n
cb
m
| m > 3n}.
L = {wcw
−1
| w = a
2
b
n
a n > 0}.
L = {w | |w| = 2
n
n}.
L = {wc
|w|
| w ∈ {a, b}
∗
, |w| − w}.
λ x λ
λ λ
λ λxx, λx(xx), λxλx(λx(xx)λx(xx))
λ (xx), λx(λx) λx((xx)
λ {x, λ, (, )}
U = {(x
1
(1), x
2
(1), y(1))(x
1
(2), x
2
(2), y(2)) . . . (x
1
(n), x
2
(n), y(n)) | y = y(n) . . . y(2)y(1)
n x
1
= x
1
(n) . . . x
1
(2)x
1
(1)
x
2
= x
2
(n) . . . x
2
(2)x
2
(1)}
L = {w | w 6= w}
Σ = {a, b}