www.wikidata.uk-ua.nina.az

Регулярна граматика Див також Регулярний вираз Цю статтю потрібно повністю переписати відповідно до стандартів якості Ві

Регулярна граматика

Див. також: Регулярний вираз
Цю статтю потрібно повністю переписати відповідно до стандартів якості Вікіпедії. Ви можете допомогти, переробивши її. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (травень 2020)

Регулярна граматика — формальна граматика типу 3 за ієрархією Чомскі. Регулярні граматики визначають в точності всі регулярні мови, і тому еквівалентні кінцевим автоматам і регулярним виразами. Регулярні граматики є підмножиною контекстно-вільних.

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

Теоретичні відомості ред.

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

Для теорії автоматів притаманний наступний підхід. Фіксується деякий клас автоматів K. Ставиться задача: побудувати мову L (як правило, таку, що не використовує автоматних понять, зручну в тому чи іншому відношенні, що задовольняє певним вимогам, і т. д.), таку, що всі L події, і тільки вони представимі в автоматах класу K.

Розв'язання цієї задачі включає доведення двох теорем:

  • теореми синтезу (кожна L-подія представима в деякому автоматі класу K)
  • теореми аналізу (кожна подія, представима в автоматі класу K, є L-подією).

Як правило, теорема синтезу одразу припускає наявність алгоритму синтезу, тобто, алгоритму побудови автомата за заданою подією, а теорема аналізу — алгоритму аналізу, тобто, алгоритму побудови L-виразу за заданим автоматом.

Вперше такий підхід в теорії автоматів застосував американський математик Кліні С. К., для класу скічненних автоматів. Для подій, представимих в скінченних автоматах, він побудував спеціальну мову — мову регулярних виразів. Ця мова стала однією із основних мов для визначення умов функціонування автомату, особливо після його вдосконалення (а також відповідних алгоритмів синтезу та аналізу) в працях радянського математика Глушкова В. М., та американського математика Мак-Нотона Р. Ф., і інших дослідників.

Побудова алгебраїчної мови ред.

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

  1. A ∨ B — диз'юнкція або об'єднання (позначається також A ∪ B) — теоретико множинна операція: подія A ∨ B являє собою звичайне об'єднання множин A та B;
  2. AB — добуток (конкатенація), визначається через добуток слів. Добутком слів p та q називають слово pq, утворене в результаті дописування слова q справа до слова p. Подія AB складається із тих і тільки тих слів, які мають вигляд pq, де p належить A, а q належить B;
  3. {A} — ітерація (позначається також A*).

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

Таким чином, слово q тоді і тільки тоді належить {A}, коли q має вигляд pn, де p — належить A.

Нехай алфавіт X, над яким розглядаються події, складається із літер x1, x2, …, xm, тоді подія, яка складається із одного однолітерного слова xi (i = 1, 2, …, m), називається елементарною подією і позначається символом xi, тобто, відповідає одній літері алфавіту.

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

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

Будь-який регулярний вираз R визначає деяку подію S (S отримується в результаті виконання всіх операцій, які входять у вираз R). Події, які визначаються в такий спосіб, називаються регулярними подіями над алфавітом X. Іншими словами, регулярною подією називається подія, отримана із елементарних, із допомогою застосування скінченої кількості раз операції диз'юнкції, добутку і ітерації.

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

Приклад застосування ред.

Наприклад, в алфавіті із трьох літер x, y, z, регулярний вираз

визначає подію (регулярну), яка складається із всіх слів, які починаються на літеру x і закінчуються літерою y або z.

У сучасних мовах програмування, наприклад, Perl, аналогічний вираз міг би мати вигляд: 

^x[xyz]*[yz]$

Джерела інформації ред.

