операції об'єднання мов ми знаємо. Визначимо операції конкатенації та ітерації (іноді її називають замиканням Клині).

Нехай L 1 та L 2 - мови в алфавіті

Тоді, тобто. конкатенація мовскладається з конкатенацій всіх слів першої мови з усіма словами другої мови. Зокрема, якщо , то , а якщо , то .

Введемо позначення для "ступеня" мови L :

Таким чином в L i входять усі слова, які можна розбити на i поспіль слів, що йдуть з L .

Ітерацію (L) * мови L утворюють всі слова які можна розбити на кілька поспіль слів, що йдуть з L :

Її можна уявити за допомогою ступенів:

Часто зручно розглядати "усічену" ітерацію мови, яка не містить порожнього слова, якщо його немає в мові: . Це не нова операція, а просто зручне скорочення для вираження.

Відзначимо також, що якщо розглядати алфавіт як кінцеву мову, що складається з однолітерних слів, то введене раніше позначення для багатьох слів, включаючи і порожнє, в алфавіті відповідає визначенню ітерації цієї мови.

У наступній таблиці наведено формальне індуктивне визначення регулярних виразівнад алфавітом і ними мов.

Вираз r	Мова L r
	L a = (a)
Нехай r 1 і r 2 це	L r1 і L r2 - представлені
Регулярні вирази.	ними мови.
Тоді такі висловлювання
є регулярними	і репрезентують мови:
r=(r 1 +r 2)
r=(r 1 circr 2)
r=(r 1) *	L r = L r1 *

При записі регулярних виразівбудемо опускати знак конкатенації і вважатимемо, що операція має більший пріоритет, ніж конкатенація і + , а конкатенація - більший пріоритет, ніж + . Це дозволить опустити багато дужок. Наприклад, можна записати як 10 (1 * + 0).

Визначення 5.1. Два регулярні вирази r і p називаються еквівалентними, якщо збігаються їх мови, тобто. L r = L p. У цьому випадку пишемо r = p.

Неважко перевірити, наприклад, такі властивості регулярнихоперацій:

