Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування

Теоpема1. Для формальної мови L наступнi умови рiвносильнi:

1) – регулярна мова;

2) iснує такий детермiнований скiнченний автомат A, що L(A) =L;

3) iснує такий недетермiнований скiнченний автомат A, що L(A) = L;

4) мова L породжується деякою праволiнiйною граматикою.

Дов. Рiвносильнiсть 2) ⇔ 3)доведена в теоремi *(Теорема *. Формальна моварозпiзнається НСА тодi i лише тодi, коли вона розпiзнається ДСА).

а iмплiкацiя 1) ⇒ 3) в твердженнi **(Твеpдження **. Кожна регулярна мова розпiзнається деякимнедетермiнованим скiнченним автоматом).

3) ⇒ 1) Покажемо як побудувати регулярний вираз, що позначає мову, яка розпiзнається даним недетермiнованим скiнченним автоматом A. Спершу, ми доведемо цей факт для помiчених графів регулярних виразiв. Помiчений граф G має двi спецiальнi вершини: початкову вершину ν1i кiнцеву вершину νf , i кожна стрiлка графа позначена регулярним

виразом. Для кожного шляху π з вершини ν1 в вершину νf через Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru позначиморегулярний вираз Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , утворений позначкамистрiлок з Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru :

Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru

Далi, для кожного помiченого графа G через L(G) позначимо формальну мову

Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru

Доведемо iндукцiєю за кiлькiстю вершин графа G, вiдмiнних від Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru i Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , що для кожного помiченого графа G формальна мова L(G)є регулярною мовою.

База iндукцiї: Для n = 0 граф G має тiльки двi вершини Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru та Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ,або єдину вершину Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru = Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru . Спершу замiнимо всi паралельнi стрілкиз позначками Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , якi iдуть з вершини υ в вершину ν наодну стрiлку з позначкою Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru :

Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru

Як наслiдок отримаємо один з двох графів:

де a, b, c, d – регулярнi вирази.Очевидно, що для першого графа G регулярна мова L(G) = a∗.

Розглянемо другий граф i шлях π з Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru до Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru . Припустимо, що шлях πпроходить через вершину Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru разiв. Тодi, шлях π можна податияк послiдовнiсть Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , де Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru – це шлях з Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru до Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , а Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru – такi шляхи з Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru до Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , що Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru не є промiжною вершиною в будь-якому з шляхiв Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , 1 ≤ j ≤ k. Очевидно, що r( Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ) = Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru для деякого Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ≥ 0 i, для

j = 2, . . . , k, вираз r( Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ) дорiвнює або c або Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru длядеякого Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ≥ 0, тобто

Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru . Таким чином, для кожногорегулярного виразу r в

Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru iснує такий шлях π в графi G звершини Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru до вершини Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , що r(π) = r. Отже, L(G) = a∗b(c+da∗b)∗i база доведена.

Iндуктивний крок: Для n ≥ 1, оберемо вершину ν, вiдмiнну від Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru та Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , i вилучимо її наступним чином. Спершу, за методом, використаним в базi iндукцiї, вилучимо паралельнi стрiлки. Таким чином,можна вважати, що iснує не бiльше однiєї стрiлки з довiльної вершини υ в довiльну вершину ω. Далi, припустимо, що ν має петлю з

позначкою c. Видалимо вершину ν разом з цiєю петлею. Для довiльної пари (υ, ω) вершин графа G з стрiлками υ Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , видалимо стрiлки υ → ν i ν → ω i замiнимо позначкуd стрiлки υ → ω новою позначкою d + ac∗b (якщо не iснує стрілкиυ → ω в графi G, то вважаємо, що стрiлка υ → ω має позначку ∅).

Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru Дане перетворення показано на рисунку:

Вiдмiтимо,що дане перетворення не змiнює формальної мови L. Таким чином,за iндуктивним припущенням, мова, щорозпiзнається графом G є

регулярною.

Вище доведено, що мови, породженi помiченим графом є регулярними. Наостанок, покажемо, що для довiльногонедетермiнованого скiнченного автомата A формальна мова L(A) є регулярною. Спершу перетворимо автомат A до рiвносильного автомата Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru з єдинимкiнцевим станом f, замiнюючи кiнцевi стани в A на некiнцевi стани, Iдодаючи новий кiнцевий стан i нову кiнцеву e-стрiлку з кожного старого кiнцевого стану до нового кiнцевого стану f. Граф автомата Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru є помiченим графом G, кожна стрiлка якого позначена єдиним символом з множини {e}∪X. Очевидно також, що L(G) = L( Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ). Таким

чином, з доведеного вище випливає, що L( Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ) – регулярна мова.

2) ⇒ 4) Нехай регулярна мова L розпiзнається ДСА (Q,X, δ, q0, F).

Без втрати загальностi, можна вважати, що Q ∩ X = ∅. Побудуємоправолiнiйну граматику G = (N, T, S, P), де N = Q, T = X, S = q0 і P = {q → ap | δ(q, a) = p} ∪ {f → e | f ∈ F}.

