АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Зредагуйте вирази. Поясніть.
  2. Порівняйте вирази в наступних парах і спробуйте визначити, в яких випадках
  3. Поставте слова, наведені в дужках, у формі множини. Перекладіть речення.
  4. Принцип замикання множини атрибутів
  5. Синтаксичний аналіз у ручному режимі двох прикладів операторів підмножини мови SQL варіантом як спадним, так і висхідним методами.
  6. Сталі вирази з дієсловами to be і to have

Означення: Нехай S - скінчений алфавіт. Регулярна множина в алфавіті S визначається рекурсивно:

П1. Æ - пуста множина – це регулярна множина в алфавіті S;

П2. {e} – пусте слово – регулярна множина в алфавіті S;

П3. {a} – однолітерна множина – регулярна множина в алфавіті S;

П4. Якщо P та Q – регулярні множини, то такими є наступні множини:

P È Q (операція об’єднання);

P * Q (операція конкатенації);

{P} = {e} È P È P*P È ……. (операція ітерації).

П5. Ніякі інші множини, окрім побудованих на основі ПП 1-4 не є регулярними множинами.

Таким чином, регулярні множини можна побудувати з базових елементів ПП 1-3 шляхом скінченого застосування операцій об’єднання, конкатенації та ітерації.

Регулярні вирази позначають регулярні множини таким чином, що:

П1. 0 позначає регулярну множину Æ;

П2. e позначає регулярну множину {e};

П3. а позначає регулярну множину {a};

П4. Якщо p та q позначають відповідно регулярні множини P та Q, то

p + q позначає регулярну множину P È Q;

p . p позначає регулярну множину P * Q;

p* позначає регулярну множину {P}.

П5. Ніякі інші вирази, окрім побудованих на основі ПП 1-4 не є регулярними виразами.

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

1) a + b = b + a; 7) a + b + c = a + (b + c);

2) ae = ea = a; 8) a + b + c = (a + b) + c;

3) a0 = 0a = 0; 9) p + p* = p*;

4) a(b + c) = ab + ac; 10) 0* = e;

5) (a + b)c = ac + bc; 11) e* = e.

6) a + a = a;

По аналогії з класичними алгебрами розглянемо лінійне рівняння в алгебрі регулярних виразів:

X = aX + b, де a, b – регулярні вирази.

Взагалі таке рівняння в залежності від a та b може мати безліч розв’язків, наприклад: X = a*(b + g), при умові, що a позначає e-ланцюжок. Тоді g може бути навіть і нерегулярним виразом. Серед всіляких розв’язків рівняння з регулярними коефіцієнтами виберемо найменший розв’язок X = a*b, який назвемо найменша нерухома точка. Щоб перевірити, що a*b розв’язок рівняння в алгебрі регулярних виразів, підставимо його в початкове рівняння та перевіримо тотожність виразів на основі системи тотожних перетворень:

a*b = aa*b+b = (aa*+e)b = (a (e + a +aa+…) + e)b = (e + a + aa +…)b = a*b

В алгебрі регулярних виразів також розглядають і системи лінійних рівнянь з регулярними коефіцієнтами:

X1 = a11X1 + a12X2+ … + a1nXn + b1

X2 = a21X1 + a22X2+ … + a2nXn + b2

………………..

Xn = a1nX1 + a2nX2 + … + annXn + bn

де aij, bi, i,j = 1..n.

Метод розв’язку системи лінійних рівнянь з регулярними коефіцієнтами нагадує метод виключення Гауса.

П1. Покласти i = 1.

П2. Якщо i рівне n, то перейти на П4. Інакше і–е рівняння, використавши систему тотожних перетворень, записати у вигляді:

Xi = aXi + b, де a - регулярний вираз в алфавіті S, а b – регулярний вираз виду b0 + bi+1Xi+1 + bi+2Xi+2 + … bnXn, де bk (k=0, i+1,.. n) - регулярні коефіцієнти. Далі, в правих частинах рівнянь зі змінними Xi+1, Xi+2, … Xn в лівій частині рівняння підставити заміст Xi значення a*b.

П3. Збільшити i на 1 та перейти на П2.

П4. Записати рівняння Xn = aXn + b, де a, b – регулярні вирази в алфавіті S. Це можливо оскільки на кожному кроці виконання П2 для кожного i < n в в правій частині рівняння для Xi не буде невідомих X1, X2, …, Xi-1. Перейти на П5, при цьому i буде рівне n.

П5. Для рівняння з Xi, котре має вигляд Xi = aXi + b, де a, b - регулярні вирази в алфавіті S, записати Xi = a*b. В рівняння для X1, X2, …, Xi-1 підставити замість Xi регулярний вираз a*b.

П6. Якщо і рівне 1 то зупинитися, інакше i зменшити на 1 та перейти на П5.

Приклад 4. Розв'язати систему лінійних рівнянь:

X = a1X + a2Y + a3

Y = b1X + b2Y +b3

З першого рівняння:

X = a1*(a2Y + a3).

Підставимо значення X в друге рівняння та зведемо подібні члени:

Y = b1a1*(a2Y+a3) + b2Y + b3 = b1a1*a2Y + b1a1*a3 + b2Y+ b3 =

(b1a1*a2 + b2)Y + (b1a1*a3 + b3)

Таким чином,

Y = (b1a1*a2 + b2)* (b1a1*a3 + b3).

Підставимо Y в перше рівняння:

X = a1X + a2(b1a1*a2 + b2)* (b1a1*a3 + b3) + a3

Звідси,

X = a1*(a2(b1a1*a2 + b2)* (b1a1*a3 + b3) + a3)

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)