• r + p = p + r (комутативність об'єднання),
• (r+p) +q = r + (p+q) (асоціативність об'єднання),
• (r p) q = r (p q) (асоціативність конкатенації),
• (r *) * = r * (ідемпотентність ітерації),
• (r + p) q = rq + pq(Дистрибутивність).

Приклад 5.1. Доведемо як приклад менш очевидна рівність : (r + p) * = (r * p *) * .

Нехай L 1 - мова, що подається його лівою частиною, а L 2 - правою. Порожнє слово належить обом мовам. Якщо непусте слово, то за визначенням ітерації воно представне як конкатенація підслів, що належать мові. Але ця мова є підмножиною мови L" = L r * L p * (чому?). . Назад, якщо слово , воно представимо як конкатенація підслів, що належать мові L " . Кожне з таких підслів v представимо як v = v 1 1 ... v k 1 v 1 2 ... v l 2, де всім i=1, ... , k підслів і всім j=1, ... , l підслів (можливо, що k чи l дорівнює 0). Але це означає, що w є конкатенацією підслів, кожне з яких належить і, отже, .

Регулярні множинита регулярні вирази

Регулярні множини

У цьому розділі ми розглянемо клас множин ланцюжків над кінцевим словником, які дуже легко описати формулами певного виду. Ці множини називаються регулярними.

Визначення 1.Нехай V 1 і V 2 - безлічі ланцюжків. Визначимо три операціїна цих множинах.

Об'єднання: V 1 V 2 =(|   V 1 ) або   V 2 .

Конкатенація (твір, склеювання): Vl  V2 = (|  V 1 ,  V 2 ) Знак операції конкатенації зазвичай опускається.

Приклад: V, = (abc, ba), V2 = (b, cb). V1V2 = (abcb, abccb, bab, bacb).

Позначимо V n добуток n множин V:V n =VV...V,V° =() (тут -порожній ланцюжок).

Приклад: V1 = (abc, ba), V12 = (abcabc, abcba, baba, baabc).

3. Ітерація: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

Приклад: V = (a, bc), V * = (, a, bc, aa, abc, bcbc, bca, aaa, aabc,...).

Визначення 4.13.Клас регулярних множин над кінцевим словником V визнайтеється так:

об'єднання ST;

конкатенація ST;

ітерація S* та Т*.

5. Якщо безліч може бути побудовано кінцевим числом застосування правил 1-4, воно нерегулярно.

Приклади регулярних множин: (ab, ba) * (aa); (b)((c)(d, ab)*). Приклади нерегулярних множин: (a n b n | n > 0); ( | у ланцюжку  кількості входжень символів а і b збігаються).

Регулярні вирази

Регулярні множини хороші тим, що їх можна дуже просто описати формулами, які ми назвемо регулярними виразами.

Визначення 2.Клас регулярних виразів над кінцевим словником V визнайтеється так:

їхня сума R1+R2;

їх добуток R1R2;

їх ітерація R1 і R2.

4. Якщо вираз не побудовано кінцевим числом застосування правил 1-3, воно не є регулярним.

Знак твору можна опускати. Для зменшення числа дужок, як і в будь-якій алгебрі, використовуються пріоритети операцій: ітерація найпріоритетніша; менш пріоритетний твір; найнижчий пріоритет у складання.

Приклади регулярних виразів: ab+ba*; (аа) * b + (з + dab) *.

Вочевидь, що регулярні множини і регулярні висловлювання дуже близькі. Але вони являють собою різні сутності: регулярне безліч - це безліч ланцюжків (загалом нескінченне), а регулярний вираз - цеформула, схематично показує, як було побудовано відповідне їй регулярне безліч за допомогою перерахованих вище операцій(і ця формула є кінцевою).

Нехай R^ - регулярна множина, що відповідає регулярному виразу R. Тоді:

Таким чином, регулярне вираз - це кінцева формула, що задає безліч ланцюжків, тобто мову.

Розглянемо приклади регулярних виразів та відповідних їм мов.

Регулярний вираз	Відповідна мова
	Усі ланцюжки, що починаються з b, за яким слідує довільна кількість символів а
	Всі ланцюжки а і b, що містять рівно два входження b
	Всі ланцюжки з а і b, до яких символи входять лише парами
(a+b)*(aa+bb)(a+b)*	Всі ланцюжки з а і b, що містять хоча б одну пару, що поряд стоять а або b
(0+1)*11001(0+1)*	Усі ланцюжки з 0 і 1, що містять підчіпку 11001
	Усі ланцюжки з а та b, що починаються символом а та закінчуються символом b

Очевидно, що безліч ланцюжків регулярно тоді і тільки тоді, коли вона може бути представлена ​​регулярним виразом. Однак те саме безліч ланцюжків може бути представлено різними регулярними виразами, наприклад, безліч ланцюжків, що складається з символів а і містить не менше двох а може бути представлено виразами: аа * а; а*ааа*; ааа*; а*аа*аа* і т.д.

Визначення 3.Два регулярні вирази R1 і R2 називаються еквівалентними (позначається Rl = R2) тоді і лише тоді, колиR1 ^ = R2 ^ .

Отже, аа*а = а*ааа* = ааа* = а*аа*аа*. Виникає питання, як визначити еквівалентність двох регулярних виразів.

Теорема1 . Для будь-яких регулярних виразів R, S іТ справедливо:

Ці співвідношення можна довести, перевіряючи рівність відповідних множин ланцюжків. Їх можна використовувати для спрощення регулярних виразів. Наприклад: b (b + aa * b) = b (b + aa * b) = b (b + aa *) b = ba * b. Звідси b (b + aa * b) = ba * b, що очевидно.

Теорема Кліні

Регулярні вирази – це кінцеві формули, що задають регулярні мови. Але таку ж властивість мають і кінцеві автомати - вони теж задають мови. Виникає питання: як співвідносяться між собою класи мов, що задаються кінцевими автоматами та регулярними виразами? Позначимо А безліч автоматних мов, R – безліч регулярних мов. Стефен Кліні, американський математик, довів таку теорему.

Теорема2 . (Теорема Кліні.) Класи регулярних множин та автоматних мов збігаються, тобто А = R .

Іншими словами, кожна автоматна мова може бути задана формулою (регулярним виразом) і кожна регулярна множина може бути розпізнана кінцевим автоматом. Ми доведемо цю теорему конструктивно, за два кроки. На першому кроці доведемо, що будь-яка автоматна мова є регулярною безліччю (або, що те саме, для будь-якого кінцевого автомата можна побудувати регулярне вираз, що задає мову, що розпізнається цим автоматом). На другому кроці доведемо, що будь-яка регулярна множина є автоматною мовою (або, що те саме, за будь-яким регулярним виразом можна побудувати кінцевий автомат, що допускає в точності ланцюжка відповідної регулярної множини).

Введемо на розгляд модель графа переходів як узагальнення моделі кінцевого автомата. У графі переходів одна початкова і довільна кількість заключних вершин, а спрямовані ребра позначені, на відміну кінцевого автомата, не символами, а регулярними висловлюваннями. Граф переходів допускає ланцюжок а, якщо аналежить безлічі ланцюжків, що описується добутком регулярних виразів R 1 R 2 ...R n , Які позначають шлях з початкової вершини в одну із заключних вершин. Безліч ланцюжків, що допускаються графом переходів, утворює мова, що допускається ним.

Мал. 1. Граф переходів

На рис. 1 зображено граф переходів, який допускає, наприклад, ланцюжок abbca, оскільки шлях s->r->p->s->r->q, який веде в заключний стан q, позначений ланцюжком регулярних виразів.   c * а. Кінцевий автомат є окремим випадком графа переходів і тому всі мови, що допускаються автоматами, допускаються і графами переходів.

Теорема 3.Кожна автоматна мова є регулярним безліччю, А  R.

Доведення. Граф переходів з однією початковою та однією заключною вершинами, у якого єдине ребро з початкової в заключну вершину позначено регулярним виразом R, допускає мову R^ (рис. 1).

Мал. 2. Граф переходів, що припускає регулярну мову FT

Доведемо тепер, що кожна автоматна мова є регулярним безліччю приведенням будь-якого графа переходів без зміни мови до еквівалентного виду (рис. 2).

Будь-який кінцевий автомат і будь-який граф переходів завжди можна уявити в нормалізованій формі, в якій тільки одна початкова вершина тільки з вихідними ребрами і тільки одна заключна вершина тільки з ребрами, що входять (рис. 3).

Мал. 3. Граф переходів з однією початковою та однією заключною вершинами

З графом переходів, представленим у нормалізованій формі, можуть бути виконані дві операції редукції - редукція ребра та редукція вершини - зі збереженням допустимої цим графом переходів мови:

а) редукція ребра:

Б ) редукція вершини (заміна виконується для кожного шляху, що проходить через вершину р, з подальшим її викиданням як недосяжний стан):

