Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
K Σ Σ
∗
K(u, K(v, w)) = u · (v · w) = uvw = (u · v) · w = K(K(u, v), w)
u, v, w ∈ Σ
∗
x ∈ Σ
∗
x · λ = λ · x = x.
(Σ
∗
, K, λ) λ
x, y ∈ Σ
∗
|xy| = |x · y| = |x| + |y|.
xy K(x, y) x ·y
Σ x ∈ Σ
∗
i i x
i
x
x
i
= xx
i−1
,
x
0
= λ
K(aabba, aaaaa) = aabbaaaaaa = a
2
b
2
a
6
= a
2
b
2
(aa)
3
x
ab . . . bb . . . c ac . . . b ab . . . b b . . . a a . . . b bb . . . ab
v, w ∈ Σ
∗
Σ
• v w ⇔ ∃x, y ∈ Σ
∗
: w = xvy.
• v
w ⇔ ∃x ∈ Σ
∗
: w = xv.
• v w ⇔ ∃y ∈ Σ
∗
: w = vy.
• v 6= λ [ ]
w v 6= w v [ ] w
( )
(abc)
3
= abca bcabc abc (abc)
3
bc (abc)
3
Σ x ∈ Σ
∗
|x| = n
n ∈ IN
x abbcbbab
x ∈ Σ
∗
a ∈ Σ Σ
|x|
a
a x
A |A| A P(A) =
{S | S ⊆ A} A
|(abbab)|
a
= 2 |(11bb0)|
0
= 1 x ∈ Σ
∗
|x| =
X
a∈Σ
|x|
a
.
Σ = {s
1
, s
2
, . . . , s
m
} m ≥ 1
s
1
< s
2
< ··· < s
m
Σ
Σ
∗
u, v ∈ Σ
∗
u < v ⇔ (|u| < |v|)
∨ (|u| = |v| ∧ u = x ·s
i
· u
0
∧ v = x · s
j
·v
0
x, u
0
, v
0
∈ Σ
∗
i < j).
Σ Σ
∗
L
C
L Σ Σ
∗
− L
L
∅
= ∅
L
λ
= {λ} λ
L
1
L
2
Σ
L
1
· L
2
= L
1
L
2
= {vw | v ∈ L
1
, w ∈ L
2
}
L
1
L
2
L Σ
L
0
:= L
λ
,
L
i+1
= L
i
·L i ∈ IN
0
,
L
∗
=
[
i∈IN
0
L
i
,
L
+
=
[
i∈IN
L
i
= L · L
∗
.
L
∗
L
9
A a ∈ A b ∈ A f(a) < f(b)
Σ = {a, b }
L
1
= ∅
L
2
= {λ}
L
3
= {λ, ab, abab}
L
4
= Σ
∗
= {λ, a, b, aa, . . .}
L
5
= Σ
+
= {a, b, aa, . . .}
L
6
= {a}
∗
= {λ, a, aa, aaa, . . .} = {a
i
| i ∈ IN
0
}
L
7
= {a
p
| p }
L
8
= {a
i
b
2·i
a
i
| i ∈ IN
0
}
L
9
= Σ
L
10
Σ
3
= {aaa, aab, aba abb baa b a b, bba, bbb}
Σ
keyboard
Σ
keyboard
Σ
i
= {x ∈ Σ
∗
| |x| = i},
L
∅
L = L
∅
= ∅
L
λ
·L = L.
L
1
= {λ, ab, b
3
a
4
} L
2
= {ab, b, ab
2
, b
4
}
L
1
L
2
∪
∩
A B
A ⊆ B B ⊆ A A = B
A ⊆ B x ∈ A x
B x ∈ B
L
1
, L
2
L
3
Σ
L
1
L
2
∪ L
1
L
3
= L
1
(L
2
∪ L
3
).
L
1
L
2
∪L
1
L
3
⊆ L
1
(L
2
∪L
3
)
L
1
L
2
⊆ L
1
(L
2
∪ L
3
)
L
1
L
2
= {xy | x ∈ L
1
∧ y ∈ L
2
} { }
⊆ {xy | x ∈ L
1
∧ y ∈ L
2
∪L
3
} {
L
2
⊆ L
2
∪ L
3
}
= L
1
·(L
2
∪ L
3
) { }.
L
1
L
3
⊆ L
1
(L
2
∪ L
3
) L
1
L
2
∪L
1
L
3
⊆
L
1
(L
2
∪ L
3
)
L
1
(L
2
∪ L
3
) ⊆ L
1
L
2
∪ L
1
L
3
x ∈ L
1
(L
2
∪ L
3
)
x ∈ {yz | y ∈ L
1
∧ z ∈ L
2
∪ L
3
}
{
}
⇒ ∃y ∈ L
1
∧ ∃z ∈ L
2
∪L
3
, x = yz
⇒ ∃y ∈ L
1
∧ (∃z ∈ L
2
∨ ∃z ∈ L
3
),
x = yz
{ ∪}
⇔ (∃y ∈ L
1
∧ ∃z ∈ L
2
: x = yz) ∨ (∃y ∈ L
1
∧ ∃z ∈ L
3
: x = yz)
{
∧, ∨}
⇔ (x ∈ {yz | y ∈ L
1
∧z ∈ L
2
}
| {z }
L
1
L
2
) ∨ (x ∈ {yz | y ∈ L
1
∧ z ∈ L
3
}
|
{z }
L
1
L
3
)
{
}
⇔ x ∈ L
1
L
2
∪ L
1
L
3
{
∪}.
ut
L
1
, L
2
L
3
Σ
L
1
(L
2
∩ L
3
) ⊆ L
1
L
2
∩ L
1
L
3
.
x ∈ L
1
(L
2
∩ L
3
)
x ∈ {yz | y ∈ L
1
∧z ∈ L
2
∩ L
3
}
{ }
⇔ ∃y, z ∈ Σ
∗
, y ∈ L
1
∧ (z ∈ L
2
∧ z ∈ L
3
)
x = yz
{ ∩}
⇔ ∃y, z ∈ Σ
∗
, (y ∈ L
1
∧ z ∈ L
2
) ∧ (y ∈ L
1
∧ z ∈ L
3
) : x = yz
⇒ ∃y, z ∈ Σ
∗
, (yz ∈ L
1
L
2
) ∧ (yz ∈ L
1
L
3
) : x = yz
{
}
⇔ x ∈ L
1
L
2
∩L
1
L
3
{
∩}.
ut
L
1
(L
2
∩ L
3
) ⊇ L
1
L
2
∩ L
1
L
3
U
1
U
2
U
3
U
1
(U
2
∩ U
3
) ⊂ U
1
U
2
∩ U
1
U
3
.
U
1
U
2
U
3
x
L
1
L
2
L
1
L
3
x = yz x ∈ L
1
z ∈ L
2
∩ L
3
x
x = y
1
z
1
= y
2
z
2
y
1
6= y
2
( z
1
6= z
2
),
y
1
, y
2
∈ L
1
z
1
∈ L
2
z
2
∈ L
3
x ∈ L
1
L
2
∩L
1
L
3
x L
1
(L
2
∩ L
3
)
U
1
U
2
U
3
∈ (Σ
bool
)
∗
U
1
(U
2
∩ U
3
) ( U
1
U
2
∩ U
1
U
3
.
U
2
= {0} U
3
= {10} U
2
∩U
3
= ∅
U
1
(U
2
∩ U
3
) = ∅
U
1
U
1
U
1
U
2
∩ U
1
U
3
U
1
= {λ, 1}
U
1
U
2
= {0, 10}, U
1
U
3
= {10, 110},
U
1
U
2
∩ U
1
U
3
= {10} 6= ∅.
ut
L
1
L
2
L
3
{0}
L
1
(L
2
∩L
3
) = L
1
L
2
∩ L
1
L
3
?
L
1
⊆ Σ
∗
1
L
2
, L
3
⊂ Σ
∗
2
Σ
1
Σ
2
Σ
1
∩Σ
2
= ∅
L
1
(L
2
∩L
3
) = L
1
L
2
∩ L
1
L
3
?
L
1
L
2
L
3
L
1
(L
2
∩ L
3
)
L
1
L
2
∩ L
1
L
3
{a}
∗
{b}
∗
= {a
i
b
j
| i, j ∈ IN
0
}.
{a}
∗
{b}
∗
⊆ {a
i
b
j
| i, j ∈ IN
0
}
x ∈ {a}
∗
{b}
∗
x = yz, y ∈ {a}
∗
∧ z ∈ {b}
∗
{
}
⇒ x = yz,
(∃k ∈ IN
0
: y ∈ {a}
k
) ∧ (∃m ∈ IN
0
: z ∈ {b}
m
)
{ }
⇔ x = yz,
(∃k ∈ IN
0
: y = a
k
) ∧ (∃m ∈ IN
0
: z = b
m
)
⇔ ∃k, m ∈ IN
0
, x = a
k
b
m
⇒ x ∈ {a
i
b
j
| i, j ∈ IN
0
}.
{a
i
b
j
| i, j ∈ IN
0
} ⊆ {a }
∗
{b}
∗
x ∈ {a
i
b
j
| i, j ∈ IN
0
}
x = a
r
b
l
r, l ∈ IN
0
⇒ x ∈ {a}
∗
{b}
∗
,
a
r
∈ {a}
∗
, b
l
∈ {b}
∗
.
ut
({a}
∗
{b}
∗
)
∗
= {a, b}
∗
.
Σ
1
Σ
2
Σ
1
Σ
2
h : Σ
∗
1
→ Σ
∗
2
• h(λ) = λ
• h(uv) = h(u) ·h(v) u, v ∈ Σ
∗
1
h(a)
a ∈ Σ
1
h Σ
1
Σ
2
x = x
1
x
2
. . . x
m
x
i
∈ Σ
1
i = 1, . . . , m
h(x) = h(x
1
)h(x
2
) . . . h(x
m
).
h
h(#) = 10, h(0) = 00 h(1) = 11.
h {0, 1, #} Σ
bool
h(011#10 1#) = h(0 )h(1 )h(1 )h(#)h(1)h(0)h(1)h(#)
= 00111 11011 001110.
h
{0, 1, #} Σ
bool
10
{0, 1, #} Σ
bool
{0, 1, #} (Σ
bool
)
∗
Σ
logic
Σ
bool
Σ
bool
Σ
1
Σ
2
h
Σ
1
Σ
2
L ⊆ Σ
∗
1
h(L) = {h(w) | w ∈ L}.
L
1
, L
2
⊆ Σ
∗
1
h(L
1
)h(L
2
) = h(L
1
L
2
).
A
A : Σ
∗
1
→ Σ
∗
2
Σ
1
Σ
2
• Σ
1
• Σ
2
• A
A x A(x)
A A B
Σ A(x) = B(x)
x ∈ Σ
∗
Σ L ⊆ Σ
∗
(Σ, L) x ∈ Σ
∗
x ∈ L x /∈ L.
A (L, Σ) x ∈ Σ
∗
A(x) =
x ∈ L
x /∈ L
A L
L L
L
L ⊆ Σ
∗
Σ
∗
L L
{
= Σ
∗
− L
(Σ, L)
(Σ, L)
x ∈ Σ
∗
A(x) ∈ Σ
bool
= {0, 1},
A(x) =
x ∈ L
x /∈ L
({a, b }, {a
n
b
n
| n ∈ IN
0
})
({a, b }, {a
n
b
n
| n ∈ IN
0
})
x ∈ {a, b}
∗
x = a
n
b
n
n ∈ IN
0
(Σ
bool
, {x ∈ (Σ
bool
)
∗
| Number(x) }).
(Σ
bool
, {x ∈ (Σ
bool
)
∗
| Number (x) })
x ∈ (Σ
bool
)
∗
Number (x)
L = {x ∈ (Σ
keyboard
)
∗
| x }
x ∈ (Σ
keyboard
)
∗
x ∈ L
(Σ, HC) Σ = {0, 1, #}
11
12
HC = {x ∈ Σ
∗
| x
}.
(Σ
logic
, SAT)
SAT = {x ∈ (Σ
logic
)
∗
| x }.
A B
Σ Γ
A f : Σ
∗
→ Γ
∗
x ∈ Σ
∗
A(x) = f (x).
Σ Γ R ⊆ Σ
∗
×Γ
∗
A R
R x ∈ Σ
∗
(x, A(x)) ∈ R.
R x y
(x, y) ∈ R
R
fac
⊆ (Σ
bool
)
∗
× (Σ
bool
)
∗
(x, y) ∈ R
fac
• Number (y) Number (x)
13
14
f
L
L ⊆ Σ
∗
Σ
∗
{0, 1}
f
L
(x) = 1 x ∈ L
15
x y
(x, y) ∈ R
16
a b b a
a /∈ {1, b}
• y = 1 Number (x)
R
fac
x ∈ (Σ
bool
)
∗
y ∈ (Σ
bool
)
∗
y = 1 Number (x)
Number (y) Number (x) x
R
Proof
⊆ (Σ
keyboard
)
∗
× (Σ
keyboard
)
∗
(x, y) ∈ R
Proof
• x
y
• y =
t
x
x M(x)
x
R
(x, y) ∈ R y x.
R x
y M(x)
U = (Σ
I
, Σ
O
L, M, cost, goal)
• Σ
I
• Σ
O
• L ⊆ Σ
∗
I
x ∈ L U
• M L P(Σ
∗
O
x ∈ L
M(x) x
• cost cost :
S
x∈L
(M(x) × {x}) → IR
+
• goal ∈ {
17