Перевірка несуперечності вихідних описів кінцевих автоматів

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Ю.М. Вишняков

У 60-70-х роках на теорію кінцевих автоматів (КА), як універсальний інструментарій опису і синтезу цифрових схем, покладалися великі надії. Проте можливості технологічного базису та інформаційні технології того часу обмежили практичне використання теорії КА тільки рамками структурного синтезу. Абстрактний синтез так і залишився предметом теоретичних досліджень. Сьогодні в автоматизованому проектуванні відбувається інтенсивний перехід до інтегрованих інструментальних засобів, що здійснюють наскрізну розробку проектів на всіх рівнях. У таких системах поряд зі стандартними засобами проектування топології та моделювання повинні бути присутнім і засоби реалізація проектних процедур логічного синтезу. Таким чином сьогодні сформовані практичні потреби і є всі умови, щоб абстрактна теорія КА зайняла гідне місце в автоматизованому проектуванні. Проте в цьому плані вона повинна бути перероблена в контексті наскрізного автоматизованого проектування.

У рамках цієї мети пропонована робота розвиває абстрактний синтез в частині побудови несуперечливих описів КА мовою регулярних виразів.

Нехай задані вхідний X = {X1, X2 ,..., Xn} і вихідний Y = {Y1, Y2 ,..., Ym} алфавіти. КА переробляє вхідні слова (ланцюжки) aÎX * у вихідні bÎY * відповідно до алфавітного (автоматним) оператором b = F (a) (А-оператор). Доведено, що оброблювані КА безлічі ланцюжків, відносяться до класу регулярних множин (РМ), які задаються через правила їх породження, звані регулярними виразами (РВ) [1].

В алгебрі РВ за визначенням Æ, l (порожня ланцюжок), X1, X2, ..., Xn є елементарними РВ. Якщо e1, e2, e - РВ, то результати операцій e1 * e2 - (конкатенації), e1 | e2 (АБО), {e} (Кліні), (e) (круглі дужки) також є РВ. Також відзначимо, що породжується безліч ланцюжків або мову РВ e позначають через | e |.

Уявімо А-оператор через систему РВ (СРВ). Для цього виділимо в X * підмножини регулярних ланцюжків E1, E2, ..., Em (у загальному випадку нескінченних) таким чином, щоб ланцюжок aÎE1 приводила до появи на виході КА букви Y1, aÎE2 - букви Y2, aÎEm -. Ym. Для випадку aÎX * (E1 Перевірка несуперечності вихідних описів кінцевих автоматів E2 Перевірка несуперечності вихідних описів кінцевих автоматів ... Перевірка несуперечності вихідних описів кінцевих автоматів Em) визначимо додаткову літеру Ym +1. Також введемо умова несуперечності Ei Перевірка несуперечності вихідних описів кінцевих автоматів Ej = Перевірка несуперечності вихідних описів кінцевих автоматів (I, j = 1 .. m, i ¹ j). Уявімо кожне безліч Ei породжує його регулярним виразом (РВ) ei (| ei | = Ei). Тоді представляє КА система співвідношень виду (1) і називається СРВ:

Перевірка несуперечності вихідних описів кінцевих автоматів (1)

Перевірка несуперечності вихідних описів кінцевих автоматів

Оскільки взаємно однозначна відповідність між мовою і породжує його РВ відсутній (наприклад, РВ а {a} і {a} a породжують різними способами один і той же мова), побудова несуперечливої ​​CРВ вимагає далеко нетривіальних дій. І в цьому зв'язку можна припустити, що кошти дослідження несуперечності СРВ потрібно шукати поза алгебри РВ.

Найближчою моделлю до РВ, якою може бути промодельований розбір ланцюжків, є система переходів (СП), дуги якої зважені літерами вхідного алфавіту. КА з вихідним алфавітом Y = {0,1}, що розпізнає мову | e |, називають кінцевим розпізнавачем (КР). Представлення КР у вигляді діаграми станів (рис.1), в якій початкова вершина S і кінцева вершина Z пов'язані дугою e ​​називається системою переходів (СП). Тут будь-яка ланцюжок aÎ | e | переводить КА зі стану S в стан Z [2].

Перевірка несуперечності вихідних описів кінцевих автоматів

СП елементарних РВ наведені на рис.2. Відповідно до алгеброю РВ СП будь-якого РВ e можна представити у вигляді композиції елементарних СП. Таку СП будемо називати наведеної і позначати через КПС. Введемо на КПС ряд понять.

Визначення 1. Якщо з деякого стану Q виходить l-дуга в стан A1, зі стану A1 в стан A2 і т.д. до стану Т, а зі стану Т немає вихідних l-дуг, то будемо говорити, що стан Q пов'язано зі станом Т лінійним l-шляхом.

