Регуларни језик

У теоретској компјутерској науци, регуларни језик је формални језик (тј. неограничен скуп низова симбола из ограниченог скупа алфабета) који задовољава следеће истоветне особине:

• може бити прихваћен од стране детерминистички одређеног аутомата (машине)
• може бити прихваћен од стране недетерминистичког коначног аутомата
• може бити прихваћен од стране алтернирајућег коначног аутомата
• може бити описан формалним регуларним изразом. Обратите пажњу да су својства „регуларног израза“ доступна од стране многих програмских језика образложени особинама уз помоћ којих могу да препознају језике који нису регуларни, те стога нису у потпуности еквивалентни формалним регуларним изразима.
• може бити генерисан од стране регуларне граматике
• може бити прихваћен од стране Тјурингове машине
• може бити препознат од стране неког ограничено одређеног моноида
• он је препознат неким финално генерисаним моноидом
• он је претходна верзија подскупа финитног моноида у хомоморфизму од слободног моноида из свог алфабета

Регуларни језици изван неког алфабета

Скуп регуларних језика у једном алфабету Σ неког језика дефинише се искључиво на следећи начин:

• празан језик Ø је регуларни језик.
• језик празног низа { ε } је регуларни језик.
• За свако а које припада скупу Σ синглетон од а { а } је регуларни језик.
• Уколико су А и Б регуларни језици онда су А унија Б , А надовезивање на Б, и А* (Клинијев оператор) регуларни језици.
• Ниједан језик изван Σ није регуларан језик.

Сви коначни језици су регуларни. Други типични примери укључују све језике који садрже све низове изван алфабета {а, b} који садрже паран број а, или језик који се састоји из свих низова форме: неколико а је праћено са неколико b.

Резултати комплексности

У компјутерској теорији комплексности (сложености), комплексна класа свих регуларних језика понекад се назива REGULAR или REG представља исто што и DSPACE(О(1)) проблеми који се могу решити у непроменљивом простору (простор који се користи је независан од улазне величине). REGULAR ≠ AC° пошто укључује проблем одлучивања да ли број 1 битова (низова) у инпуту је паран или непаран и овај проблем није у AC°¹. С друге стране није познато да садржи AC°.

Уколико језик није регуларан тада аутомат мора имати најмање Ω (log log n) простора да га препозна (где n означава улазну величину)². Другим речима, DSPACE(o(log log n)) представља класу регуларних језика. У пракси већина нерегуларних проблема се решава помоћу аутомата који захтевају најмање логаритмиски простор.

Својства затворености

Регуларни језици су затворени приликом следећих операција, тј. ако су L и P регуларни језици онда су и следећи језици регуларни:

• комплемент од L
• Клинијев оператор L* од L
• слика φ(L) од L под низом хомеоморфизма
• надовезивање језика L на језик P
• унија језика L и P
• пресек језика L и P
• разлика језика L и P
• супротност

Одлучивање да ли је језик регуларан

Приликом одлучивања да ли је језик регуларан да би га сместили у хијерархију Чомског примећујемо да је сваки језик контекстно-слободан. Супротно од тога нпр. језик који се састоји од низа који има подједнак број а и б је контекстно-слободан али није регуларан. Да би доказали да један овакав језик није регуларан користимо Михил-Неродову теорему или лему о надувавању.

Не постоје два искључиво алгебарска приступа у дефинисању регуларних језика. Уколико је Σ ограничени алфабет а Σ* означава слободни моноид изван Σ који садржи све низове изван Σ, ф : Σ* → M је моноидни хомоморфизам где је M финитни моноид, С је подскуп од M, онда је скуп инверзних слика скупа С регуларан. Сваки језик произилази на овај начин.

Ако је L било који подскуп од Σ* онда релацију еквиваленције ~ (својевремено знану као синтаксичка релација) дефинишемо у Σ* као што следи: u ~ v је дефинисано да значи да је

uw Є L ако и само ако vw Є L за све w Є Σ*.

Језик L је регуларан ако и само ако је број еквивалентних класа од ~ ограничен (Доказ за ово се налази у чланку о синтаксичком моноиду). Када је језик регуларан, онда је број еквивалентних класа једнак броју минималне детерминистички одређене аутоматизације прихваћене у L.

Сличан скуп тврдњи може се формулисати за моноид M који је подскуп скупа Σ*. У овом случају, еквивалентност изван M доводи до концепта препознатљивих језика.

Финитни (ограничени) језици

Посебан подскуп у оквиру класе регуларних језика је finitni jezik - oni koji sadrže jedino ograničen broj reči. Oni su očigledno regularni pošto možete napraviti regularni izraz koji predstavlja uniju svih reči u jeziku te je stoga regularan.

Vidi još

• Lema o naduvavanju za regularne jezike