Page 21 - 4625

Далі, на основі граматики G побудуємо скінченний авто-
1
мат М, таким чином:
- як імена станів автомата візьмемо нетермінали гра-
матики G ;
1
- початковий стан автомата позначається аксіомою S;
- функція  визначається діаграмою переходів, яка бу-
дується на основі правил виду A  a A :
i
j
k

Рисунок 7

- множина F заключних станів скінченного автомата
визначається так:
F = {A | A   }.
i
i
Індукцією по довжині вхідного слова покажемо, що якщо
S  n−1 w, то (q , w) ⊨ (q, ): базис i = 0: S  , тоді (q , )
n
0
0
⊨ (q , ).
0
0
i
Нехай |w| = i+1, тобто w = aw : тоді S  a A p  aw та
1
1
(q ,aw ) |= (q , w ) |⊨ i−1 (q, ), q  F. Доведення навпаки є
0
i
1
1
очевидним.

2.4 Регулярні множини та регулярні вирази
Означення: Нехай  - скінчений алфавіт. Регулярна
множина в алфавіті визначається рекурсивно:
П1.  - пуста множина – це регулярна множина в алфавіті
;
П2. {} – пусте слово – регулярна множина в алфавіті ;
П3. {a} – однолітерна множина – регулярна множина в
алфавіті ;
П4. Якщо P та Q – регулярні множини, то такими є
наступні множини:
P  Q (операція об’єднання);
P*Q (операція конкатенації);

20