Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




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

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

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

Алдымен бульдік операцияларында: бірігу, қиылысу, толықтау кезіндегі тұйықталу қасиетін қарастырайық. 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 — автомат тілдері AL = (QL, Σ, δL, qL, FL) және AM =(QM, Σ, δM, qM, FM) автомат алфавиттері бірдей болып саналады, яғни егер L және M. Оңай болу үшін AL = (QL, Σ, δL, qL, FL) және AM = (QM, Σ, δM, qM, FM) DFA болсын. L,M үшін AL және AM бір уақытта автомат күйлерін моделідейтін А автоматын құрастырайық. А қос куй болсын, біріншісі AL куйі ал екіншісі AM куйі болсын. А автоматының өту жолдарын құру үшін, А (p, q) куйінде тұр деп ұйғарайық. Мұндағы р-автомат куйі, ал q- AM куйі. AL

Автоматы қандай әрекет орындайтынын білеміз, кірісінде а символын алады. Ол s куйіне өтсін, ал - AM а кіріс символы арқылы t куйіне өтеді. Онда А автоматының куйі (s, t) болады, сөйтіп А автоматы AL және AM автоматтарының жұмысын моделдейді. A былай анықталады A = (QL × QM, Σ, δ, (qL, qM), (FL × FM),где δ((p, q), a) = (δL(p, a), δM(q, a)).#

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

 

 





Поделиться с друзьями:


Дата добавления: 2017-02-24; Мы поможем в написании ваших работ!; просмотров: 644 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Либо вы управляете вашим днем, либо день управляет вами. © Джим Рон
==> читать все изречения...

2259 - | 1997 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.008 с.