Вочевидь, кожна операція редукції не змінює мови, розпізнаваного графом переходів, але зменшує чи кількість ребер, чи кількість вершин, і зрештою редукції приведуть граф переходів до виду, наведеному на рис. 2. Теорема доведена: кожна автоматна мова є регулярною безліччю.

приклад

Нехай заданий кінцевий автомат А:

Будуємо еквівалентний граф переходів у нормалізованому вигляді.

Редукція вершини 3:

Редукція дуг та застосування правила R = R:

Редукція вершини 2:

Редукція дуги та вершини 1:

Таким чином, мова, що розпізнається автоматом А, задається регулярним виразом: RA = b+(a+bb)(b+ab)*a.

Доведемо теорему Кліні в інший бік.

Теорема 2.Кожна регулярна множина є автоматною мовою: R  A.

Доведення.Покажемо, що для кожного регулярного виразу R може бути побудований кінцевий автомат A r (можливо недетермінований), що розпізнає мову, що задається R. Визначення таких автоматів дамо рекурсивно.

(Початковий та заключний стан А поєднуються).

приклад(продовження)

Теорія автоматів - це розділ теорії керуючих систем, що вивчає математичні моделі перетворювачів дискретної інформації. автоматами. З певної точки зору такими перетворювачами є як реальні пристрої (обчислювальні машини, автомати, живі організми тощо), так і абстрактні системи (наприклад, формальна система, аксіоматичні теорії тощо), завдяки чому можливе застосування теорії автоматів у різних наукових та прикладних дослідженнях. Найбільш тісно теорія автоматів пов'язана з математичною логікою та теорією алгоритмів. Зокрема, засобами теорії автоматів доводиться роздільна здатність деяких формальних обчислень.

