Page 17 - 4625

1. Довільний скінченний автомат з пустою множиною
заключних станів (а мінімальний – з пустою множиною ста-
нів) допускає ;
2. Розглянемо автомат М =<{q }, , q , , {q }>, у
0
0
0
якому  не визначено для жодних а  .
Тоді L(M) = {}.
3. Розглянемо автомат М =<{q , q }, , q , , {q }>, у
0
0
1
1
якому функція  визначена лише для пари (q , a), а саме: (q ,
0
0
a) = q .
1
Тоді L(M) = {a}.
Твердження: Якщо M =<Q , , q , δ , F > та M =
2
1
1
1
1
01
<Q , , q , δ , F >, що визначають відповідно мови L(M )
02
1
2
2
2
та LM ), то скінчено автоматними мовами будуть:
2
- L(M )  L(M );
2
1
- L(M ) * L(M );
1
2
- {L(M )} = {}  L(M )  L(M )* L(M )  ….,
1
1
1
1
де:
L(M )  L(M ) = {w | w  L(M ) або w  L(M )},
2
1
2
1
L(M ) * L(M ) = {w = xy | x  L(M ), y  L(M )}.
2
1
1
2
Доведення:
1. Побудуємо автомат М = <Q, , q , , F>, такий що
0
L(M) = L(M )  L(M ).
2
1
- Q = Q  Q  {q }, де q – новий стан (q  Q 
0
1
0
2
1
0
Q );
2
- функцію  визначимо таким чином:
(q ,a) = δ (q, a), q  Q , а  ;
1
1
(q, a) = δ (q, a), q  Q , а  ;
2
1
(q , a) = δ (q , a) δ (q , a), q 01  Q , q 02  Q , а ;
1
1
0
1
02
2
01
- множина заключних станів: 
F = { F 1  F 2 , якщо   (L  L 2 ) }
F 1  F 2 , q 0 , якщо   ( L 1  L 2 )
Побудований у цьому випадку автомат взагалі недетер-

мінований. Індукцією по i >=1 покажемо, що (q ,w) ⊨ (q, )
i
0
16