Page 18 - 4625

i
можливо тоді і тільки тоді, коли (q ,w) ⊨ (q, ), q F або
1
01

(q ,w) ⊨ (q, ), q  F 
i
2
02
2. Побудуємо автомат М = <Q, , q , , F>, такий що
0
L(M) = L(M ) * L(M ):
1
2
- Q =Q  Q ;
1
2
- q =q ;
0
01
- функцію  визначимо таким чином:
(q, a) = δ (q, a), q  Q \F , а  ;
1
1
1
(q, a) = δ (q, a), q  Q , а  ;
2
2
(q, a) = δ (q, a)  δ (q , a), q F , q 02  Q , а  ;
1
1
2
02
2
- множина заключних станів: 
F = { F 2 , якщо   L 2 }
F 1  F 2 , якщо   L 2
3. Побудуємо автомат М = <Q, , q , , F>, такий що L(M)
0
= {L(M )}:
1
- Q = Q  {q }, де q – новий стан (q  Q );
0
0
1
0
1
- функцію  визначимо таким чином:
(q, a) = δ (q, a), q  Q \F , а  ;
1
1
1
(q , a) = δ (q , a), q 01  Q , а  ;
1
1
0
01
(q ,a) = δ (q ,a)  δ (q , a), q F , а  ;
01
1
1
1
- множина заключних станів F = F  {q }.
1
0

2.3 Скінчені автомати та праволінійні граматики
Означення: Породжуюча граматика G – це п’ятірка G =<
N, S, P, S>,
де:
N – скінченна множина - допоміжний алфавіт (нетерміна-
ли);
 – скінченна множина – основний алфавіт (термінали);
P – скінченна множина правил виду
  ,   (N)* N (N)*,   (N).
*
*
S – виділений нетермінал (аксіома).
17