Див. також ред.


Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Div takozh Regulyarnij viraz Cyu stattyu potribno povnistyu perepisati vidpovidno do standartiv yakosti Vikipediyi Vi mozhete dopomogti pererobivshi yiyi Mozhlivo storinka obgovorennya mistit zauvazhennya shodo potribnih zmin traven 2020 Regulyarna gramatika formalna gramatika tipu 3 za iyerarhiyeyu Chomski Regulyarni gramatiki viznachayut v tochnosti vsi regulyarni movi i tomu ekvivalentni kincevim avtomatam i regulyarnim virazami Regulyarni gramatiki ye pidmnozhinoyu kontekstno vilnih Regulyarni podiyi ta virazi ce podiyi sho mozhna predstaviti u skinchennih avtomatah a takozh vidpovidni virazi skladeni za specialnoyu algebrichnoyu movoyu regulyarna mova yaka zadaye ci podiyi Zmist 1 Teoretichni vidomosti 1 1 Pobudova algebrayichnoyi movi 1 2 Regulyarni virazi 2 Priklad zastosuvannya 3 Dzherela informaciyi 4 Div takozhTeoretichni vidomosti red Podiyeyu nazivayetsya dovilna mnozhina sliv v deyakomu alfaviti Prirodno sho pri vivchenni teoriyeyu avtomativ riznomanitnih pitan pov yazanih z ponyattyam podiyi yak pravilo pripuskayetsya nayavnist deyakih zasobiv dlya opisannya viznachennya podij Takim konstruktivnim zasobom mozhe buti formalna mova virazi yakoyu zadayut podiyi nad deyakim alfavitom tobto formalna mova interpretuyetsya v mnozhinu podij Yaksho poznachiti cyu movu cherez L to pravilno pobudovani virazi mozhna nazivati L virazami a podiyi yaki voni zadayut L podiyami Ochevidno sho mnozhina vsih L podij dlya bud yakoyi movi L ne bilsh nizh lichima oskilki mnozhina vidpovidnih viraziv ne bilsh nizh zlichima Oskilki potuzhnist mnozhini vsih podij kontinualna to nema takoyi movi L dlya yakoyi vsi podiyi ye L podiyami Dlya teoriyi avtomativ pritamannij nastupnij pidhid Fiksuyetsya deyakij klas avtomativ K Stavitsya zadacha pobuduvati movu L yak pravilo taku sho ne vikoristovuye avtomatnih ponyat zruchnu v tomu chi inshomu vidnoshenni sho zadovolnyaye pevnim vimogam i t d taku sho vsi L podiyi i tilki voni predstavimi v avtomatah klasu K Rozv yazannya ciyeyi zadachi vklyuchaye dovedennya dvoh teorem teoremi sintezu kozhna L podiya predstavima v deyakomu avtomati klasu K teoremi analizu kozhna podiya predstavima v avtomati klasu K ye L podiyeyu Yak pravilo teorema sintezu odrazu pripuskaye nayavnist algoritmu sintezu tobto algoritmu pobudovi avtomata za zadanoyu podiyeyu a teorema analizu algoritmu analizu tobto algoritmu pobudovi L virazu za zadanim avtomatom Vpershe takij pidhid v teoriyi avtomativ zastosuvav amerikanskij matematik Klini S K dlya klasu skichnennih avtomativ Dlya podij predstavimih v skinchennih avtomatah vin pobuduvav specialnu movu movu regulyarnih viraziv Cya mova stala odniyeyu iz osnovnih mov dlya viznachennya umov funkcionuvannya avtomatu osoblivo pislya jogo vdoskonalennya a takozh vidpovidnih algoritmiv sintezu ta analizu v pracyah radyanskogo matematika Glushkova V M ta amerikanskogo matematika Mak Notona R F i inshih doslidnikiv Pobudova algebrayichnoyi movi red Algebrayichna mova buduyetsya yak mova viraziv deyakoyi algebri V comu vipadku rozglyadayetsya mova dlya opisannya podij tomu mnozhina vsih podij yavlyaye soboyu deyaku universalnu algebru tobto nad podiyami viznachayutsya algebrayichni operaciyi Dlya pobudovi movi regulyarnih viraziv bulo vikoristano tri operaciyi nad podiyami dvi binarni i odna unarna A B diz yunkciya abo ob yednannya poznachayetsya takozh A B teoretiko mnozhinna operaciya podiya A B yavlyaye soboyu zvichajne ob yednannya mnozhin A ta B AB dobutok konkatenaciya viznachayetsya cherez dobutok sliv Dobutkom sliv p ta q nazivayut slovo pq utvorene v rezultati dopisuvannya slova q sprava do slova p Podiya AB skladayetsya iz tih i tilki tih sliv yaki mayut viglyad pq de p nalezhit A a q nalezhit B A iteraciya poznachayetsya takozh A Iteraciya viznachayetsya trohi skladnishe Vvedemo poznachennya An dlya dobutku A A A n displaystyle begin matrix underbrace AA dots A n end matrix nbsp Todi iteraciyu mozhna visloviti cherez poperedni dvi operaciyi tak A A A2 An Takim chinom slovo q todi i tilki todi nalezhit A koli q maye viglyad pn de p nalezhit A Nehaj alfavit X nad yakim rozglyadayutsya podiyi skladayetsya iz liter x1 x2 xm todi podiya yaka skladayetsya iz odnogo odnoliternogo slova xi i 1 2 m nazivayetsya elementarnoyu podiyeyu i poznachayetsya simvolom xi tobto vidpovidaye odnij literi alfavitu Regulyarni virazi red Viraz pobudovanij iz liter alfavitu X simvoliv elementarnih podij i iz simvoliv operacij diz yunkciyi dobutku i iteraciyi z vikoristannyam vidpovidnim chinom kruglih duzhok nazivayetsya regulyarnim virazom v alfaviti X Bud yakij regulyarnij viraz R viznachaye deyaku podiyu S S otrimuyetsya v rezultati vikonannya vsih operacij yaki vhodyat u viraz R Podiyi yaki viznachayutsya v takij sposib nazivayutsya regulyarnimi podiyami nad alfavitom X Inshimi slovami regulyarnoyu podiyeyu nazivayetsya podiya otrimana iz elementarnih iz dopomogoyu zastosuvannya skinchenoyi kilkosti raz operaciyi diz yunkciyi dobutku i iteraciyi Regulyarni podiyi i tilki voni predstavimi v skinchenih avtomatah Priklad zastosuvannya red Dokladnishe Regulyarnij virazNapriklad v alfaviti iz troh liter x y z regulyarnij viraz x x y z y z viznachaye podiyu regulyarnu yaka skladayetsya iz vsih sliv yaki pochinayutsya na literu x i zakinchuyutsya literoyu y abo z U suchasnih movah programuvannya napriklad Perl analogichnij viraz mig bi mati viglyad x xyz yz Dzherela informaciyi red Enciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973 T 2 S 285 Div takozh red nbsp Portal Matematika Algebrayichna teoriya avtomativ Algebra podij Universalni algebri Regulyarnij viraz Algoritmi viznachennya regulyarnosti gramatiki Programuvannya Glibina ciklichnoyi podiyi nbsp Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Regulyarna gramatika amp oldid 36412333