Ще одним найважливішим об'єктом вивчення в даному курсі є формальна мова 1 - Довільна безліч слів деякого алфавіту. Важливість формальних мов для теоретичної інформатики обумовлена ​​тим, що найбільш простою та зручною моделлю даних, що використовуються в комп'ютерних програмах, є кінцева послідовність, кожен елемент якої взятий з деякої заздалегідь зафіксованої кінцевої множини. Оскільки формальні мови, що використовуються в додатках, як правило, є нескінченними, то потрібен спосіб кінцевого опису формальної мови. В даному курсі вивчатимемо 3 класичні засоби такого опису: автомати, Регулярні виразиі породжувальні граматики.

Вступ

1. Початкові поняття теорії формальних мов

Розглянемо непусту кінцеву множину А, що складається із символів ( a 1 , …, a k). Будемо називати А алфавітом , а його символи – літерами . Будь-яка кінцева послідовність літер цього алфавіту називається словом (ланцюжком або рядком ): w=a 1 a 2 …a n- Слово ( a i A), |w| - Довжина слова (число букв, з яких складається слово, причому кожен символ зустрічається стільки разів, скільки разів він зустрічається в w). Через | w| bпозначимо кількість входжень символу bу слово w.

Нескінченна послідовність букв алфавіту Аназивається надсловом , - надслово з нескінченного числа букв а. Порожнім називається слово, що не містить жодної літери. Воно позначається через . Вочевидь, ||=0.

- безліч слів алфавіту Адовжини n. Безліч всіх слів алфавіту А(включаючи надслова) позначається А*. Це безліч лічильне, оскільки є об'єднанням лічильного числа кінцевих множин
. Безліч пустих слів в алфавіті Апозначається А+. Якщо A={a), то А*={a)* будемо позначати через а*.

Будь-яке підмножина
називається мовою (формальною мовою ) над алфавітом А.

Якщо xі y- Слова мови
, то слово ху(Результат приписування слова унаприкінці слова х) називається конкатенацією (зчепленням , твором ) слів хі у.
(nраз беремо х). Покладемо
.

Говорять, що слово х – підслів слова у, якщо y=uxvдля деяких слів uі v. Усі підслівні слова мови
утворюють безліч підслів мови L, Що позначається через Subw( L).

Приклади. 1. ba 3 =baaa,
- у цьому слові є підслів ab, aba, baі т.п.

2. Безліч ( a, abb) - мова (кінцева) над алфавітом ( a, b}.

3. Безліч
є мовою над алфавітом ( a, b). Ця мова нескінченна, вона містить слова b, ba, aba, baa, abaa, baaa, aabaa, abaaaі т.д.

Оскільки кожна мова є безліччю, можна розглядати операції об'єднання, перетину та різниці мов, заданих над тим самим алфавітом. Так, мова
, де
, називається доповненням мови Lщодо алфавіту А. І якщо  завжди включено до А*, то мова
може як утримувати, так і не утримувати його. В останньому випадку
.

Нехай ,
. Тоді мова називається конкатенацією (зчепленням , твором ) мов і . При цьому
,
(nраз), якщо n>0.

Приклади. 1. Якщо
,
,то .

2. Якщо L = (0, 01), то
.

Ітерацією мови Lназивається мова
(Ця операція називається також зірочкою Кліні ). Мова
називається позитивною ітерацією мови L.

