Автоматтарды pumping туралы теоремасы.

Тілді регулярлы болуы оны андай да бір аырлы детерменистік автомат абылданылуымен пара пар. Мнда М-ні кйлеріні саны аырлы. Мысала n дана.

Рumping туралы теоремасы.L-регулярлы жиын болсын, онда саны бар болып, егер -кез келген сз шін , оны трінде жазуа болады. мндаы рі кез келген шін .

Рumping туралы теоремадан: егер бір регулярлы жиында жеткілікті зындыта

сзі бар болса, онда осы жиын сзін де амтитын шексіз жиын дегенді тсінуге болады.

Рumping туралы теорема олданылуы.Ойын ретінде арастырса: сіз ж/е таы бір адам бар, негізгі масат сізді оны жеуііз.

1. Сіз регулярлы емес деп ойлаан бір L тілін тадап алыыз.

2. арсы жа n санын тадап алу керек, яни Рumping туралы теоремадаы траты сан n. Енді кез келген тадап алынан n санына дайын болу керек, біра бір жасы жері арсы жаы бір рет n санын тадап аланнан кейін ол оны згерте алмайды. Дегенмен арсы жаты те осал деп санамау керек.

3. Енді сіз осы L тіліне тиісті бір сздер тізбегі -ны алыыз. Сізді тадап алан арсы жаы тадап алан n санымен іштей байланыста.

4. арсы жаы Сіз берген сзін =xyz трінде жіктеп жазылуы керек, яни x,y,z-ішкі сзін белгілеу керек. рі олар шартын анааттандыруы шарт.

5. Сіз енді Рumping туралы теореманытжырымына айшы орытындыа келтіруііз керек, ол шін кез келген аныталан x,y,z ішкі сздер шін андай да бір бар болып шартын анааттандыратын t санын табу керек.

 

 

 

Майхилл-Нероуд теоремасы.

Майхилла-Нероудты теоремасыны формалды тiлдерiнi теорияларында ажеттi жне тiлдi жйелiлiгiнi жеткiлiктi шарттарын анытайды. Сонымен бiрге осы теорема осы тiлді жйелi длелдеуге ммкiндiк бередi.

Теорема (Майхилл-Нероуд): егер - регуляр тіл болса, онда DFA- L тілін анытайтын автомат табылып, автоматты кйлер саны L тілі бойынша эквивалент кластар санына те.

V алфавитінде L тілі берілсін, L атынасы алфавиттегі бкіл сздер жиынына берілген.

X L y болады сонда ж/е тек сонда ана,егер барлы берілген алфавитке тиісті z шін, xz ж/е yz сздері L тілдеріне тиісті немесе бір уаытта тиісті емес болса. L-Vалфавитіндегі сздер жиыныны эквивалентті атынасы екенін длелдей аламыз. Майхилл Нероуд теоремасы б/ша минималды DFA-та, L-тіл бар, L атынасынасы б/ша эквивалентті класс санына те. Берілген атынас сонымен атар бинарлы атынастардаы индексі деп аталады, indL деп белгіленеді.

Майхил-Нероуд теоремасынан эквивалентті кластар саны аырлы болан кезде ана тіл регулярлы болатындыы шыады. Егер атынас шексіз эквивалентті кластар санында тілді бзса тіл регулярлы болмайды. Бл тжырым регуляр емес тілдерді анытаанда жиі олданылады.

13. Майхилл-Нероуд теоремасыны салдары(регуляр емес тілдер туралы)

L тілі регуляр болады сонда жне тек сонда ана егер тілі бойынша аныталан эквивалент класстар саны аырлы болса. Длелдеу: Егер L тілі регуляр болса, онда L кейбір аырлы автоматтар шін жне -де эквиваленттік класстардан аз емес кй сатайды. Демек в эквивалентті класстарды аырлы саны. Бл салдар арылы тілді регуляр емес екендігін де длелдеуге болады. Мысалы: L={ }

Ешандай екі сз i бола тры атысты эквивалентті емес, себебі кейін жазылса да L тіліні сзін береді, біра L тіліне жатпайтын сзді береді. Осыдан шексіз кп эквивалентті класса ие. Осыны салдарынан L тілі регуляр емес болып шыады.