Дехтярь М.И. Конечные автоматы (Лекции по дискретной математике)
Подождите немного. Документ загружается.
M =< Σ, Q, q
0
, F, Φ >
Σ = {a
1
, . . . , a
m
} (m ≥ 1)
Q = {q
0
, . . . , q
n−1
} (n ≥ 1)
q
0
∈ Q
F ⊆ Q
Φ : Q × (Σ ∪ {ε}) → 2
Q
a ∈ Σ Φ(q, a)
q a Φ(q, ε)
q
q ∈ Q a ∈ Σ
q
0
∈ Φ(q, a) qa → q
0
q
0
∈ Φ(q, ε) q → q
0
q ∈ Q a ∈ Σ
qa → q
0
ε q → q
0
q q
0
Φ (m + 1)
ε q a ∈ (Σ ∪ {ε})
Φ(q, a)
M =< Σ, Q, q
0
, Φ > D
M
=
(Q, E) q
0
F qa → q
0
(a ∈ Σ)
(q, q
0
a q → q
0
(q, q
0
ε.
p = e
1
e
2
. . . e
T
D
M
w = w
1
w
2
. . . w
t
(t ≤ T )
ε t p
0
= e
j
1
e
j
2
. . . e
j
t
w w
i
e
j
i
(1 ≤ i ≤ t)
p
ε
k
1
w
1
ε
k
2
w
2
. . . ε
k
t
w
t
ε
k
t+1
k
j
≥ 0 (j = 1, 2, . . . , t + 1) t +
P
t+1
j=1
k
j
= T
w q q
0
D
M
q q
0
w
M =< Σ, Q, q
0
, F, Φ, >
(q, w) q ∈ Q w ∈ Σ
∗
`
M
(q, w) `
M
(q
0
, w
0
) ⇔ (w = aw
0
q
0
∈ Φ(q, a)) (w = w
0
q
0
∈ Φ(q, ε)).
`
∗
M
`
M
M w q ∈ F
(q
0
, w) `
∗
M
(q, ε)
L
M
M
L
M
= {w | M w}
w
F
D
M
M
w
q ∈ F D
M
w q
0
q D
M
q
0
q w ε
N
1
=< {a, b}, {0, 1, 2, 3, 4}, 0, {3}, Φ >
Φ :
Q \ Σ
X
ε
0 {0, 1} {0} ∅
1 ∅ ∅ {4}
2 {3} ∅ ∅
3 ∅ ∅ {1}
4 ∅ {2} ∅
D
N
1
3
a
?
ε
?
b
Q
Q
Q
Q
Q
Q
Qk
ε
3
a
H
H
H
H
H
H
HY
ε
⇒
a, b
N
1
ababa
(0, ababa) `
N
1
(1, baba) `
N
1
(4, baba) `
N
1
(2, aba) `
N
1
(0, aba) `
N
1
(1, ba) `
N
1
(4, ba) `
N
1
(2, a) `
N
1
(3, ε). ababa ∈ L
N
1
.
N
1
M A L
A
= L
M
M =< Σ, Q, q
0
, F, Φ >
M
M
1
ε
M
1
A
M
ε D
ε
= (Q, E
ε
) E
ε
= {(q, q
0
) | q
0
∈ Φ(q, ε)} D
ε∗
= (Q, E
∗
ε
)
D
ε
E
∗
ε
= {(q, q
0
) | q =
q
0
D
ε
q q
0
}.
M
1
=< Σ, Q
1
, q
0
, F
1
, Φ
1
>
Q
1
= {q
0
} ∪ {q | q
0
∈ Q a ∈ Σ, q ∈ Φ(q
0
, a)}
F
1
= {q | q
0
∈ F, (q, q
0
) ∈ E
∗
ε
}
M
ε
q
0
∈ Q, a ∈ Σ
Φ
1
(q, a) = {r | q
0
∈ F, (q, q
0
) ∈ E
∗
ε
r ∈ Φ(q
0
, a)} D
M
1
a q r D
M
ε
q
0
a r
M
1
ε M M
1
L
M
1
= L
M
w = w
1
w
2
. . . w
t
w ∈ L
M
1
D
M
1
p =
e
1
e
2
. . . e
t
(e
1
= (q
0
= r
0
, r
1
), e
i
= (r
i−1
, r
i
), i = 2, . . . , t) q
0
r
t
∈ F
1
w e
i
w
i
Φ
1
e
i
(r
i−1
, r
i
)
D
M
r
i−1
r
i
ε w
i
D
M
q
0
r
t
w r
t
∈ F
1
r
t
∈ F D
M
ε r
t
r
0
∈ F
D
M
q
0
w w ∈ L
M
w ∈ L
M
D
M
q
0
r w r
0
= q
0
r
i
w
i
(i = 1, . . . , t)
r
i−1
r
i
w
i
ε Φ
1
D
M
1
r
i−1
r
i
w
i
D
M
1
q
0
r
t
r
t
= r ∈ F D
M
r
t
ε r ∈ F F
1
r
t
∈ F
1
. w ∈ L
M
1
2
T
a T
0
T a
M
1
=< Σ, Q
1
, q
0
, F
1
, Φ
1
> A =< Σ, Q
A
, q
A
0
, F
A
, Φ
A
>
Q
A
= {Q
0
| Q
0
⊆ Q
1
}
q
A
0
= {q
0
}
F
A
= {Q
0
| Q
0
∩ F
1
6= ∅}
Φ
A
(Q
0
, a) = {q | q
0
∈ Q
0
, q ∈ Φ
1
(q
0
, a)}
A
Q
0
, Q
00
Q
A
w ∈ Σ
∗
(Q
0
, w) `
∗
A
(Q
00
, ε) ⇐⇒ Q
00
= {r | q
0
∈ Q
0
, (q, w) `
∗
M
1
(r, ε)}
w
|w| = 0 w = ε Q
0
= Q
00
|w| = 1 w = a ∈ Σ
Φ
A
(Q
0
, a)
≤ k
|w| = k + 1 w w = aw
0
˜
Q
(Q
0
, a) `
A
(
˜
Q, ε) (
˜
Q, w
0
) `
∗
A
(Q
00
, ε) |w
0
| = k
Q
00
= {r | q
0
∈
˜
Q, (q, w
0
) `
∗
M
1
(r, ε)} Φ
A
˜
Q = {q | q
0
∈
Q
0
, q ∈ Φ
1
(q
0
, a)} Q
00
= {r | q
0
∈
Q
0
, (q, w) `
∗
M
1
(r, ε)}
2
L
A
= L
M
1
w q
0
q ∈ F
1
M
1
Q
0
= {q
0
} q ∈ Q
00
Q
00
(Q
0
, w) `
∗
A
(Q
00
, ε) Q
00
∈ F
A
w ∈ L
A
w ∈ L
A
Q
00
∈ F
A
({q
0
}, w) `
∗
A
(Q
00
, ε)
Q
00
q ∈ F
1
M
1
(
q
0
, w
)
`
∗
M
1
(
q, ε
)
} w
∈
L
M
1
.
2
N
1
E
∗
ε
= {(2, 0), (1, 4), (3, 1), (4, 1)} M
1
3
a
?
6
b a
Q
Q
Q
Q
Q
Q
Qk
a, b
3
a
+
b
⇒
a, b
M
1
N
1
ε
M
1
A
Q
A
= {∅, {0}, {1}, {2}, {3}, {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3},
{1, 2, 3}, {0, 1, 2, 3}}.
M
1
F
A
= {{3}, {0, 3}, {1, 3}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {0, 1, 2, 3}}
Φ
A
Q
A
\ Σ
∅ ∅ ∅
{0} {0, 1} {0}
{1} ∅ {2}
{2} {0, 1, 3} {0}
{3} ∅ {2}
{0, 1} {0, 1} {0, 2}
{0, 2} {0, 1, 3} {0}
{0, 3} {0, 1} {0, 3}
Q
A
\ Σ
{1, 2} {0, 1, 3} {0, 2}
{1, 3} ∅ {2}
{2, 3} {0, 1, 3} {0, 2}
{0, 1, 2} {0, 1, 3} {0, 2}
{0, 1, 3} {0, 1} {0, 2}
{0, 2, 3} {0, 1, 3} {0, 2}
{1, 2, 3} {0, 1, 3} {0, 2}
{0, 1, 2, 3} {0, 1, 3} {0, 2}
{0} {0, 1}
{0, 2} {0, 1, 3} {0}
A
A
N
1
3
a
?
b
Q
Q
Q
Q
Q
Q
Qk
b
3
a
+
b
H
H
H
H
H
H
HY
a
⇒
b
A
n
2
n
A
0
aba
0
M
M =< {a, b}, {0, 1, 2}, 0, {2}, Φ > Φ : 0a → 1, 0 → 1, 1b → 2,
1 → 2, 2b → 2.
M =< {a, b}, {0, 1, 2}, 0, {2}, Φ > Φ : 0a → 1, 0a → 2,
1b → 2, 1 → 2, 2b → 0.
M =< {a, b}, {0, 1, 2, 3}, 0, {2, 3}, Φ > Φ : 0a → 1, 0a → 2,
0 → 1, 1b → 1, 1 → 2, 2a → 3, 3b → 1, 3 → 0
∅, ε, a ∈
Σ ◦
∗
r L
r
L
1
L
2
Σ
L = L
1
◦ L
2
= {w | (∃w
1
∈ L
1
)(∃w
2
∈ L
2
)(w = w
1
w
2
)}
ε ∈ L
1
L
2
⊆ L ε ∈ L
2
L
1
⊆ L
L
L
0
= {ε}
L
1
= L
L
i+1
= L ◦ L
i
(i = 1, 2, . . .).
L
i
i
L
(L)
∗
L
L
(L)
∗
= {ε} ∪ {w | (∃k ≥ 1)(w = w
1
w
2
. . . w
k
) w
i
∈ L}
(L)
∗
=
S
∞
i=0
L
i
L
+
=
S
∞
i=1
L
i
L ◦ L
∗
Σ = {a
1
, . . . , a
m
}
Σ
∗
Σ
Σ
∗
Σ
r L
r
∅ L
∅
= ∅
ε L
ε
= {ε}
a ∈ Σ L
a
= {a}
r
1
r
2
L
r
1
L
r
2
r = (r
1
+ r
2
) L
r
= L
r
1
∪ L
r
2
r = (r
1
◦ r
2
) L
r
= L
r
1
◦ L
r
2
r = (r
1
)
∗
L
r
= L
∗
r
1
◦
∗
(((1 ◦ 0) ◦ ((1)
∗
+ 0)) 10(1
∗
+ 0)
r p
L
r
= L
p
r = p
r + p = p + r
(r + p) + q = r + (p + q)
(rp)q = r(pq)
(r
∗
)
∗
= r
∗
(r + p)q = rq + pq
(r+p)
∗
=
(r
∗
p
∗
)
∗
L
1
L
2
ε w ∈ L
1
L
r
∪ L
p
L
0
= L
∗
r
L
∗
p
w ∈ L
2
= (L
0
)
∗
. w ∈ L
2
L
0
v
v = v
1
1
. . . v
1
k
v
2
1
. . . v
2
l
i = 1, . . . , k v
1
i
∈ L
r
j = 1, . . . , l
v
2
j
∈ L
p
k l w
L
r
∪ L
p
w ∈ L
1
(0 + 1)
∗
{0, 1}
11(0 + 1)
∗
001
{0, 1},
(1 + 01 + 001)
∗
(ε + 0 + 00)
{0, 1}
1
∗
(01
∗
01
∗
)
∗
L
0
{0, 1},
L
0
1
∗
01
i
01
j
, i, j ≥
0, (01
∗
01
∗
)
L
0 1
{0, 1},
w = w
1
w
2
. . . w
n
L
0 1
n
n = 2k w p
i
= w
2i−1
w
2i
i = 1, 2, . . . , k
w
(01 + 10)(00 + 11)
∗
(01 +
10)(00+11)
∗
(00 + 11)
∗
R
0 1
L
0 1
R
0 1
= (00 + 11)
∗
((01 + 10)(00 + 11)
∗
(01 + 10)(00 + 11)
∗
)
∗
p
∗
(p + q)
∗
= (p + qp
∗
)
∗
= (p + q)
∗
p(qp)
∗
= (pq)
∗
p
(p
∗
q
∗
)
∗
= (q
∗
p
∗
)
∗
(pq)
+
(q
∗
p
∗
+ q
∗
) = (pq)
∗
pq
+
p
∗
L
Σ = {0, 1}
L = {w | w }
L = {w | w }
L = {w | w }
(0
∗
1
∗
)0
(01
∗
)0
(00 + 11 + (01 + 10)(00 + 11)
+
(01 + 10))
∗
(00
∗
)0 + (00)
∗
(0 + 1)(ε + 00)
+
+ (0 + 1)
(0 + ε)0
∗
1