Далi, простою iндукцiєю легко довести, що для будь-яких p, q ∈ Q iкожного ω ∈ X,

δ(q, ω) = p тодi i тiльки тодi, коли iснує виведення Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru в граматицi G. Зокрема, ω ∈ L тодi i лише тодi, коли iснуєвиведення q0⇒∗ ωf ⇒ ω для деякого f ∈ F. Звiдси випливає, щоL ⊂ L(G). Бiльше того, оскiльки єдиними правилами в P, якi в правiйчастинi не мiстять нетермiнальних символiв є f → e, де f ∈ F, товищезгаданi виведення є єдиними в граматицi G. Таким чином, L =L(G).

4) ⇒ 3) Нехай G = (N, T, S, P) – праволiнiйна граматика. Побудуємо помiчений орiєнтований граф наступним чином. Множинавершин спiвпадає з N ∪ {f}, де f / ∈ N. Стан S є початковим станом,а f – єдиним кiнцевим станом автомата. Для кожної продукцiї в Gвиду A → ωB, де A,B ∈ N i ω ∈ Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru малюємо стрiлку A Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru B в графi,а для кожної продукцiї вигляду A → ω, де A ∈ N i ω ∈ Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru малюємострiлку A Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru f.

Легко бачити, що кожне виведення S ⇒∗ ω граматики G вiдповiдає шляху графа вiд початкової вершини S до кiнцевої вершини f,позначки якого утворюють слово ω. Таким чином, мова, яка зображується даним помiченим графом, спiвпадає з мовою L(G). Оскiлькикожному такому помiченому орiєнтованому графу вiдповiдає НСА,

який розпiзнає ту ж мову, то мова L(G) є регулярною.Дов.

Твеpдження. Якщо L1 i L2 є регулярними мовами, то L1/L2теж є регулярною мовою.

Дов. Припустимо, що L1 розпiзнається ДСА A = (Q,X, δ, q0, F). Для слова ω ∈ L1/L2 iснує таке слово ν ∈ L2, що δ(q0, ων) = δ(δ(q0, ω), ν) ∈F. Iншими словами, припустимо, що ми аналiзуємо слово ω i переходмио в стан Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru = δ(q0, ω). Якщо iснує таке ν ∈ L2, що

δ( Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , ν) ∈ F, то слово ω розпiзнається, тобто Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru слiд визначити кiнцевим станом автомата для мови L1/L2. Таким чином, визначимо Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ,

i покладемо Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru = (Q,X, δ, q0, Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ). Легко бачити, що Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru розпiзнає мову L1/L2. Дов.

Наслiдок. Клас регулярних мов замкнений вiдносно скiнченних об’єднань, перетинiв, доповнення, рiзницi, симетричної рiзницi, конкатенацiї, iтерацiї та частки.

Лема. (про роздування для регулярних мов)

Нехай L –регулярна мова, тодi iснує така (залежна вiд L) константа s, що кожне слово

ω ∈ L, яке задовольняє нерiвнiсть |ω| ≥ s, можна так розбити на три пiдслова ω = αβγ, що виконуються наступнi умови:

а) |β| ≥ 1; б) |αβ| ≤ s; в) для кожного k ≥ 0 слово Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ∈ L, тобто Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru ⊂ L.

Дов.Нехай L – регулярна мова, тодi згiдно з теоремою 1 iснує ДСА A, який розпiзнає цю мову. Нехай кiлькiсть станiв автомата A дорiвнює s (константа, яка фiгурує в формулюваннi леми). Якщо ω ∈ L, то обчислювальний шлях для слова ω починається в

початковому станi q0 i закiнчується в кiнцевому станi qf . Цей шлях мiстить |ω| стрiлок, оскiльки кожна стрiлка позначена єдиною буквою слова ω. Таким чином, вiн мiстить послiдовнiсть з |ω|+1 станiв. Оскiльки |ω| ≥ s, то деякий стан в обчислювальному шляху, згiдно принципу Дiрiхле, обов’язково повториться двiчi. Нехай Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru –перший повторюваний стан при аналiзi слова ω.

Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru

Позначимо через β ту частину слова ω, яка складається з букв, якi позначають стрiлки пiдшляху вiд першого входження стану Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru до другого входження стану Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru = Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru в обчислювальний шлях слова ω.Позначимо через α частину слова ω перед β, а через γ – його частину пiсля β. Очевидно, що |β| ≥ 1 та |αβ| ≤ s (оскiльки всi стани до другої появи Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru рiзнi). Бiльше того, слово αβkγ для будь-якого цілого невiд’ємного числа k має переводити автомат у той самий заключний стан, що й слово αβγ. Справдi, частина Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru слова Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru просто переводить стани автомата A вздовж петлi, яка починається та закiнчується в станi Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru . Ця петля проходить k разiв. Звiдси випливає, що автомат A розпiзнає слова Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування - student2.ru , оскiльки вiн розпiзнає слово αβγ.

Тому всi такi слова належать мовi L. Дов.

Наши рекомендации