Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
3
•
•
1
2
•
IN = {1, 2, . . .}
IN
0
= IN ∪{0}
• Σ
bool
= {0, 1}
• Σ
lat
= {a, b, c, . . . , z}
• Σ
keyboard
= Σ
lat
∪{A, B, . . . , Z,
t
, >, <, (, ), . . . , !}
t
• Σ
m
= {0, 1, 2, . . . , m −1} m ≥ 1 m
• Σ
logic
= {0, 1, x, (, ), ∧, ∨, ¬}
3
4
IN = {0, 1, 2, . . .} 0
Σ Σ
Σ λ
w Σ |w|
Σ Σ
∗
Σ
+
= Σ
∗
− {λ}
0, 1, 0 , 0, 1, 1 Σ
bool
Σ
keyboard
|0, 1, 0, 0, 1, 1| = 6 λ
|λ| = 0
x
1
x
2
. . . x
n
x
1
, x
2
, . . . , x
n
.
010011 0, 1, 0 , 0, 1, 1
t
Σ
keyboard
λ
t
Σ
keyboard
|
t
| = 1
t
Σ
keyboard
(Σ
bool
)
∗
= {λ, 0, 1, 00, 01, 10, 11, 0 00, 001, 010, 100, 011, . . .}
= {λ} ∪{x
1
x
2
. . . x
i
| i ∈ IN
0
, x
j
∈ Σ
bool
j = 1, . . . , i}.
Σ i ∈ IN
0
i Σ
Σ = {0, 1, #} k n
k ≤ n
• n k 0
• n k
0
x = x
1
x
2
. . . x
n
∈ (Σ
bool
)
∗
, x
i
∈ Σ
bool
i = 1, . . . , n
Number(x) =
n
X
i=1
2
n−i
·x
i
.
5
λ
Λ e
m
Bin(m) ∈ Σ
∗
bool
m
Number(Bin(m)) = m.
m
1 Bin(m) m
x ∈ (Σ
m
)
∗
m ≥ 2
x m
Number
m
(x) Number
m
(x) x
a
1
, a
2
, . . . , a
m
m ∈ IN
0
a
i
∈ IN
0
i = 1, . . . , m
Bin(a
1
)#Bin(a
2
)# ···#Bin(a
m
) ∈ {0, 1, #}
∗
.
G = (V, E) V E ⊆
{(u, v) | u, v ∈ V, u 6= v} |V | = n
V G M
G
0 1 M
G
= [a
ij
]
n × n
a
ij
= 1 ⇐⇒ (v
i
, v
j
) ∈ E.
a
ij
= 1 G (v
i
, v
j
) v
i
v
j
a
ij
= 0 G M
{0, 1, #}
M #
0 0 1 1
0 0 1 1
0 1 0 1
0 0 0 0
.
0011#0011#0101#0000#.
6
Bin( m)
Number (Bin(m )) = m Bin( m)
1
v
1
v
2
v
3
v
4
{0, 1, #} n(n+1) n
Σ
bool
G = (V, E, h) h E IN
e ∈ E
a
ij
= 0
,
{v
i
, v
j
} G
{v
i
, v
j
} ∈ E
a
ij
= h({v
i
, v
j
}),
{v
i
, v
j
}
v
1
v
2
v
3
v
4
v
5
1
1
1
6
6
5
7
a
ij
=
h({v
i
, v
j
}) #
#
7
8
u v {u, v} u
v (u, v)
0 7 0 6 1
7 0 1 1 0
0 1 0 6 0
6 1 6 0 5
1 0 0 5 0
{0, 1, #}
0#111#0#110#1##111#0#1#1#0##0#1#0#110#0##110#1#110#
0#101##1#0#0#101#0.
M
G
= [a
ij
]
G a
ij
= a
ji
i, j
G
M
G
G {0, 1, #}
111#0#110#1##1#1#0##110#0##101.
¬ ∨ ∧
x
1
, x
2
, x
3
, . . .
x
1
, x
2
, x
3
, . . .
Σ
logic
= {0, 1, x, (, ), ∧, ∨, ¬}
x
i
xBin(i)
i ∈ IN
(x
1
∨ x
7
) ∧ ¬(x
12
) ∧ (x
4
∨ x
8
∨ ¬(x
2
))
(x1 ∨ x111) ∧ ¬(x1100) ∧ (x100 ∨ x1000 ∨ ¬(x10)).
Σ
Σ K : Σ
∗
× Σ
∗
→ Σ
∗
K(x, y) = x · y = xy
x, y ∈ Σ
∗
x = 0aa1bb y = 111b Σ = {0, 1, a, b} K(x, y) = x ·y = 0 aa1bb11 1b