ify"> правилом A В® w B.
2. Замінити кожне правило виду A В® a 1 ... a n B, для n> 1, на правила:
A В® a 1 A 1
A 1 В® a 2 A 2
... n-1 В® a n A n ,
де: A i , для (1
3. Якщо є правила виду А В® B, то, по-перше, видалити правила B В® B (якщо такі є), по-друге, замінити їх правилами види: A В® a, для всіх A і a, для яких існують правила A В® B і B В® a.
Застосувавши дану процедуру переказу до отриманої праволінейной граматиці G ', отримаємо таку автоматну граматику:
В
4. ПОБУДОВА недетермінірованного кінцевих автоматів
Процедуру побудови недетермінірованного автомата по автоматною граматиці:
1. Вхідним безліччю автомата буде термінальне безліч граматики;
2. Безліччю станів автомата буде нетермінальний безліч граматики, а в якості початкового стану виступатиме початковий нетермінальний символ граматики - S;
. За правилом Z В® < span align = "justify"> e стан Z буде допускає;
. Для всіх правил граматики за правилом A В® xB вводимо в автоматі перехід зі стану A в стан B по входу x
. Щоб отримати повністю певни...