Визначення 2. Якщо з деякого стану Q виходить l-дуга в стан А1, а зі стану А1 в стан А2 і т.д. стану Ak, а зі стану Ak в стан Q, то будемо говорити, що стан Q, A1, A2 ,..., Ak входять в один і той же кільцевої l-шлях.

Довжиною l-шляху будемо називати число входять до нього l-дуг.

Визначення 3. Блоком станів (БС) для деякого стану Q БС (Q) назвемо безліч станів, що включають сам стан Q і всі стани, що входять до l-шляху, що виходять з стану Q.

Якщо зі стану Q не виходить l-шляхів, то БС (Q) = {Q}. Надалі БС (Q), що включає більш ніж один стан, будемо позначати l-БС (Q).

Визначення 4. Якщо зі стану Q виходить один або кілька l-шляхів одиничної довжини, то l-БС (Q) назвемо простим, в іншому випадку складеним.

Введемо на СП функцію розбору m, що представляє відображення {БС} Перевірка несуперечності вихідних описів кінцевих автоматів Х ® БС. Її за аналогією з функцією переходів запишемо у вигляді БС = m (БС (Q), xi). Ланцюжок a допускається КА, якщо існує функція розбору виду БС (Zi) = m (БС (S), a), де S - початковий стан, Zi - заключне стан СП КА.

Нехай задана СРВ e1, e2, ..., em і для кожного РВ виконано незалежне побудова КПС. Тут S1, S2, ..., Sm початкові і Z1, Z2, ..., Zm заключні стану відповідних КПС. Введемо наступну перевірочну таблицю (ПТ), на основі якої будемо одночасно будувати функцію розбору для всіх РВ. ПТ містить m +1 стовпець, де 1,2 ,..., m стовпці, відповідають буквам вхідного алфавіту X, а 0-стовпець представляє БС, які іменують рядка. Безліч рядків ПТ розбито на групи, кожна з яких може містити до m рядків по числу РВ, і являє БС для всіх РВ, отриманих на певному етапі побудови функції розбору. У клітку перетину рядка і стовпця записується розрахований значення функції розбору для даного БС і вхідний літери.

Алгоритм перевірки несуперечності СРВ.

1. Побудувати порожню ПТ, сформувати БС (S1), БС (S2 ),..., БС (Sm) і поіменувати ними першу групу рядків;

2. Для всіх букв xi Î X обчислити функцію розбору;

3. Утворити нову групу рядків і поіменувати їх новими БС, отриманими в п.2 і не містять заключних станів Zi.

4. Повторювати п.2 до тих пір, поки не перестануть утворюватися нові БС, не містять заключних станів.

Вихід: СРВ суперечлива, якщо на певному етапі для однієї і тієї ж вхідний букви отримані більш ніж один БС, що містить заключні стану.

В якості прикладу нижче представлені перевіряється на несуперечність СРВ, СП, що входять до неї РВ (рис.4), і відповідна ПТ:

Перевірка несуперечності вихідних описів кінцевих автоматів (2)

Перевірочна таблиця

Перевірка несуперечності вихідних описів кінцевих автоматів

Перевірка несуперечності вихідних описів кінцевих автоматів

Як це видно з побудови ПТ СРВ (2) є несуперечливою.

Отже, пропонована в роботі процедура перевірки на несуперечливість вихідних описів КА, може бути покладена в основу побудови однієї з функціональних частин програмної підсистеми логічного синтезу інтегрованої інструментального середовища САПР. Це дозволить на ранніх етапах проектування виявити коректність вихідного опису об'єкту проектування.

Список літератури

Вавілов Є.М., Кравець Г.П. Синтез схем електронних цифрових машин. М.: Сов.радіо, 1963. 440 з.

Гріс Д. Конструювання компіляторів для цифрових обчислювальних машин. М.: Світ, 1975, 545 с.

Вишняков Ю.М. Інструментарій розробника НВІС. - Таганрог: ТРТУ, 1993. 178 с.


Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
15кб. | скачати


Схожі роботи:
Лісп-реалізація кінцевих автоматів
Закони виключеного третього та несуперечності
Формування вихідних даних
Аналіз вхідних і вихідних грошових потоків підприємства
Перевірка закону Ома для ділянки кола і всього ланцюга Перевірка закону Кірхгофа
Розробка модуля перевірки діапазону вихідних даних і знаходження номера першого символу в рядку
Складання описів справ
Складання архівних описів
Складання архівних описів
© Усі права захищені
написати до нас