Дехтярь М.И. Конечные автоматы (Лекции по дискретной математике)
Подождите немного. Документ загружается.
- -
x(t) . . . x(2)x(1) y(t) . . . y(2)y(1)
1, 2, . . . , t, t+
1, . . . x(1), x(2), . . . , x(t), x(t + 1), . . .
A y(1)y(2), . . . , y(t), y(t + 1), . . .
y(t)
t x(1), x(2), . . . , x(t)
Ψ(x(1), x(2), . . . , x(t)) = y(t)
t
x(1), x(2), . . . , x(t)
Q
q ∈ Q
x(1), x(2), . . . , x(t)
A =< Σ
X
, Σ
Y
, Q, q
0
, Φ, Ψ >
Σ
X
= {a
1
, . . . , a
m
} (m ≥ 1)
Σ
Y
= {b
1
, . . . , b
r
} (r ≥ 1)
Q = {q
0
, . . . , q
n−1
} (n ≥ 1)
q
0
∈ Q
Φ : Q × Σ
X
→ Q Φ(q, a)
q a
Ψ : Q × Σ
X
→ Σ
Y
Ψ(q, a) Σ
Y
q a
Φ, Ψ
mn q
i
a
j
→ Φ(q
i
, a
j
)/Ψ(q
i
, a
j
)
Φ Ψ
n × m
Q Σ
X
q
i
a
j
Φ(q
i
, a
j
)
Ψ(q
i
, a
j
).
A =< Σ
X
, Σ
Y
, Q, q
0
, Φ, Ψ >
D
A
= (Q, E)
q
0
q ∈ Q
|Σ
X
| a/b (a ∈ Σ
X
, b ∈ Σ
Y
)
q ∈ Q a ∈ Σ
X
a/Ψ(q, a) q q
0
= Φ(q, a)
x
1
x
2
. . . x
t
q(0) = q
0
x
1
q(1) = Φ(q
0
, x
1
) y(1) = Ψ(q
0
, x
1
) x
2
q(2) = Φ(q(1), x
2
) y(2) = Ψ(q(1), x
2
)
q(0), q(1), . . . , q(t), . . .
y(1), . . . , y(t), . . .
q(0) = q
0
q(1) = Φ(q(0), x
1
)
y(1) = Ψ(q
0
, x
1
)
. . .
q(t + 1) = Φ(q(t), x
i
)
y(t + 1) = Ψ(q(t), x
i
)
. . .
SUM
n
n n
SUM
x(i) = (x
1
(i), x
2
(i)) i (1 ≤ i ≤ r)
x
1
= x
1
(r) . . . x
1
(2)x
1
(1) x
2
= x
2
(r) . . . x
2
(2)x
2
(1)
x(r + 1) = ∗
(r + 1) y = x
1
+ x
2
x
1
(r) . . . x
1
(2) x
1
(1)
x
2
(r) . . . x
2
(2) x
2
(1)
y(r + 1) y(r) . . . y(2) y(1)
Σ
X
= {(00), (01), (10), (11), ∗},
Σ
Y
= {0, 1} SUM i
x
1
x
2
(i + 1) (x
1
(i + 1), x
2
(i + 1))
y(i + 1) i
Q = {q
0
, q
1
} q
0
q
1
SUM
Φ :
Q \ Σ
X
q
0
q
0
q
0
q
0
q
1
q
0
q
1
q
0
q
1
q
1
q
1
q
0
Ψ :
Q \ Σ
X
q
0
0 1 1 0
q
1
1 0 0 1
SUM
q
0
⇒
-
(00)/0
(01)/1
∗/0
(10)/1
q
0
q
1
(11)/1
(01)/0
(10)/0
-
(11)/0
(00)/0
∗/1
SUM
q
0
q
1
q
1
q
0
≥ 8
L
w w ∈ L?
w
A =< Σ, Q, q
0
, F, Φ, >
Σ = {a
1
, . . . , a
m
} (m ≥ 1)
Q = {q
0
, . . . , q
n−1
} (n ≥ 1)
q
0
∈ Q
F ⊆ Q
Φ : Q × Σ → Q Φ(q, a)
q a
Φ mn
q
i
a
j
→ Φ(q
i
, a
j
)
Φ
n × m Q
Σ q
i
a
j
Φ(q
i
, a
j
)
A =< Σ, Q, q
0
, Φ >
D
A
= (Q, E)
q
0
q ∈ Q |Σ
X
|
a ∈ Σ q ∈ Q a ∈ Σ
q q
0
= Φ(q, a) a
p = e
1
e
2
. . . e
t
w = w
1
w
2
. . . w
t
w
i
e
i
(1 ≥ i ≥ t)
q q
0
w q q
0
A =< Σ, Q, q
0
, F, Φ, >
(q, w) q ∈ Q w ∈ Σ
∗
Σ
∗
Σ, ε
`
A
(q, w) `
A
(q
0
, w
0
) ⇔ w = aw
0
, Φ(q, a) = q
0
w = ε q ∈ Q (q, ε) `
A
(q, ε)
`
∗
A
`
A
(q, w) `
∗
A
(q
0
, w
0
) A
q w = w
1
. . . w
l
0 ≤ k ≤ l
k w q
0
w
0
= w
k+1
. . . w
l
w
A w
q ∈ F
(q
0
, w) `
∗
A
(q, ε) w
L
A
A,
L
A
= {w | A w}
ε ∈ L
A
⇔ q
0
∈ F
A B
L
A
= L
B
A w
q ∈ F D
A
q
0
q w
w q
0
q
w
L
A
A
D
A
q
0
F
L
L Σ = {a, b}
aa b
aa q
0
a q
1
a
q
1
q
2
ab, ba, bb
L
q
!
b
L aa b
q
2
q
3
⇒
q
0
q
1
q
2
?
a
q
3
?
a
q
!
a, b
-
@
@
@
@R
?
-
-
a a
b
b
b b
⇒
A
w = aaababa
(q
0
, aaababa) `
A
(q
1
, aababa) `
A
(q
2
, ababa) `
A
(q
2
, baba) `
A
(q
3
, aba) `
A
(q
3
, ba) `
A
(q
2
, a) `
A
(q
2
, ε)
q
2
w /∈ L
A
w
1
= wb =
aaababab
(q
0
, w
1
) `
∗
A
(q
3
, ε) w
1
∈ L
A
A
L
q ∈ Q L(q)
q
0
q
L = ∪
q∈F
L(q)
A
L(q
0
) = {ε}
L(q
1
) = {a},
L(q
2
) = {w | aa b},
L(q
3
) = L,
L(q
!
) = {w | aa}.
L(q
0
), L(q
1
) L(q
!
)
A q
0
q
2
aa
L(q
2
) q
0
q
3
aab
L(q
3
) w ≤ n
w q
0
q
i
(i = 2, 3) ⇔ w ∈ L(q
i
).
n + 1.
|w| = n + 1. w = w
0
α α ∈ {a, b}. |w
0
| = n, w
0
w
0
q
0
q
2
aa
b α = a w q
0
q
2
aa b α = b w q
0
q
3
aa b L.
w
0
q
0
q
3
aa
b α = a w q
0
q
3
aa b α = b w q
0
q
2
aa b α = a w q
0
q
i
(i = 2, 3) ⇔ w
0
q
0
q
i
(i = 2, 3)
b w w
0
α = b A
w q
0
q
2
⇔ w
0
q
0
q
3
w q
0
q
3
⇔
w
0
q
0
q
2
b w w
0
A q
3
L
A
= L(q
3
) = L
M
1
=< Σ, Q
1
, q
1
0
, F
1
, Φ
1
> M
2
=< Σ, Q
2
, q
2
0
, F
2
, Φ
2
>
Σ L
1
L
2
M =< Σ, Q, q
0
, F, Φ > M
1
M
2
(M = M
1
× M
2
) Q = Q
1
× Q
2
= {(q, p) | q ∈ Q
1
, p ∈ Q
2
}
(q, p) a ∈ Σ Φ((q, p), a) =
(Φ
1
(q, a), Φ
2
(p, a)). M q
0
= (q
1
0
, q
2
0
)
L
1
L
2
M
F
∪
= {(q, p) | q ∈ F
1
p ∈ F
2
} M =< Σ, Q, q
0
, F
∪
, Φ >
L = L
1
∪ L
2
F
∩
= {(q, p) | q ∈ F
1
p ∈ F
2
} M =< Σ, Q, q
0
, F
∩
, Φ >
L = L
1
∩ L
2
F
\
= {(q, p) | q ∈ F
1
p /∈ F
2
} M =< Σ, Q, q
0
, F
\
, Φ >
L = L
1
\ L
2
(q, p) (q
0
, p
0
) M
w w (q, p) (q
0
, p
0
) M
q q
0
M
1
p p
0
M
2
.
w
σ = {a, b}
L = {w | w }
L = {w | w
0
aab
0 0
bba
0
}
L = {w | w }
L = {w | }
(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).