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

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

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

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

Алдымен бульдік операцияларында: бірігу, қиылысу, толықтау кезіндегі тұйықталу қасиетін қарастырайық. 1) Егер L,M тілдері ∑ алфавитіне тиісті болса, онда LUM тілінде L,M тілдерінің кем дегенде біреуінде бар барлық тізбектер (цепочка) бар; 2) Егер L,M тілдері ∑ алфавитіне тиісті болса, L∩M тілінде 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 тілдері де регуляр#