Σ - ө қ: 0- ө ; 1- ө ; 
, 
- ө ; 
ө , (
), (
) ә 
ө ө .
қ қ, 
ң ө ғ, ө ң қ қғ ғ . ө -ң 
.
: 
. 
ө .
Ә ө 
қ құ, қ:
1) L(a)⇔{a}, 
,
2) L(0)⇔ø,
3) L(1)⇔{e},
4) L(e*f)⇔ 
,
5) 
: L- , қ ө қ.
: - ө .
1) 
2) 
3) e+0=e 4) 
5) 
6) 
8) 
9) 
10) 
11) 
: - 
ө ү -ң :
1) 
2) 
3) 
4) 
: - 
L , : 
. қ ққ .
5. қ , қ . . қ . қ (finite automaton,FA) M=(Q，Σ，δ，q0，F) Qүң қ . ∀q∈Q，q- M-ң ү . (state). Σ (Input alphabet). ө Σ ғ c . q0q0∈Q, M-ң қ ү (initial state). δү (transition function). δ：Q×Σ→Q, ∀(q，a)∈Q×Σ，ү δ(q，a)=p қ ：M-ң q ү ұ a қ, ү p-ғ ңғ қ қ . FF⊆Q, M-ң қ үң (final state). ∀q∈F, q- M-ң қ ү қ ү (accept state). қ: (instantaneous description) қ (Q, Σ, ∆, I, F) - ұ (q, 
) , ұ q∈Q ә ∈ 
.
қ: қ ң ө қ қ қ 
қ. (p, x, q) ∈∆ ә ∈ , (p, x ) 
(q, w)
δ қ: 
: Q× 
> Q. - q∈Q ∈ ∈ ү (1) (q, 
)= q (2) (q, 
)= δ (
(q, 
), a) (q, )= (q, 
)= δ ( (q, 
), a) = δ(q, ) q∈Q, a∈Σ ү δ(q,a)-қ қғ ә , қ M- қ : ∀x∈Σ*ү, δ(q,w)∈F , x- M-қ , δ(q,w) ∉F , M- x- қ . L(M)={x| x∈Σ*ә δ(q,w)∈F } M- қ . -L(M1)=L(M2)={02n|n≥1} L(M1)=L(M2), M1 M2 . q 
қ w қ , ө (q, ) =
|
|
|
6.қ ұғ. қ . қ - ұ ұ:=(K, Σ, ∆, s, F) K- қ үң Σ- s∈K- қ ү F 
- қ ү ∆- ө ү, K×(Σ 
K қ: (instantaneous description) қ (Q, Σ, ∆, I, F) - ұ (q, ) , ұ q∈Q ә ∈ . 
ә қ qi- qj - w
Ә ү (q, u, p) ∈∆ ө ; ұ ғң . қғ қ қ iң қ ө ұқ. ұ K× 
. ң ғ ғ 
қ: (q, w) 
(
) ә ғ, u∈ 
{e} ғ ғ, w=u 
ә (q, u, 
) ∈∆. ққ ү : ғ (q, w) ұ ү () қ ұ ү - (q, w) ().
7. ң
.
L(
)=L(
)
NFA=DFA?
{NFA қ } = {DFA қ } ә: NFA ә DFA ү 1 : {NFA қ } 
{DFA қ }
ә: ә DFA-NFA , DFA қ NFA қ.
2 Қ: {NFA қ } ⊆ {DFA қ }
ә: NFA- ә - DFA-ғ ғ . NFA қғ DFA қ.
NFA- DFA-ғ