приклад. Якщо A={a, b) та L={aa, ab, ba, bb), то
.

Зверненням або дзеркальним чином слова wназивається слово w R, в якому букви слова wйдуть у зворотному порядку. Наприклад, якщо w=bac, то

Нехай
. Тоді мова
називається зверненням мови L.

Будь-який початок слова будемо називати префіксом , а всякий кінець слова – суфіксом . Наприклад, якщо y=xv, то х- Префікс слова у(позначення – х[y), а v- Суфікс слова у(позначення – v]y). Очевидно, що порожнє слово є префіксом, так і суфіксом будь-якого слова. Усі префікси слів мови
формують безліч префіксів цієї мови: Pref( L)
. АналогічноSuf( L)
-м ножство суфіксів мови
.

Якщо мова Lтакий, що жодне слово Lне є префіксом (суфіксом) жодного іншого слова L, то кажуть, що Lмає префіксним (Суфіксним) властивістю .

Нехай А 1 та А 2 – алфавіти. Якщо відображення f:
задовольняє умову всім слів
і
, то відображення fназивається гомоморфізмом .

Зауваження. 1. Можна довести, що якщо f- гомоморфізм, то
.

2. Гомоморфізми не завжди є бієкціями, але кожен гомоморфізм однозначно визначається своїми значеннями на однолітерних словах.

3. Застосовуючи гомоморфізм до мови L, отримуємо іншу мову f(L).

Якщо f:
- Гомоморфізм,
і
, то через f(L 1) позначається мова
, а через
позначається мова
, а саме відображення
називається зверненням гомоморфізму .

Приклади. 1. Допустимо, ми хочемо замінити кожне входження в ланцюжок символу 0 на символ а, а кожне входження 1 – на bb. Тоді можна визначити гомоморфізм fтак що
і
. Якщо
, то
.

2. Нехай f– гомоморфізм, для якого
і
. Тоді
і
.

У цьому розділі ми починаємо викладення елементів теорії формальних мов.

Говорячи " формальний мову " , маємо у вигляді те, що наведені тут результати використовуються передусім описі штучних мов, придуманих людьми для спеціальних цілей, наприклад мов програмування. Але непереборної перешкоди між спеціально придуманими штучними (формальними) мовами і природними мовами, що стихійно виникають і розвиваються, не існує. Виявляється, що природні мови характеризуються складними граматичними правилами, тобто. досить жорстко формалізовані, а навіть "науково розроблена" мова програмування містить "темні місця", однозначне розуміння яких є проблемою.

Вивчаючи мови, слід мати на увазі три основні аспекти.

Перший з них - синтаксис мови . Мова - це якась безліч "слів", де "слово" є певна кінцева послідовність "літер" - символів якогось заздалегідь фіксованого алфавіту. Терміни "літера" та "слово" можуть розумітися по-різному (математичне визначення цих термінів буде дано нижче). Так, "літерами" можуть бути дійсно літери алфавіту якоїсь природної або формальної мови, наприклад, російської мови або мови програмування "Паскаль". Тоді "словами" будуть кінцеві послідовності "літер": крокодил", " integer". Такі слова називають "лексемами". Але "літерою" може бути "слово" ("лексема") в цілому. Тоді "слова" - це пропозиції природної мови або програми мови програмування. Якщо фіксована якась безліч "літер", то не кожна їхня послідовність буде "словом", тобто Елексемою даної мови, а тільки така послідовність, яка підпорядковується певним правилам. Слово "крикаділ" не є лексемою російської мови, а слово "iff" не є лексемою в "Паскалі". Пропозиція "Я люблю ти" не є правильною пропозицією російської мови, так само, як і запис "х:= =t" не є правильно написаний оператор присвоювання "Паскаля". Синтаксис* мови і є системою правил, відповідно до якими можна будувати "правильні" послідовності "літер". Кожне слово мови характеризується певною структурою, специфічною саме цієї мови. Тоді необхідно, з одного боку, розробити механізми перерахування, або породження, слів із заданою структурою, а з іншого - механізми перевірки того, що це слово належить цій мові. Насамперед саме: ці механізми і вивчає класична теорія формальних мов.

