Регуляр рнектер мен регуляр тілдер.

-алфабиті бойынша регуляр рнек келесідей рекурсивті жолмен аныталады: 0-регуляр рнек болып табылады; 1- регуляр рнек болып табылады; егер болса, онда -регуляр рнек болады; егер регуляр рнек болса, онда ( ), ( ) жне рнектері де регуляр рнектер болады.

Жашаларды азайту масатында, операциясыны приоритеті кбейту операциясынан жоары, ал кбейту амалыны приоритеті осу операциясына араанда жоары деп аламыз. Кбінесе -ті орнына деп жазады.

Мысалы: . Онда –регуляр рнек болады.

рбір е регуляр рнегі алфабиті бойынша андай да бір тіл рады, ол келесідей рекурсивті жболмен аныталады:

1) L(a){a}, егер болса,

2) L(0)ø,

3) L(1){e},

4) L(e*f) ,

АН: L-регуляр тіл деп аталады, егер ол андай да бір регуляр рнекпен аныталса.

Ан: е-регуляр рнек болсын. Онда

1) 2) 3) e+0=e 4)

5) 6) 8) 9)

10) 11)

Лемма: Кез-келген регуляр рнектері шін келесі тепе-тедіктер орындалады:

Лемма: Кез-келген

L тілі регулярлы тіл деп аталады, егерде М автоматы табылып: орындалса. Аырлы автоматпен абылданатынбарлы тіл регулярлы.

5. Детерменистік аырлы автоматтар, олармен абылданатын тілдер. Конфигурация.Детерминистік автоматпен абылданатын тіл.Аырлы автомат (finite automaton,FA) M=(Qq0F) Q——кйлерді бос емес аырлы жиыны . qQq-ді M-ны бір кйі деп атаймыз. (state). —— алфавит (Input alphabet). Енгізілген сздер тізбегі тек даы cимволдардан алынады. q0——q0Q, M-автоматыны бастапы кйі (initial state). ——кй ауыстыру функциясы (transition function). Q×Q, (qa)Q×шін (qa)=p арылы M-автоматыны q кйінде трып a символын оып, кйін p-а ауыстыруды сонымен бірге оа арай бір адам жылжытуды білдіреді. F——FQ, M-ны аятау кйлеріні жиынын білдіреді (final state). qF, q-ді M-ны тотау кйі деп атаймыз немесе абылдау кйі (accept state). Анытама: Конфигурация немесе тез бейнелеу( instantaneous description) аырлы автоматы (Q, , , I, F) деп кез-келген реттелген жпты (q, ) айтамыз, мнда qQ жне .

Анытама: Барлы конфигурацияны кбіндегі аырлы автоматын М бинарлы атынасты келесідей анытаймыз. Егер (p, x, q) жне , онда (p, x ) (q, w)

ны толытыру: : Q× > Q. Кез-келген qQ шін (1) (q, )= q (2) (q, )= ( (q, ), a) (q, )= (q, )= ( (q, ), a) = (q, ) Кез келген qQ, a шін (q,a)-натылы анытаан мні бар болса, онда ондай автоматты Детерминистік аырлы автомат деп атаймыз M- абылдайтыаан тіл: x*шін,егер (q,w)F болса, онда x-ті M-абылдайды дейміз, ал (q,w) F болса, онда M-автоматы x-ті абылдамайды деп атаймыз. L(M)={x| x*рі (q,w)F } M-автоматымен абылданатын тіл. -L(M1)=L(M2)={02n|n1} Егер L(M1)=L(M2), онда M1мен M2 автоматтары эквивалент деп аталады. Егер q ден а дейін w арылы жол бар болса, онда оны тмендегідей белгілейміз (q, ) =

6.Аырлы детерминистік емес автомат ымы. Детерминистік емес автоматпен абылданатын тіл.Детерминистік емес аырлы автомат - бл мына бестіктен трады:М=(K, , , s, F) K- аырлы кйлерді жиыны - алфавит sK- бастапы кй F - аырлы кйлер жиыны - кшу кйі, K×( K Анытама: Конфигурация немесе тез бейнелеу( instantaneous description) аырлы автоматы (Q, , , I, F) деп кез-келген реттелген жпты (q, ) айтамыз, мнда qQ жне . Ламбда тасымалы

Орындалады сонда жне тек ана сонда егер qi-ден qj -ге дейін w бойынша бір жол

бар болса болады

р штік (q, u, p) М ге кшу деп аталады; Бл баытты формализациясы. Аныталынан детерменистік аырлы автоматтармен детерменистік емес аырлы автоматты есептеудi анытамасы те сас. Конфигурация М бл K× . Конфигурацияны арасындаы жадай былай аныталады: (q, w) ( ) сонда жне тек сонда ана, u {e} болан жадайда, w=u жне (q, u, ) . Байаса – міндетті трде функция емес: кейбір конфигурациялара (q, w) бірнеше жп болуы ммкін ( ) немесе ешандай жп болмауы ммкін - (q, w) ( ).