Головна |
Будь-яке регулярне безліч, яке розпізнається КА, можна описати за допомогою автоматної граматики. Алгоритм побудови граматики наступний:
1. Початковий символ граматики - початковий стан КА.
2. Термінальні символи граматики - алфавіт КА (без символу
"Кінець ланцюжка" - +).
3. Нетермінальні символи граматики - безліч станів КА.
4. Якщо в таблиці переходів КА є перехід зі стану А в стан В при надходженні вхідного символу х - ввести правило такого вигляду: А -> xB.
5. Якщо D - допускає стан КА, то ввести правило такого вигляду: D -> @ (@ -Нехай ланцюжок).
Приклад Заданий КА a b - +
- Вхідний алфавіт V = {a, b, - +}; => A | A B | доп
- Безліч станів S = {A, B, C}; | |
- Початковий стан A; B | A C | відп
- Безліч допускають станів | |
S1 = {A, C}. C | C B | доп
L ---
Побудувати граматику, мовою якої буде безліч ланцюжків, що допускаються заданим КА.
Рішення
1. Початковий символ граматики A.
2. Безліч термінальних символів граматики VT = {a, b}.
3. Безліч нетермінальних символів VN = {A, B, C}.
4. Безліч правил P = {A -> aA (1); A -> bB (2); B -> aA (3);
B -> bC (4); C -> aC (5); C -> bB (6); A -> @ (7); C -> @ (8)}.
Для перевірки правильності побудови граматики отримаємо висновок ланцюжка aaabb, яка допускається заданим КА.
(1) (1) (1) (2) (4) (8) (правила)
A -> aA -> aaA -> aaaA -> aaabB -> aaabbC -> aaabb
Для будь-якої автоматної граматики (граматика типу 3) можна побудувати КА-распознаватель. Алгоритм побудови КА - распознавателя наступний:
1. Вхідний алфавіт КА V = {VT, - +}.
2. Безліч станів КА S = {VN, F} (F-фінішне стан КА - єдине допускає стан КА-розпізнавача).
3. Початковий стан КА - початковий символ граматики.
4. Безліч допускають станів S1 = {F}.
5. Таблиця переходів КА (керуюча таблиця) будується наступним чином:
- Позначити стовпці таблиці символами вхідного алфавіту КА
(Останній стовпець - символ "кінець ланцюжка");
- Позначити рядки таблиці станами КА (перший рядок-початковий стан КА);
- В соответстви з правилами X -> yZ заповнити клітину таблиці на перетині рядка Х і стовпці y переходом в стан Z;
- Відповідно до правил Х -> z заповнити клітину таблиці на перетині рядка Х і стовпці z переходом в стан F;
- Заповнити клітини останнього стовпчика (всі "відп.", Крім перетину F і - + - "доп.");
- Залишилися незаповненими клітини таблиці заповнити символом Е-стан помилки (якщо КА потрапив в цей стан, то викликається зовнішня процедура обробки помилок, а ланцюжок відкидається, як невідповідна граматиці); допускається залишати залишилися клітини незаповненими, маючи на увазі перехід в порожнє безліч - то ж стан помилки (це зручно при побудові НКА).
Примітки:
1. Перед початком побудови КА-распознавателя перевірити безліч нетерміналів граматики G на продуктивність і досяжність; при необхідності виконати еквівалентні перетворення граматики G в G1 з укороченим безліччю правил Р.
2. Якщо в безлічі правил Р для однакових лівих частин праві частини правил починаються з однакового термінального символу, то при побудові вийде НКА-распознаватель, який потім можна
перетворити в КА-распознаватель.
приклад
Для граматики G [Z] побудувати КА-распознаватель.
G [Z] = (VT = {a, b, c}; VN = {Z, A, B}; Z; P = {Z-> aA, A-> bA, A-> cB, B-> cZ ,
B-> b, A-> a}).
Рішення
1. Перевірка нетерміналів граматики G [Z] на продуктивність і досяжність.
а) продуктивні нетермінали A і В (на підставі двох останніх правил); на підставі першого правила продуктивний нетермінал Z;
б) можна досягти все термінали (правила 1 і 3).
2. Задамо параметри автомата-розпізнавача:
- Вхідний алфавіт {a, b, c, - +};
- Безліч станів автомата S = {Z, A, B, F};
- Початковий стан автомата - Z;
- Безліч допускають станів автомата S1 = {F};
- Таблиця переходів (керуюча таблиця автомата) має вигляд:
г ======= T ===== T ====== T ====== T === T ==
| | A | b | c | - + |
| --- + --- + --- + --- + --- |
| Z | A | E | E | відп. |
| --- + --- + --- + --- + --- |
| A | F | A | B | відп. |
| --- + --- + --- + --- + --- |
| B | E | F | Z | відп. |
| --- + --- + --- + --- + --- |
| F | E | E | E | доп. |
L ======= | ===== | ====== | ====== | ====== -
По виду таблиці переходів видно (в кожній клітині один стан), що отриманий КА-распознаватель, який можна перевірити
на еквівалентність станів і мінімізувати (перевірити самостійно).
Перевірка роботи КА: Нехай задана ланцюжок з граматики G [Z] abccaa (висновок в граматиці отримати самостійно).
Необроблена Поточний стан Новий стан
ланцюжок КА - роз-ля КА - роз-ля
abccaa- + Z A
bccaa- + A A
ccaa- + A B
caa- + B Z
aa- + Z A
a- + A F
- + F доп.
Примітка: по самому лівому символу необробленої чіпкий і поточному стану КА відповідно до таблиці переходів виробляється новий стан.
Задана ланцюжок буде допущена побудованим КА-розпізнавачем.
Зміна напрямку рекурсії | Побудова КА-распознавателей для праволінейних граматик
ДОНБАСЬКИЙ ІНСТИТУТ ТЕХНІКИ І МЕНЕДЖМЕНТУ | МІЖНАРОДНОГО НАУКОВО-ТЕХНІЧНОГО УНІВЕРСИТЕТУ | Безлічі. Способи завдання множин | Операції над множинами | Число елементів безлічі | Властивості бінарних відносин | Операції з бінарними відносинами | Складові висловлювання; таблиці істинності | Логічні закони | Відносини між висловлюваннями |