Другий аспект - семантика мови . Семантика** передбачає зіставлення словами мови якогось "сенсу", Езначення". Наприклад, записуючи математичну формулу, ми повинні дотримуватися певних синтаксичних правил (розстановка дужок, правопис символів, порядок символів і т.п.), але, крім цього, формула має цілком певний сенс щось позначає.

Мова – це засіб спілкування, передачі інформації. Якщо ми хочемо, щоб нас зрозуміли, ми повинні не тільки синтаксично правильно, дотримуючись належного порядку букв у слові та слів у реченні, будувати свою мову, а й дбати про її зміст, про ті ідеї, які ми висловлюємо у мові. Математичні теорії "сенсу" з'явилися порівняно недавно, і на додаток до наступного розділу ми дуже коротко розглянемо деякі підходи до математичного опису семантики мов програмування.

* Слово "синтаксис" походить від давньогрецьких "syn" - "разом" та "taxis" - "порядок, лад". Таким чином, синтаксис можна розуміти як "складання".

** Від давньогрецьких слів "sema" - "знак, знак" і "semanticos" - "що позначає".

Нарешті, третій аспект - прагматика мови . Прагматика пов'язана з тими цілями, які ставить перед собою носій мови: наприклад, людина вимовляє мову, маючи перед собою цілі, пов'язані не з синтаксисом, не з семантикою мови, якою вона говорить або пише, а, скажімо, з отриманням за певну мову суми грошей. Прагматика є вже скоріше дисципліною соціально-філософської, що зачіпає цілу діяльність особистості. Ми ні в якому разі не будемо її торкатися.

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

• Алфавіт, слово, мова

• Граматики, що породжують

  Як зазначалося, класична теорія формальних мов вивчає передусім синтаксис мови. Вона вводить математичну модель синтаксису, яка описує механізми породження та розпізнавання "правильно побудованих" ланцюжків. У цьому розділі ми розглянемо перший із цих механізмів.

Лабораторна робота №3

Розробка лексичного аналізатора виконується досить легко, якщо використовується теорія регулярних мов та кінцевих автоматів. Рамки цієї теорії класи однотипних лексем розглядаються як формальні мови (мова ідентифікаторів, мова констант і т.д.), безліч пропозицій яких описується за допомогою відповідної граматики, що породжує. При цьому ці мови настільки прості, що вони породжуються найпростішою з граматик – регулярною граматикою.

Визначення 1. породжувальна граматика G = , правила якої мають вигляд: А::=аВ або С::=b де А, В,С Є N; a, b Є Т називається регулярною (автоматною).

Мова L (G), що породжується автоматною граматикою, називається автоматною (регулярною) мовою або мовою з кінцевим числом станів.

Приклад 1. Клас ідентифікаторів, якщо ідентифікатором є послідовність, що складається з букв і цифр, і першим символом ідентифікатора може бути тільки буква, описується наступною регулярною граматикою, що породжує G = , в якій

N = (I, K), T = (б, ц), S = (I),

