Головна

Побудова КА для розпізнання автоматних граматик

  1. А. Побудова кривої виробничих можливостей
  2. А. Визначення характеристик випадкових величин і побудова ліній регресії за даними вибірки
  3. Аксіоматична побудова теорії ймовірностей
  4. Аудиторська вибірка, їх види та побудова
  5. Б) Побудова пропозицій.
  6. Варіаційний ряд і його побудова.
  7. Введення тексту, формул, функцій і побудова графіка.

Будь-яке регулярне безліч, яке розпізнається КА, можна описати за допомогою автоматної граматики. Алгоритм побудови граматики наступний:

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 доп.

Примітка: по самому лівому символу необробленої чіпкий і поточному стану КА відповідно до таблиці переходів виробляється новий стан.

Задана ланцюжок буде допущена побудованим КА-розпізнавачем.

Зміна напрямку рекурсії | Побудова КА-распознавателей для праволінейних граматик


ДОНБАСЬКИЙ ІНСТИТУТ ТЕХНІКИ І МЕНЕДЖМЕНТУ | МІЖНАРОДНОГО НАУКОВО-ТЕХНІЧНОГО УНІВЕРСИТЕТУ | Безлічі. Способи завдання множин | Операції над множинами | Число елементів безлічі | Властивості бінарних відносин | Операції з бінарними відносинами | Складові висловлювання; таблиці істинності | Логічні закони | Відносини між висловлюваннями |

© 2016-2022  um.co.ua - учбові матеріали та реферати