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

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

уреди

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

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

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

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

уреди

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

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

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

уреди

Регуларни језици су затворени приликом следећих операција, тј. ако су 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š

уреди