Регулярна мова (регулярна множина) — формальна мова третього (найвужчого) класу в ієрархії Чомскі.
Регулярну мову можна задати регулярною граматикою або регулярним виразом, або ж ДСкА чи НДСкА, що її розпізнають.
Від контекстно-вільних мов регулярні відрізняються додатковими умовами: права частина правил виведення має бути порожнім словом, термінальним, нетермінальним, або нетермінальний вслід за яким стоїть термінальний символ.
Для визначення приналежності мови до класу регулярних існує Лема про накачку для регулярних мов та .
Означення
Нехай — скінченний алфавіт. Регулярна мова в цьому алфавіті визначається рекурсивно:
- — пуста множина — це регулярна множина в алфавіті
- — пусте слово — це регулярна множина в алфавіті
- — однолітерна множина — регулярна множина в алфавіті
- Якщо та — регулярні множини, то такими є наступні множини:
- (операція об‘єднання);
- (операція конкатенації);
- (операція ітерації).
- Ніякі інші множини, окрім побудованих на основі ПП 1-4 не є регулярними множинами.
«Стандартними» способами опису регулярної мови є представлення її у вигляді скінченного автомату, регулярної граматики, або ж регулярного виразу.
Теорія автоматів
Формальна мова є регулярною тоді й лише тоді, коли існує детермінований скінченний автомат здатний її розпізнати (акцептор).
При чому, для кожної регулярної мови можна побудувати недетермінований скінченний автомат, що її розпізнає. Та навпаки, кожен недетермінований скінченний автомат розпізнає певну регулярну мову.
Властивості
Регулярні мови замкнені відносно операцій об'єднання, перетину, конкатенації, доповнення та зірочки Кліні. Тобто, якщо та регулярні мови, тоді регулярними будуть мови: , , , , та .
Існують й інші операції, відносно яких замкнені регулярні мови. Так, наприклад, гомоморфне відображення регулярної мови також є регулярною мовою. Таким чином, регулярні мови замкнені відносно гомоморфізму.
Крім того, для будь-якої регулярної мови у стандартному представленні існує алгоритм, що визначає приналежність заданого слова до цієї мови. Стандартне представлення регулярної мови також дає можливість створити алгоритм, який би перевіряв чи ця мова порожня, скінченна, або ж нескінченна.
Стандартне представлення регулярних мов також дає можливість створити алгоритм, який би перевіряв їх на рівність.
Примітки
- (Розділ 4.2 в Linz)
- Визначення 2.3 в: Peter Linz (January 2016). 2.1 Deterministic Finite Accepters. An Introduction to Formal Languages and Automata (вид. 6-те). Jones & Bartlett Learning. ISBN .
- Теореми 3.4.1.2 та 3.4.1.3 в: by George Tourlakis (April 2012). 3.4 REGULAR GRAMMARS AND LANGUAGES. Theory of Computation. John Wiley & Sons. ISBN .
- теорема 4.1 у Linz
- теорема 4.3 у Linz
- (теорема 4.5 у Linz)
- (теорема 4.6 у Linz)
- (теорема 4.7 у Linz)
Див. також
Це незавершена стаття про мови програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Regulyarna mova regulyarna mnozhina formalna mova tretogo najvuzhchogo klasu v iyerarhiyi Chomski Regulyarnu movu mozhna zadati regulyarnoyu gramatikoyu abo regulyarnim virazom abo zh DSkA chi NDSkA sho yiyi rozpiznayut Vid kontekstno vilnih mov regulyarni vidriznyayutsya dodatkovimi umovami prava chastina pravil vivedennya maye buti porozhnim slovom terminalnim neterminalnim abo neterminalnij vslid za yakim stoyit terminalnij simvol Dlya viznachennya prinalezhnosti movi do klasu regulyarnih isnuye Lema pro nakachku dlya regulyarnih mov ta OznachennyaNehaj S displaystyle Sigma skinchennij alfavit Regulyarna mova v comu alfaviti viznachayetsya rekursivno displaystyle emptyset pusta mnozhina ce regulyarna mnozhina v alfaviti S displaystyle Sigma e displaystyle varepsilon puste slovo ce regulyarna mnozhina v alfaviti S displaystyle Sigma a a S displaystyle a a in Sigma odnoliterna mnozhina regulyarna mnozhina v alfaviti S displaystyle Sigma Yaksho P displaystyle P ta Q displaystyle Q regulyarni mnozhini to takimi ye nastupni mnozhini P Q displaystyle P cup Q operaciya ob yednannya P Q displaystyle P Q operaciya konkatenaciyi P e P P P displaystyle P varepsilon cup P cup P P cup ldots operaciya iteraciyi Niyaki inshi mnozhini okrim pobudovanih na osnovi PP 1 4 ne ye regulyarnimi mnozhinami Standartnimi sposobami opisu regulyarnoyi movi ye predstavlennya yiyi u viglyadi skinchennogo avtomatu regulyarnoyi gramatiki abo zh regulyarnogo virazu Teoriya avtomativ Formalna mova ye regulyarnoyu todi j lishe todi koli isnuye determinovanij skinchennij avtomat zdatnij yiyi rozpiznati akceptor Pri chomu dlya kozhnoyi regulyarnoyi movi mozhna pobuduvati nedeterminovanij skinchennij avtomat sho yiyi rozpiznaye Ta navpaki kozhen nedeterminovanij skinchennij avtomat rozpiznaye pevnu regulyarnu movu VlastivostiRegulyarni movi zamkneni vidnosno operacij ob yednannya peretinu konkatenaciyi dopovnennya ta zirochki Klini Tobto yaksho L1 displaystyle L 1 ta L2 displaystyle L 2 regulyarni movi todi regulyarnimi budut movi L1 L2 displaystyle L 1 cup L 2 L1 L2 displaystyle L 1 cap L 2 L1L2 displaystyle L 1 L 2 L1 displaystyle L 1 emptyset ta L1 displaystyle L 1 Isnuyut j inshi operaciyi vidnosno yakih zamkneni regulyarni movi Tak napriklad gomomorfne vidobrazhennya regulyarnoyi movi takozh ye regulyarnoyu movoyu Takim chinom regulyarni movi zamkneni vidnosno gomomorfizmu Krim togo dlya bud yakoyi regulyarnoyi movi u standartnomu predstavlenni isnuye algoritm sho viznachaye prinalezhnist zadanogo slova do ciyeyi movi Standartne predstavlennya regulyarnoyi movi takozh daye mozhlivist stvoriti algoritm yakij bi pereviryav chi cya mova porozhnya skinchenna abo zh neskinchenna Standartne predstavlennya regulyarnih mov takozh daye mozhlivist stvoriti algoritm yakij bi pereviryav yih na rivnist Primitki Rozdil 4 2 v Linz Viznachennya 2 3 v Peter Linz January 2016 2 1 Deterministic Finite Accepters An Introduction to Formal Languages and Automata vid 6 te Jones amp Bartlett Learning ISBN 9781284077254 Teoremi 3 4 1 2 ta 3 4 1 3 v by George Tourlakis April 2012 3 4 REGULAR GRAMMARS AND LANGUAGES Theory of Computation John Wiley amp Sons ISBN 9781118014783 teorema 4 1 u Linz teorema 4 3 u Linz teorema 4 5 u Linz teorema 4 6 u Linz teorema 4 7 u Linz Div takozhIyerarhiya Chomski Regulyarna gramatika Ce nezavershena stattya pro movi programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi