Регуляр тілдерді тйытау асиеттері. Аырлы автоматты тйыты асиеттері.

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

Регуляр тілдерді тйыты асиеттері келесі операциларда сйкесінше орындалады:

Бірігу, иылысу, толытау,итерация, конкатенация, гомоморфизм, кері гомоморфизм.

Алдымен бульдік операцияларында: бірігу, иылысу, толытау кезіндегі тйыталу асиетін арастырайы. 1) Егер L,M тілдері алфавитіне тиісті болса , онда LUM тілінде L,M тілдеріні кем дегенде біреуінде бар барлы тізбектер (цепочка) бар; 2) Егер L,M тілдері алфавитіне тиісті болса, LM тілінде Lжне M тілдеріні барлы тізбектері (цепочка) бар; 3) Егер андай да бір L тілі алфавитіне тиісті болса, онда ^¯L тілі, L-ді толытауы – L тіліне жатпайтын * алфавитіні тізбектеріні жиыны.

ТЕОРЕМА.Егер L,M тілдері алфавитіне тиісті болса жне регуляр тіл болса, онда LUM тілі де регуляр тіл. ДЛЕЛДЕУІ. L,M тілдері регуляр тіл боландытан, олара кейбір регуляр сйлемдер сай келеді, L=L(R) M=L(S) болсын, онда регуляр сйлемдер шін операцияны анытамасы бойынша LUM=L(R+S) # Бл теореманы длелдеу идеясы конкатенация мен итерацияа да сай келеді: 1)(конкатенация) Егер L,M тілдері алфавитіне тиісті болса жне регуляр тіл болса, онда LM тілі де регуляр тіл.

2)(итерация) Егер L алфавитіне тиісті болса жне регуляр тіл болса, онда L* тілі де регуляр тіл.

ТЕОРЕМА.Егер L тілі алфавитіне тиісті болса жне регуляр тіл болса, онда ^¯L * боландытан L регуляр тіл.ДЛЕЛДЕУІ. андай да бір L=L(A) болысн . A = DFA (Q, , , q0, F). Онда L = L(B), Мндаы B- DFA болысн (Q, , , q0, Q – F), яни Ажне В бірдей автоматтар тек А-даы кйлер В-да орындалмайды, жне сйкесінше В-даы кйлер А-да орындалмайды. Онда w L(B)-да жатса, сонда жне сонда ана (q0, w)

Q – F- те жатады , яни w L(A)-а жатпайды. Мндаы (q0, w) – андай да бір кй. Ада барлы жолдар аныталан, егер андай да бір жолдар аныталмаан болса (жо болса) онда L(A)-да L(B)-да жо болар еді, біра уаныша орай DFA-да рбір кйде алфавитіні рбір кйіне жол бар боландытан, рбір тізбек (цепочка) F немесе Q-F кйіне апарады. #

ТЕОРЕМА. Егер L,M тілдері алфавитіне тиісті болса жне регуляр тіл болса, онда L M тілі де регуляр тіл. L жне M — автомат тілдері A_L = (Q_L, , _L, q_L, F_L) жне A_M =(Q_M, , _M, q_M, F_M) автомат алфавиттері бірдей болып саналады, яни егер L жне M. Оай болу шін A_L = (Q_L, , _L, q_L, F_L) жне A_M = (Q_M, , _M, q_M, F_M) DFA болсын. L,M шін A_L жне A_M бір уаытта автомат кйлерін моделідейтін А автоматын растырайы. А ос куй болсын, біріншісі A_L куйі ал екіншісі A_M куйі болсын. А автоматыны ту жолдарын ру шін, А (p, q) куйінде тр деп йарайы. Мндаы р-автомат куйі, ал q- A_M куйі. A_L

Автоматы андай рекет орындайтынын білеміз, кірісінде а символын алады. Ол s куйіне тсін, ал - A_M а кіріс символы арылы t куйіне теді. Онда А автоматыны куйі (s, t) болады, сйтіп А автоматы A_L жне A_M автоматтарыны жмысын моделдейді. A былай аныталады A = (Q_L × Q_M, , , (q_L, q_M), (F_L × F_M),где ((p, q), a) = (_L(p, a), _M(q, a)).#

ТЕОРЕМА. Егер L,M тілдері алфавитіне тиісті болса жне регуляр тіл болса, онда L M тілі де регуляр тіл.L – M = L M. Теорема бойынша М жне L M регуляр тілдер => L – M тілдері де регуляр#