Формальні мови та автомати В.Ковтунець Математична логіка і формальні системи

Конкатенація множин Означення. Нехай V – алфавіт, A та B – підмножини множини V *. Конкатенацією множина А та В називається множина АВ, яка складається з усіх ланцюжків виду αβ, де α належить А, а β належить В. Приклад. A={01, 11}, B={1, 10, 110}. AB={01, 11, 011, 0110, 01110, 111, 1110, 11110, 1, 10, 110}. AB BA, взагалі кажучи.

Конктенація кількох примірників множини (степінь множини) Означення. Для заданої мнжини ланцюжків A степінь множини визначається рекурсивно: A 0 ={λ} ( множина, що містить лише порожній ланцюжок) A n+1 =A n A, n= 0, 1, 2, …. Приклад. A={1,10} A 2 ={11, 110, 101,1010}, A 3 ={111,1110,1101, 11010, 1011, 10110, 10101, }

Замикання Кліні множини ланцюжків Приклад. А = {0}. A*= {0, 00, 000, ….}.

Поняття регулярної множини. Регулярний вираз над множиною I. Означення. - регулярний вираз λ - регулярний вираз Символ x із І є регулярним виразом Якщо А та В регулярні, то регулярними є вирази (АВ), (А В), А *.

Поняття регулярної множини. Означення. Множина, задана регулярним виразом, тобто, множина ланцюжків, визначена за такими правилами: - регулярна; {λ} - регулярна; {x} – регулярна; якщо вирази А та В регулярні, то регулярними є множини (АВ), (А В), А * - називається регулярною.

Приклади регулярних множин 1.Вираз 10* породжує множину ланцюжків, кожен з яких містить 1 та послідовність нулів. 2. Вираз (10)* породжує множину ланцюжків, кожен з яких містить довільну кількість повторень пари Вираз 0 01 породжує множину із двох ланцюжків 0 та Вираз 0(0 1)* породжує множину довільних ланцюжків, що починаються з Вираз (0*1)* породжує множину довільних ланцюжків, що закінчуються одиницею.

Теорема Кліні (1956 рік) Множина розпізнається деяким скінченним автоматом тоді і лише тоді, коли вона регулярна.

Теореми. Теорема 1. Регулярна граматика породжує лише регулярну множину. Теорема 2. Для того, щоб мова була регулярною, необхідно і достатньо, щоб вона розпізнавалась скінченним атоматом.

Типи граматик. Ієрархія Хомскі (N.Chomsky) Тип граматики Обмеження на продукції 0Без обмежень 1, або = 2 =A (нетермінальний символ) 3 =A, =aB або =a, або S

Регулярні граматики Означення. Граматика типу 3, тобто, всі продукції якої виводяться лише з нетермінальних символів, і при цьому виводяться лише ланцюжки вигляду =aB або =a, або порожній, називається регулярною граматикою. Приклади 4 та 5.

Скінченні автомати з магазинною памюттю Означення. Скінченним автоматом називається система із обєктів M=(S,I,Г,F,f, m,s 0,z 0 ), де S - множина станів I – вхідний алфавіт Г – алфавіт для памяті F S – множина заключних (приймаючих) станів f: S x I х Г S - функція переходів m: S x I х Г Г * - функція зміни памяті s 0 - початковий стан z 0 – початковий символ в магазині

Прицип роботи магазинної памяті (стек!) Якщо в магазині записано рядок aα (a – символ), і m(s i,x,a)=β (рядок), то результатом здійснення кроку автомата буде вміст магазину βα. a α β α

Приклад автомата з магазинною памяттю S={s 0, s 1, s 2 }, I={0,1}, Г={0,z}, F={s 0 }. f(s 0,0,z)=s 1, m(s 0,0,z)=0z; f(s 1,0,0)=s 1, m(s 1,0,0)=00; f(s 1,1,0)=s 2, m(s 1,1,0)=λ; f(s 2,1,0)=s 2, m(s 2,1,0)=λ; f(s 2, λ,z)=s 0, m(f(s 2, λ,z)=λ/ Автомат розпізнає мову L={0 m 1 m, m=0,1, 2,…}.

Теорема Граматика є контекстно вільною тоді і лише тоді, коли породжена нею мова розпізнається автоматом з магазинною памяттю.