P = (1. I::= б

Тут б, ц – узагальнені термінальні символи для позначення букв та цифр відповідно.

Процес породження ідентифікатора «ббцбц» описується наступною послідовністю підстановок

I => бК => ббК => ббцК => ббцбК => ббцбц

Проте основним завданням ЛА не породження лексичних одиниць, які розпізнавання. Математичною моделлю процесу розпізнавання регулярної мови є обчислювальний пристрій, який називається кінцевим автоматом (КА). Термін «кінцевий» підкреслює те, що обчислювальний пристрій має фіксований та кінцевий об'єм пам'яті та обробляє послідовність вхідних символів, що належать певній кінцевій множині. Існують різні типи КА, якщо функцією виходу КА (результатом роботи) є лише вказівка ​​на те, чи допустима вхідна послідовність символів, такий КА називають кінцевим розпізнавачем.

Визначення 2. Кінцевим автоматом називається наступна п'ятірка:

А = , де V = (a 1 , a 2 , …, a m ) - Вхідний алфавіт (кінцева безліч символів);

Q = (q 0 , q 1 , …, q n -1 ) - Алфавіт станів (кінцева безліч символів);

δ: Q × V → Q – функція переходів;

q 0 Є Q – початковий стан кінцевого автомата;

F Є Q – безліч останніх станів.

Схема функціонування КА.

Є нескінченна стрічка, розбита на комірки, у кожному з яких може бути один символ з V. На стрічці записано ланцюжок α Є V*. Осередки ліворуч і праворуч від ланцюжка не заповнені. Є кінцевий пристрій управління (УУ) з головкою, що читає, яке може послідовно зчитувати символи зі стрічки, пересуваючись вздовж стрічки зліва направо. При цьому, УУ може перебувати в якомусь одному стані з Q. Починає свою роботу УУ завжди в початковому стані q 0 , а завершує в одному із заключних станів F. Щоразу, переходячи до нового осередку на стрічці, УУ переходить у новий стан відповідно до функції δ.

Функцію переходів КА можна надати такими способами:

· Сукупність команд;

· Діаграма станів;

· Таблиця переходів.

Команда кінцевого автомата записується так:

(q i , a j) → q k , де q i , q k Є Q; a j Є V.

Ця команда означає, що кінцевий автомат перебуває у стані q i , читає зі стрічки символ а j і перетворюється на стан q k .

Графічно команда представляється у вигляді дуги графа, що йде з вершини q i у вершину q k та позначеної символом a j вхідного алфавіту:

Графічне уявлення всього відображення називають діаграмою станів кінцевого автомата.

Якщо КА виявляється у ситуації (q i , a j), яка є лівою частиною будь-якої команди, він зупиняється. Якщо УУ вважає всі символи ланцюжка α, записаної на стрічці, і при цьому перейде в заключний стан q r Є F, то кажуть, що ланцюжок α допускається кінцевим автоматом.

Таблиця переходів КА будується так: стовпці матриці відповідають символам з вхідного алфавіту, рядки – символам з алфавіту станів, а елементи матриці відповідають станам, у яких переходить КА даної комбінації вхідного символу та символу стану.

Нехай задана регулярна граматика G = , правила якої мають вигляд: А i::= a j A k або А i::= a j , де А i , A k Є N і a j Є Т.

Тоді кінцевий автомат А = , що допускає ту ж мову, що породжує регулярна граматика G, будується таким чином:

2) Q = N U (Z), Z N та Z T, Z – заключний стан КА;

5) Відображення δ будується у вигляді:

· Кожному правилу підстановки в граматиці G виду А i::= a j A k ставиться у відповідність команда (A i , a j) → A k ;

· Кожному правилу підстановки виду А i:: = a j ставиться у відповідність команда (A i, a j) → Z;

приклад 2.Побудувати КА для граматики із прикладу 1. Маємо А = , де

1) V = T = (б, ц)

2) Q = N U (Z) = (I, R, Z)

3) q 0 = (S) = (I)

5) δ: a) у вигляді сукупності команд:

б) як діаграми станів

Розрізняють детерміновані та недетерміновані кінцеві автомати. КА називається недетермінованимКА (НКА), якщо діаграмі його станів з однієї вершини виходить кілька дуг з однаковими позначками. Наприклад, КА із прикладу 2 є НКА.

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

Z – «допустити вхідний ланцюжок»;

О – «запам'ятана помилка у вхідному ланцюжку»;

Е – «відкинути вхідний ланцюжок».

Стани Z та Е є заключними, і в них КА переходить при прочитанні кінцевого маркера відповідно після обробки правильного або помилкового вхідного ланцюжка. Стан є проміжним, в нього КА переходить з будь-якого допустимого стану КА при виявленні помилки у вхідному ланцюжку і залишається в ньому до надходження кінцевого маркера ├, після чого здійснюється перехід в стан Е - «відкинути вхідний ланцюжок».