- •1.Формальнi мови
- •2.Регулярні мови і регулярні вирази.
- •3.Формальні породжувальні граматики.Типи граматик.
- •4.Автомати Мілі та автомати Мура.Типи автоматів. Способи задання автоматів.
- •6. Недетерміновані скінченні автомати без виходу.Алгоритми синтезу нса.
- •7. Скінченні автомати та регулярні мови. Зв’язок прямолінійних граматик з скінченними автоматами. Існування нерегулярних мов. Лема про роздування.
- •8. Застосування регулярних виразів для конкретного пошуку тексту. Програма grep.Опис, опції, приклад.
- •Розширені регулярні вирази. Метасимволи початку, кінця рядка та довільного символу. Вибір, пошук рядків, які містять декілька регулярних виразів.
- •Квантифікатори (повторювачі). Визначення інтервалів та кількості екземплярів.
- •Символьні класи. Інвертовані символьні класи. Стандартні символьні класи. Приклади використання.
- •12. Групи та зворотні посилання. Приклади використання.
- •Застосування регулярних виразів для обробки тексту. Потоковий текстовий редактор sed. Опис опцій, адресація приклади.
- •Функції редактора sed. Функція контекстної заміни тексту.
- •Функція видалення d, друк p та вставки нових рядків a,c,I. Стирання: d
- •Інверсне обмеження: !
- •Співвідношення між d, p та !
- •Функція транслітерації та шифрування тексту. Приклади використання функції обміну інформацією між робочим та допоміжним буферами.
- •Цикл выполнения
- •Регулярні вирази в програмних продуктах LibreOffice та TotalCommander.
- •Приклад 1
- •Арифметичні та алгебраїчні обчислення в системі Mathematica: арифметичні операції, основні елементарні функції, перетворення алгебраїчних виразів, правила заміни.
- •Операції математичного аналізу в системі Mathematica: знаходження похідних, інтегралів, сум, добутків розв’язування рівнянь.
- •Функції в системі Mathematica. Використання вбудованих функції,означення власних функції користувача та їх використання.
2.Регулярні мови і регулярні вирази.
Нехай X – довiльний алфавiт. Визначимо регулярну мову (множину) в алфавiтi X рекурсивно наступним чином:
1) порожня множина ∅ є регулярною мовою;
2) для кожної букви a ∈ X множина {a} є регулярною мовою;
3) якщо A i B є регулярними мовами, то множини A ∪ B, AB і також є регулярними мовами;
4) iнших регулярних мов не iснує.
Пpиклад.
1) множина {e} є регулярною мовою, бо {e} = ;
2) множина {001, 110} – регулярна мова над бiнарним алфавiтом, бо
{001, 110} = ({0}{0}{1}) ∪ ({1}{1}{0});
Щоб спростити зображення регулярних мов, визначимо поняттярегулярного виразу над алфавiтом X наступним чином:
1) порожня множина ∅ є регулярним виразом, який позначає порожню множину;
2) e є регулярним виразом, який позначає мову {e};
3) для кожної букви a ∈ X a – регулярний вираз, що позначає мову {a};
4) якщо i є регулярними виразами, що позначають мови A i B вiдповiдно, то ( )+( ), ( )( ) i є регулярними виразами, що позначають мови A ∪ B, AB i вiдповiдно;
5) iнших регулярних виразiв над алфавiтом X не iснує.
Щоб зменшити кiлькiсть дужок в регулярних виразах, будемо вважати, що найвищий прiоритет має операцiя iтерацiї ∗, потiм – конкатенацiя i останньою виконується операцiя +. Наприклад, 01 позначає {01}, – , – , а 001 позначає
множину всiх слiв, якi складаються з нулiв i одиниць i закiнчуються словом 001.
Для кожної регулярної мови iснує нескiнченно багато виразiв, що ї ї зображують. Наприклад, вирази 1+∅ i 1 зображують одну й ту ж мову {1}. Кажемо, що
два регулярних вирази рiвнi (=), якщо вони позначають одну i ту ж
множину.
3.2. Твеpдження. Нехай α, β i γ – регулярнi вирази. Тодi:
• α + β = β + α; • = e; • α + (β + γ) = (α + β) + γ; • α(βγ) = (αβ)γ; • α(β + γ) = αβ + αγ;
• (α + β)γ = αγ + βγ; • αe = eα = α; • ∅α = α∅ = ∅; • = α + ; • = ; • α + α = α;
• α + ∅ = α.
Доведення. Нехай α i β позначають множини A i B вiдповiдно. Тодi α+β позначає A∪B, а β +α позначає B ∪A. Але A∪B = B ∪A за означенням об’єднання, тому α + β = β + α. Решту рiвностей доводяться аналогiчно. Дов.
Для зручностi запису введемо таке позначення: = .
Регулярнi вирази часто зображують помiченими орiєнтованими графами, стрiлки яких позначають буквами з алфавiту X ∪ {e}. Для довiльного регулярного виразу r, граф, що його зображує, утворюється наступним чином:
С початку малюємо двi спецiальнi вершини, якi називаються початковою i кiнцевою вершинами, i сполучаємо їх стрiлкою, позначеною r:
Далi, повторюємо наступнi кроки, доки кожна позначка довiльної стрiлки не мiститиме символiв +, · :
1)замiнюємо кожну стрiлку з позначкою f +g на двi паралельнi стрiлки з позначками f i g:
2 ) замiнюємо кожну стрiлку з позначкою fg на додаткову вершину i двi стрiлки з позначками f i g:
3 ) замiнюємо кожну стрiлку з позначкою на додаткову вершину i на три стрiлки з позначками e, f i e:
Для регулярного виразу r позначимо через G(r) помiчений орiєнтований граф, що його зображує. Очевидно, що кожна стрiлка в G(r) має позначку з множини X ∪ {e}. Кожному шляху в G(r) вiдповiдає слово, яке одержується конкатенацiєю всiх букв, якi позначають стрiлки шляху. Слово x належить мовi L(r) тодi i тiльки тодi, коли iснує шлях в G(r) з початкової вершини в кiнцеву вершину, якому вiдповiдає слово x. Кожна
е - стрiлка в G(r), яка є єдиною вихiдною стрiлкою з некiнцевої вершини чи єдиною вхiдною стрiлкою в непочаткову вершину може бути стягнута в одну вершину.