СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Ավտոմատ սարքերի աշխատանքի սկզբունքը ներկայացված է Մուրի և Մոլլի ավտոմատների աշխատանքի օրինակով

Категория: Всем учителям

Нажмите, чтобы узнать подробности

Այս աշխատանքը ներկայացնում է ավտոմատ սարքերի աշխատանքի սկղբունքը Միլլի և Մուրի ավտոմատների օրինակով

Просмотр содержимого документа
«Ավտոմատ սարքերի աշխատանքի սկզբունքը ներկայացված է Մուրի և Մոլլի ավտոմատների աշխատանքի օրինակով»























Ավտոմատների կիրառական տեսոթյուն






























Ծրագրավորման լեզուների ընդհանուր նկարագիրը


Համակարգիչը հանդիսանում է հաշվողական գործընթացների իրականացման տեսանկյունից մարդու մոդել, այսինքն որոշակի առումներով կապված հաշվողական գործընթացների կազմակերպման հետ համակարգիչը նման օրինակում է մարդուն: Մարդու ուղեղի անալոգը համակարգչի պրոցեսորն է: Մարդու հիշեղության անալոգը համակարգչի հիշողությունն է: Շրջապատող միջավայրից մարդը լսողությամբ, տեսողությամբ, զգացողությամբ և այլ միջոցներով տեղեկատվություն է ստանում: Անալոգ ձևով համակարգիչը տեղեկատվություն է ստանում ներմուծման սարքերի միջոցով: Մարդը շրջապատող միջավայրին տեղեկատվություն է տալիս: Անալոգ ձևով համակարգիչը արտասման սարքերի միջոցով տեղեկատվություն է տալիս շրջապատող միջավայրին: Գարադարանների անալոգը համակարգչի համար ստանդարտ ենթածրագրերի գրադարանն է: Գրադարանների հետ աշխատելու համար կա գրադարանների կատալոգի համանման համակարգչում ևս կան կատալոգներ: Խոսակցական լեզուներին անալոգ համակրգչի համար նախատեսված են ծրագրավորման լեզուներ: Ծրագրավորման լեզուների կառուցվածքը ընդհանուր առմամբ նման է խոսակցական լեզուների կառուցվածքին: Ծրագրավորման լեզվի այբուբենը լատինական այբուբենի տառերն են, 0-9 թվանշանները, գործողության նշանները, փակագծերը և այլ թույլատրելի նիշերը: Ծրագրավորման լեզվի բառերը 2 հիմնական տիպի՝

  • Ծառայողական (ֆիքսված, ստանդարտ) բառեր և իդենտիֆիկատորներ: Ծառայողական բառերը ֆիքսված բառեր են, որոնք ստանդարտ ձևով օգտագործվում են տվյալ լեզվի հրամանների և այլ օբյեկտների գրառման համար: Այդ բառերը ֆիքսված են և փոփոխության ենթակա չեն: Իդենտիֆիկատորը տառերի, թվանշանների և որոշ թույլատրելի նիշերի հաջորդականություն է, որը սկսվում է տառով: Իդենտիֆիկատորը նշանակում է ծրագրավորողը: Նախադասության անալոգը ծրագրավորման լեզվի հրամանն է (օպերատորը):

  • Խոսակցական լեզվի տեքստի անալոգը ծրագիրն է: Խոսակցական լեզուների նման ծրագրավորման լեզուներն ունեն բառակազմական, շարահյուսական, իմաստաբանական օրենքներ: Բառակազմական օրենքները որոշում են թե որ բառերն են թույլատրելի տվյալ լեզվի համար: Շարահյուսական օրենքները որոշում են թե տվյալ հրամանը ընդունելի է արդյոք տվյալ ծրագրավորման լեզվի համար:Իմաստաբանական օրենքը հրամաններին տալիս են իմաստ: Խոսակցական լեզուների նման ծրագրավորման լեզուներն ունեն քերականություն:

Ծրագրավորման լեզուները ունեն որոշակի ընհանուրություններ: Այդ լեզուները մեկը մյուսի նկատմամբ ունեն որոշակի առավելություններ և թերություններ: Յուրքանչյուր ծրագրավորման լեզու իր հնրարավորություններվ հարմար է որոշակի բնագավառի խնդիրների լուծման համար:

Բոլոր ծրագրավորման լեզուները ունեն տվյալների ներմուծման, արտածման, կազմակեպման հնարավորություններ: Բոլոր լեզուներում կան հրամանների հաջորդական կազմակերպում (վերագրաման օպերտոր): Բոլոր լեզուներում կան ճյուղավորում և ցիկլիկ կազմակերպման հնարավոություն: Կա ենթածրագրեր (ֆունկցիաներ, պրոցեդուրաներ) կազմակերպելու հնարավորություն:



Ավտոմատների տեսության ներածություն

Ավտոմատների տեսությունը և բարդության տեսությունը կազմում են ինֆորմացիայի միջուկի ամենակարևոր մասերը: Վերջավոր ավտոմատները հանդիսանում են սարքավորումներ և ծրագրային ապահովումների շատ բաղադրիչների մոդելներ: Դիտարկենք “միացված-անջատված” փոխարկիչի (հոսանքափոխարկիչի) ավտոմատային մոդելը: Փոխարկիչն ունի երկու վիճակ՝ միացված և անջատված: Նար սկզբնական վիճակն անջատված վիճակն է: Սարքը յուրաքանչյուր պահի հիշում է իր վիճակը: Կատարվող հիմնական գործողությունը կոճակը սեխմելու գործողությունն է: Եթե սարքը գտնվում է անջատված վիճկում և կատարվում է կոճակի սեղմում գործողությունը, ապա սարքն անցնում է միացված վիճակի և հակառակը, եթե սարքը գտնվում է միացված վիճակում, ապա կոճակի սեղմում գործողության կատարման արդյունքում սարքն անցնում է անջատված վիճակի: Փոխարկիչ սարքի ավտոմատային մոդելը հետևյալն է՝


Սեղմում

Սեղմում


Սկիզբ

Միաց

Անջ.











Սովարաբար ավտոմատի վիճակների մեջ ֆիքսվում է որոշ վիճակներ, որոնց անվանում են եզրափակիչ կամ թույլատրելի վիճակներ: Եզրափակիչ վիճակները ընդունված է նշել կրկնակի շրջանակներով: Փոխարկիչ սարքի համար եզրափակիչ վիճակ կարող է լինել միացված վիճակը, քանի որ այդ վիճակը ազդարարում է փոխարկչին միացվածսարքավորման աշխատանքի սկսվելը: Գործողությունների հաջորդականությունը, որը բերում է ավտոմատի եզրափակիչ վիճակի կանվանենք գործողություների լավ հաջորդականություն: Ավտոմատները կարող են հանդիսանալ բառապաշարային վերլուծիչի (անալիզատոր) բաղադրիչ մաս: Օրինակ՝ ներկայացնենք ավտոմատ, որը ճանաչում է then բառը: Այդ ավտոմատը հետևյալն է՝


then

the

th

t

then

the

th

t

Սկիզբ








Վերջավոր ավտոմատները հանդիսանում են հաշվարկելիության սահմանների վերլուծության կարևոր գործիք: Համկարգչի համար կան երկու հիմնական պրոբլեմ՝

  1. Ի՞նչ կարող է անել համակարգիչը:

  2. Համակարգիչը ի՞նչ կարող է անել արդյունավետ ձևով:

Առաջին պրոբլեմը խնդիրների լուծելիության պրոբլեմն է: Այն խնդիրները որոնք հնարավոր է լուծել համակարգչով անվանում են լուծելի խնդիրներ: Այս պրոբլեմի հարցերով է զբաղվում ալգորիթմների տեսություն առարկան: Երկրորոդ պրոբլեմը խնդիրների հեշտությամբկամ ոչ հեշտությամբ լուծելու պրոբլեմն է: Ընդհանրապես համակարգչով խնդրի լուխման համար անհրաժեշտ ժամանակը ֆունկցիա է կախված խնդրի մուտքային տվյալների կոդի երկարությունից: Եթե այդ ֆունկցիան կոդի երկարությունից ունի բազմանդամային տեսքի կավածություն, ապա խնդիրն անվանում են հեշտ լուծվող խնդիր: ԲԱզմանդամության ֆունկցիան արգումենտից կախված բավականաչափ դանդաղ աճող ֆունկցիա է: Եթե այդ ֆունկցիան կոդի երկարությունից կախված ավելի արագ աճող ֆուննկցիա է քան կամայական բազմանդամ ապա համապատասխան խնդիրը անվանում են դժվար լուծվող խնդիր:



Վերջավոր ավտոմատների հիմնական գաղափարները

Վերջավոր ավտոմատների վերաբերող հիմնական գաղափարներն են այբուբեն, բառ (շղթա), լեզու: Այբուբենը ոչ դատարկ վերջավոր բազմություն է: Այբուբենը ընդունված է նշանակել ∑ (սիգմա) տառով: Դա այն բազմություննէ, որի միջոցով գրառում են ավտոմատին տրվող տվյալները: Այբուբենի օրինակ են՝ ∑ = {0,1}, ∑ = {a,b…x,y,z}:

Բառեր

Բառը այբուբենի տարրերի (տառերի, նիշերի) վերջավոր հաջորդականություն է: Դատարկ կանվանենք այն տառը, որը չի պարունակում ոչ մի նիշ, այդ նշանակում է: Բառի երկարություն կանվանենք նրա այն դիրքերի քանակությունը, որոնցում այբուբենի նիշերն են գրված (բառի մեջ գրառված տառերի քանակը, հաշվի առնված պատիկություններով): Այբուբենի տառի պատիկությունը բառի մեջ այդ տառի հանդիպումների քանակն է: Նշենք ∑ այբուբենի բոլոր k երկարությամբ բառերի բազմությունը՝ ∑k: Նշենք ∑+ -ով, ∑ այբուբենի բոլոր ոչ դատարկ բառերի բազմությունը: ∑* նշանակենք ∑ այբուբենի բոլոր բառերի բազմությունը: Սահմանունից հետևում է՝

+ = ∑1 2 3

∑* = ∑+ {ε}


Բառերի կոնկատենցիա

x,y ∑* բառերի կոնկատենացիա (կցում), որը կնշանակենք xy տեսքով, կանվանենք այն բառը որը ստացվում է x բառին աջից կցագրելով y բառը:

Լեզուներ

∑ այբուբենում լեզու կանվանենք ∑* բառերի բազմության յուրաքանչյուր L ∑* ենթաբազմության: Լեզուները ակրելի է ճանաչել վերջավոր ավտոմատների միջոցով, քերականությունների միջոցով: Լեզուները կարելի է ներկայացնոլ բազմությունների տրման եղանակով, ամսնավորապես լեզուն կարելի է ներկայացնել որոշակի հատկությունների բավարարող տարրերի բազմության ներկայացման հետևյալ եղանակով: Այդ ներկյցման եղանակը հետևյալն է՝ A = {x | պայաման}: Կարդում ենք հետևյալ կերպ A-ն բոլոր և միայն այն x տարրերի բազմություննէ, որտեղ (|) կատարված է գծիկից հետո գրված պայմանը: Այլ կերպ ասած A-ն բոլոր և միայն այն x տարրերի բազմություննէ, որոնք բավարարում են գծիկից հետո գրված պայմանում: Լեզվի օրինակներ են՝

L = {0n1n | n≥0}

L = ∑*

L = {ε} դատար բառը պարունակող լեզու

Պայմանավորվենք այբուբենի տառերը նշել լատինական այբուբենի սկզբի փոքրատառերով՝ a,b,c, իսկ բառերը նշանակել այբուբենի վերջին տառերով՝ W,X,Y,Z: W բառի երկարությունը նշանակենք՝ : W բառը կանվանենք դատարկ բառ, եթե՝ =0:

Պրոբլեմներ

Ավտոմատներին վերաբերող տեսության մեջ լեզուների տեսանկյունից պրոբլեմ անվանում են հետևյալին՝ տրված է ∑ այբուբենում W բառը, պահանջվում է պարզել W բառը պատկանում է արդյոք L լեզվին (L ∑*) թե ոչ:



Դետերմինացված վերջավոր ավտոմատներ


Ավտոմատը ժամանակի յուրաքանչյուր պահի գտնվում է որոշակի վիճակում, այն մուտքում ստանում է մուտքային այբուբենի բառ հերթականությամբ ձախից աջ դիտարկում է բառում եղած տառերը և յուրաքանչյուր տառ դիտարկելուց հետո որոշակի օրենքով փոխում է իր վիճակը: Դետերմինացված վերջավոր ավտոմատը ժամանակի յուրաքանչյուր պահին գտնվում է մեկ վիճակում, այլ կերպ ասած դետերմինացված ավտոմատը գտնվելով որևէ ընթացիկ վիճակում և այդ վիճակում դիտարկելով բառի հերթական տառը անցնում է միայն մեկ վիճակի: Ոչ դետերմինացված ավտոմատը ժամանակի յուրաքանչյուր պահի կարող է գտնվել մի քանի վիճակներում: Տանք դետերմինացված վեջավոր ավտոմատի մաթեմատիկական սահմանումը: Ենթադրենք տրված է`

  1. վիճակների վերջավոր բազմություն, որը նշանակենք Q

  2. տրված է ոչ դատարկ մուտքի այբուբեն, որը նշանակենք՝ ∑

  3. տրված է δ(դելտա) արտապատկերում, որը ցույց է տալիս թե տվյալ վիճակում տվյալ տառը կարդալիս ավտոմատը ինչ վիճակի է անցնում, այլ կերպ ասած տրված է՝ δ:Q×∑ Q:

  4. տրված է q0 սկզբնական վիճակ

  5. տրված է F բազմություն, որտեղ F-ը ենթաբազմություն է Q-ից՝ F⊆Q

(Q,∑,δ, q0,F) հնգյակը կանվանենք դետերմինացված վերջավոր ավտոմատ և կնշանակենք A = (Q,∑,δ,q0,F) ( կամ կնշանակենք (Q,∑,δ,F) ): Նկարագրենք ավտոմատի աշխատանքը մուտքի այբուբենի a1a2…an բառի վրա: Ավտոմատը ճիշտ սկսում է աշխատանքը սկզբնական q0 վիճակը: q0 վիճակով դիտարկվում է բառի ամենաձախ a1 տառը, որից հետո անցնում է δ(q0, a1), որը նշանակենք q1, q1= δ(q0, a1): q1 վիճակով դիտարկում է a2 տառը անցնում է q2= δ(q1, a2), այսպես շարունակ ավտոմատը qn-1 վիճակով դիտարկում է an տառը անցնում է qn = δ(qn-1, an) վիճակի: Ավտոմատն ավարտում է աշխատանքը հենց որ հանդիպում է դատարկ նիշի (հենց որ բառի տառերը ավարտվում են): Եթե qn F ապա a1a2…an բառը թույլատրելի է ավտոմատի համար: Եթե qn F, ապա a1a2…an բառը թույլատրելի չէ ավտոմատի համար:

Ավտոմատի լեզու կանվանենք բոլոր և միայն ավտոմատի համար թույլատրելի բառերի բազմությունը:

Օրինակ՝ Դիտարկենք այն լեզուն, որը բաղկացած է 0-ներից և 1-երից, և իր մեջ պարունակում է 01 զույգը: Այս լեզուն կարելի է ներկայացնել հետևյալ կերպ`

L = {W | W=X01Y X,Y 0,1} :

Այդ լեզուն կարելի է ներկայացնել նաև հետևյալ կերպ՝

L = { X01Y | X,Y 0,1}

Այս լեզվի բառերը թույլատրելի են հետևյալ ավտոմատի համար (այս լեզուն ճանաչելի է հետևյալ ավտոմատի կողմից՝ A = ({q0, q1, q2}, {0,1}, δ, q0, { q1}) ):

δ վիճակի անցումն (կամ փոփոխումն) որոշվում է հետևյալ կերպ՝

δ(q0, 1) = q0

δ(q0, 0) = q2

δ(q2, 0) = q2

δ(q2, 1) = q1

δ(q1, 0) = q1

δ(q1, 1) = q0




Դետերմինացված վերջավոր ավտոմատի տրման եղանակները

Դետերմինացված ավտոմատի տրման եղանակներից , ավտոմատի ուրվապատկերով ներկայացման և աղյուսակով ներկայացման եղանակները: Տրված է ՝ A = (Q,∑,δ,q0,F) F⊆Q, ուրվապատկերի ներկայացումը՝

  1. գագաթների Q բազմության, յուրաքանչյուր q գագաթին համապատասխան շրջանակի ներսում գրելով այդ վիճակը: Պատկերել այնպես, որ շրջանակները հատում չունենան

  2. յուրաքանչյուր p= δ(q, a) համապատասխանության համար q գագաթին համապատասխան շրջանակը ուղղորդված աղեղով միացնում ենք p գագաթին համապատասխան շրջանակին ուղղությունն ընտրելով q գագաթից դեպի p գագաթ և աղեղի վրա գրելով a նիշը: Եթե q վիճակից p վիճակին կան անցումներ մի անի նիշերի համար, ապա a-ի վրա գրում ենք այդ նիշերի հավաքածուն:

  3. Սկզբանական վիճակի ուղղված սլաք ենք նշում, որի վրա գրում ենք սկիզբ, այդ սլաքը ոչ մի գագաթից դուրս չի գալիս:

  4. Ավտոմատի թույլատրելի վիճակները նշում են կրկնակի շրջանակներով, իսկ ոչ թույլատրելի վիճակները նշում ենք մեկ շրջանակով: 0 և 1 թվանշաններից կազմված 01 զույգը պարունակող բառեը թույլատրելի են ուրվապատկերով ներկայացվող հետևյալ ավտոմատի համար:

Սկիզբ




101000 (բառը ճանաչում է)


111100 (բառը չի ճանաչում)



Դետերմինացված ավտոմատին ներկայացումը աղյուսակի միջոցով:

Աղյուսակի միջոցով ավտոմատի ներկայացման համար ընտրում ենք աղյուսակ, որի տեղերի քանակը հավասար է (վիճակների քանակին հավասար տողեր): Սյուների քանակը հավասար է մուտքի այբուբենի նիշերի քանակին՝ ∑: Աղյուսակի համապատասխան վանդակերում նշվում է վիճակների անցման δ արտապատկերումը: Տողերը նշվում են վիճակներով, սյուները նշվում են ∑ այբուբենի տառերով: Ենթադրենք Q = {q0, q1, …qr} ∑ = { a1,a2,…,an }: Այդ դեպքում աղյուսակը կլինի հետևյալը՝



Սկզբնական սիմվոլը նշում ենք սլաքով: Թույլատրելի (եզրափակիչ) վիճակները նշում ենք աստղանիշով՝ *: Աղյուսակում qi տողի և Qj սյան հատման տեղում գրում ենք δ(qi, aj) վիճակը: Աղյուսակով ներկայացնենք ավտոմատ, որի համար թույլատրելի են 0,1 թվանշաններից կազմված 01 զույգը պարունակող բառեր:


Դետերմինացված ավտոմատի վիճակի անցման ֆունկցիայի ընդհանրացումը


Դիտարկենք կամայական A = (Q,∑,δ,q0,F) ավտոմատը: Ավտոմատի լեզուն ∑ մուտքի այբուբենի բոլոր այնբառերի բազմությունն , որոնք ավտոմատը ուրվապատկերի միջոցով ներկայացնելիս ստացվում են սկզբնական վիճակը թույլատրելի վիճակների միացնող ճանապարհների աղեղների վրա գրված նիշերը հաջորդաբար իրարա կցելով:


xm

x2

x1

Սկիզբ


Ավտոմատի լեզուն խիստ սահմանելու համար նախ սահմանենք վիճակի անցման δ ֆունկցիայի ընդհանրացումը, որը կնշանակենք՝ : Եթե δ-ն հետևյալ տեսքի արտապատկերում է՝ δ:Q×∑ Q: արտապատկերումը հետևյալ տեքսի է՝ :Q×∑* Q: Մաթեմատիկական ինդուկցիայի մեթոդով սահմանենք անցման ըհանրացված ֆունկցիայի գաղափարը:

Բազիս: (q,ε)=q

Ինդուկցիա: Դիցուք W բառը ունի W = xa ներկայացումը, որտեղ a-ն ∑ մուտքի այբուբենի տառ է, իսկ x-ը մուտքի այբուբենի բառ: Այդ դեպքում : (q,W) = δ( (q,x), a): Սա նշանակաում է, որ եթե (q,x)=p ապա (q,W) = δ(p,a): Օրինակ՝ դիցուք L լեզուն L={w | W կազմված է 0-ներից և 1-երից, որտեղ 0-ների և 1-երի քանակը զույգ են}: ԿԱռուցենք ավտոմատ որ համար այս լեզուն թույլատրելի է:

Ընտրենք հետևյալ վիճակները՝

q0 – Դիտարկված է զույգ 0, զույգ 1

q1 – Դիտարկված է զույգ 0, կենտ 1

q2 – Դիտարկված է կենտ 0, զույգ 1

q3 – Դիտարկված է կենտ 0, կենտ 1

Պահանջվող ավտոմատը կլինի հետևյալը՝

A = ({q0, q1,q2, q3,}, {0,1}, δ, q0, {q0}): Այս ավտոմատը ուրվապատկերով կներեկայացվի հետևյալ կերպ՝

Դիտարկենք 110101 բառը: Այն ավտոմատի համար թույլատրելի բառ է, դա նշանակում է, որ (q0, 110101)= q0: վիճակի ընդհանրացված ֆունկցիայի անցումները դիտարկենք 110101 բառի վրա:

(q0,ε) = q0

(q0,1) = δ( (q0,ε),1) = δ(q0,1) = q1

(q0,11) = δ( (q0,1),1) = δ(q1,1) = q0

(q0,110) = δ( (q0,11),0) = δ(q0,0) = q2

(q0,1101) = δ( (q0,110),1) = δ(q2,1) = q3

(q0,11010) = δ( (q0,1101),0) = δ(q3,0) = q1

(q0,110101) = δ( (q0,11010),1) = δ(q1,1) = q0



Դետերմինացված ավտոմատի սահմանումը

Ավտոմատի լեզվի սահմանումը: Դիտարկենք կամայական դետերմինացված ավտոմատ A = (Q,∑,δ,q0,F): Այս ավտոմատի կողմից թույլատրելի լեզուն նշանակենք՝ L(A): L(A) լեզուն սահմանվում է հետևյալ կերպ՝ L(A) = {W | (q0,W) F} (A ավտոմատի L(A) լեզուն բոլոր և միայն այն W բառերի բազմությունն է, որոնց վրա q0 սկազբնական վիճակով աշխատելով արդյունքում ավտոմատն անցնում է F-ի թույլատրելի վիճակի): Եթե L լեզվի համար գոյություն ունի A = (Q,∑,δ,q0,F) ավտոմատը, այնպես որ L = L(A), ապա L լեզուն կանվանենք կանոնական լեզու:



Ոչ դետերմինացված վերջավոր ավտոմատներ


δ(q0,0) = {q0, q1}

Դետերմինացված ավտոմատը յուրաքանչյուր պահիկարող է գտնվել մեկ վիճակում, այսինքն հերթական վիճակում տառ կարդալիս նա անցնում է մեկ վիճակի: Ոչ դետերմինացված ավտոմատը յուրաքանչյուր վիճակում յուրաքանչյուր տառ կարդալիս անցնում է վիճակների բազմության: Վիճակների այդ բազմությունը կարող է պարունակել զրո հատ, 1 հատ, n հատ տարրեր, հետևաբար ոչ դետերմինացված ավտոմատը ժամանակի յուրաքանչյուր պահին կարող էգտնվել մի քանի վիճակում: Ապացուցվում է, որ յուրաքանչյուր ոչ դետերմինացված ավտոմատի կարելի է համապատասխանեցնել դետերմինացված ավտոմատ, որը ճանաչի նույն լեզուն, որը ճանաչի նույն լեզուն, որը ճանաչում է ոչ դետերմինացված ավտոմատը: Սակայն համապատասխանեցվող ավտոմատը կարող է ունենալ էկսպոնենցիալ քանակով վիճակներ: Օրինակ՝ կառուցենք ավտոմատ, որը ճանաչում է 0,1 թվանշաններից կազմ,ված բոլոր, և միայն այն բառերի բազնությունը, որոնց մ,եջ 01 զույգն է գրված: Այդ ավտոմատի ուրվապատկերը հետևյալն է՝

Սկիզբ

Վերջավոր ոչ դետերմինացված ավտոմատի սահմանումը


Վերջավոր ոչ դետերմինացված կանվանենք հետևյալ հնգյակը՝ (Q,∑,δ,q0,F), և կնշանակենք՝ A = (Q,∑,δ,q0,F), որտեղ Q-ն ավտոմատի վիճակների բազմությունն է, ∑-ն մուտքի այբուբենը (Q-ն և ∑-ն վերջավոր բազմություններ են), δ-ն վիճակի փոփոխման արտապատկերումն է, q0-ն սկզբնական վիճակը, F-ը Q բազմության ենթաբազմություննէ, որն անվանում են եզրափակիճ կամ թույլատրելի վիճակի բազմություն: Դետերմինացված և ոչ դետերմինացված ավտոմատների միակ տարբերությունը կայանում է միայն δ արտապատկերման մեջ: Եթե դետերմինացած ավտոմատի դեպքում δ արտապատկերման արգումենտները q Q վիճակի է և a ∑ այբուբենի տառ և արտապատկերման արժեքը Q բազմության վիճակ է, ապա ոչ դետերմինացված ավտոմատի դեպքում արգումենտները նմանատիպ են δ արտապատկերման արդյունքը ոչ թե վիճակ է այլ վիճակների բազմություն, որը Q բազմության ենթաբազմությունն է: Այլ կերպ ասած ոչ դետերմինացված ավտոմատի վիճակի անցման δ արտապատկերումը հետևյալ տեսքի արտապատկերում է՝ δ:Q×∑ 2Q: 2Q հասկանում ենք Q բազմության բոլոր ենթաբազմությունների բազմությունը:

Կառուսենք {0,1} այբուբենի 01 զույգով ավարտվող բառերի բազմությունը ճանաչող ավտոմատի համապատասխան աղյուսակը:


Սկիզբ







0

1



{q0, }






*










Ոչ դետերմինացված ավտոմատի վիճակի անցման ֆունկցիայի ընդհանրացումը


Ոչ դետերմինացված ավտոմատի թույլատրելի լեզվի սահմանման համար նախ սահմանենք նրա վիճակի անցման արտապատկերման ընդհանրացման գաղափարը: Ոչ դետերմինացված ավտոմատի վիճակի անցման ընդհանրացված արտապատկերումը կնշանակենք՝ : Այն վիճակի և մուտքի այբուբենի բառի զույգին համապատասխանեցնում է վիճակների բազմության բազմություն: Այլ կերպ ասած այն հետևյալ տեսքի արտապատկերում է՝ : Q × ∑* 2Q: Այսինքն q վիճակին և W ∑* ենթաբազմության (q1,W) զույգին համապատասխանում է S⊆Q վիճակների բազմություն՝ (q,W) = S:

Ինդոկտիվ եղանակով սահմանենք ոչ դետերմինացված ավտոմատի վիճակի անցման ֆունկցիայի ընդհանրացված գաղափարը:

Բազիս: (q,ε) = {q}

Ինդուկցիա: W = xa, որտեղ a-ն ∑ այբուբենի տառ է, իսկ x-ը ∑* բառ է: Սահմանենք (q,W) արտապատկերման արժեքը: Ենթադրենք (q,x){r1,r2,…rk} այդ դեպքում (q,W) = (ri,a):

Դիտարկենք {0,1} այբուբենի 01-ով ավարտվող բառերի բազմությունը ճանաչող ավտոմատը և դիտարկենք նրա արտապատկերման արժեքների փոփոխությունը 00101 բառի վրա՝

(q0,ε) = {q0}

(q0,0) = δ(q,0) = { q0,q1}

(q0,00) = δ(q0,0) δ(q1,0) = { q0,q1} = { q0,q1}

(q0,001) = δ(q0,1) δ(q1,1) = { q0} {q2} = { q0,q2}

(q0,0010) = δ(q0,0) δ(q2,0) = { q0,q1} = { q0,q1}

(q0,00101) = δ(q0,1) δ(q1,1) = { q0} {q2} = { q0,q2}





Ոչ դետերմինացված ավտոմատի թույլատրելի լեզուն


Ոչ դետերմինացված ավտոմատը W բառը ճանաչում է (W թույլատրելի է ավտոմատի համար) եթե q0 սկզբնական վիճակով W բառի աջից վերջին տառը դիտարկելուց հետո ավտոմատի ստացված վիճակների մեջ կա գոնե մեկ հատ թույլատրելի (եզրափակիչ) վիճակ: A = (Q,∑,δ, q0,F) այդ ավտոմատի լեզու, որը կշանակենք L(A) կանվանենք հետևյալը՝

L(A) = {W | (q0,W) F }





Կանոնական արտահայտություններ և լեզուներ


Կանոնական արտահայտություններ: Դետերմինացված և ոչ դետերմինացված վերջավոր ավտոմատները լեզուների ներկայացման համար օգտագործման եղանակից անցնենք լեզուները կանոնական արտահայտությունների միջոցով ներկայացնելով: Ցույց տանք, որ ավտոմատների միջոցով ներկայացվող ցանկացած լեզու, այսինքն ցանկացած կանոնական լեզու կարելի է ներկայացնել կանոնական արտահայտությունների միջոցով: Կանոնական արտահայտությունները օգտագործվում են որպես բառեր մշակող բազմաթիվ համակարգերի մուտքային լեզու: Օրինակ դիտարկենք Lex և Flex բառապաշարային անալիզատորների գեներատորները, որոնք հանդիսանում են կոմպիլյատորի բաղադրիչ և մուտքային ծրագիրը տրոհում ենք առանձին փոքր բաղադրիչների, որոնք հանդիսանում են նիշերի հաջորդականություն և ունեն որոշակի իմաստ, որոնց անվանում են լեքսեմներ: Լեքսեմների օրինակներ են բանալիային բառերը, օրինակ՝ while և իդենտիֆիկատորները: Բառապաշարային անալիզատորները ստանում են լեքսեմների ֆորմալ (ձևայնացված) նկարագրությունը և ստեղծում են ավտոմատ, որը ճանաչում է մուտքում ստացված լեքսեմները:


Կաանոնական արտահայտությունների օպերատորները: Կանոնական արտահայտությունների միջոցով ստացվում են (տրվում են, ներկայացվում են) լեզուներ, որպես օրինակ դիտարկենք 01*+10* կանոնական արտահայտությունը: Այս կանոնական արտահայտության միջոցով տրվում է այն լեզուն, որը բաղկացած է մեկ հատ զրոյիցև նրան հաջորդող մեկերից բաղկացած կամ մեկ հատ մեկից և նրանց հաջորդող զրոներից բաղկացած բառերից:

Կան կանոնական արտահայտությունների համար երեք օպերատորներ և այդ կանոնական արտահայտություններին համապատասխան լեզուների համար երեք գործողություններ՝

  1. L, M լեզուների միավորում, որը կնշանակենք՝ L M տեսքով, կանվանենք բոլոր այն բառերի բազմությունը, որոնք պատկանում են L բազմությանը կամ M բազմությանը:

  2. L, M լեզուների կոնկատենացիա կամ կցում, որը կնշանակենք L•M կամ (LM), կանվանենք բոլոր այն բառերի բազմությունը, որոնք ստացվում են L լեզվի բառերի աջից կցելով M լեզվի բառեր:

  3. L լեզվի իտերացիա (կրկնում), որը կնշանակենք L*, կանվանենք բոլոր այն բառերի բազմությունը, որոնք ստացվում են L լեզվի վերջավոր թվով բառեր իրար կցելով:


Կանոնական արտահայտությունների կառուցումը: Ցանկացած հանրահաշիվ սահմանելու համար նախ սահմանվում են տարրական արտահայտություններ, հաստատուններ և փոփոխականններ, այնուհետև օպերատորների միջոցով տարրական արտահայտություններից կամ արդեն ստացված արտահայտություններից սահմանվում են ավելի բարդ արտահայտություններ: Արտահայտություններ սահմանելիս օգտագործում են նաև փակագծեր: Այս ձևով է սահմանվում նաև թվաբանության հանրահաշիվը նման ձևով է սահմանվում նաև կանոնական արտահայտությունների հանրահաշիվը:

Բազիս: Բաղկացած է երեք կետերից՝

  1. ε և հաստատունները հանդիսանում են կանոնական արտահայտութնուններ, որոնք համապատասխանաբար լեզուներն են՝ L(ε) = {ε} և L( ) = (E կանոնական արտահայտության համապատասխան լեզուն նշանակում են L(E)-ով):

  2. Եթե a-ն կամայական նշան է ապա այն կանվանենք կանոնական արտահայտություն, կնշանակենք՝ a: a կանոնական արտահայտության համապատասխան լեզուն է՝ L(a) = {a}:

  3. Ընդունված է լեզուները նշանակել լատինական այբուբենի մեծատառ տեսքով:

Ինդուկցիա: Բաղկացած է չորս կետից: Առաջին երեք կետերը վերաբերում են կանոնական արտահայտությունների օպերատորներին, իսկ չորրորդ կետը վերաբերում է փակագծերի օգտագործմանը:

  1. E, F կանոնական արտահայտությունների միավորում կնշանակենք E+F տեսքով: Նրան համապատասխան լեզուն որոշվում է հետևյալ կերպ՝ L(E+F) = L(E) L(F):

  2. E, F կանոնական արտահայտությունների կոնկատենացիա կնշանակենք E•F կամ (EF) տեսքով: Նրան համապատասխան լեզուն որոշվում է հետևյալ կերպ՝ L(EF) = L(E)•L(F):

  3. E կանոնական արտահայտության իտերացիա կնշանակենք E* և նրան համապատասխան լեզուն որոշվում է հետևյալ կերպ՝ L(E*) = (L(E))*:

  4. E կանոնական արտահայտության կանոնական արտահայտություն է նաև` (E), այն որոշում է նույն L(E) լեզուն՝ L((E)) = L(E):


Կանոնական արտահայտությունների նախապատվություն (приоритет): Ամենամեծ նախապատվություն ունի իտերացիայի * օպերատորը: Հաջորդ նախապատվելի գործողությունը իտերացիայից հետո համարվում է կոնկատենացիա՝ • : Այնուհետև + գործողությունը: Փակագծերը մտցվում են լրացուցիչ նախապատվություն, այսինքն սկզբից կատարվում են փակագծերում տրված օպերատորի հավաքածուն այնուհետև նրանից դուրս նշած օպերատորները:











Կոնտեքստից ազատ քերականություններ


Կոնտեքստից ազատ քերականությունը իրենից ներկայացնում է G = (N,T,P,S) քառյակը, որտեղ՝

  1. T-ն իրենից ներկայացնում է քերականությանը համապատասխան լեզվի այբուբեն, այսինքն այբուբեն, որի նիշերի միջոցով գրառվում են տվյալ լեզվի բառերը: T-ն անվանում են տերմինալների բազմություն:

  2. N-ը ոչ տերմինալների (փոփոխականների) բազմություն է: Ոչ տերմինալները լեզվին համապատասխան բառեր ստանալիս օգտագործվում են որպես միջանկյալ նիշեր: Ոչ տերմինալները լեզվի բառերի գրառման նիշեր չեն և N T= :

  3. P-ն կանոնների բազմություն է, որոնց միջոցով արտածվում են լեզվին համապատասխան բառերը: Յուրաքանչյուր կանոն բաղկացած է երեք մասից՝
    ա) ամենաձախ մասում կանոնի գրվում է ոչ տերմինալային նիշ
    բ) ոչ տերմինալային նիշին հաջորդում է՝ նիշը:
    գ) նիշին աջից հաջորդում է տերմինալներից և ոչ տերմինալներից կազմված բառը:

  4. S նիշն անվանում են սկզբնական նիշ, այն ոչ տերմինալային նիշ է՝ S N:

Քերականությունը օգտագործվում է լեզվի բառերը ճանաչելու համար: Քերականության հասկացությունը օգտագործվում է լեզվի շարահյուսական վերլուծության համար կոմպիլյատորների մեջ:



Քերականությունների օրինակներ

Օրինակ 1: Կառուցենք քերականություն որով տրվում է պոլինդրոմ բառերից կազմված լեզուն: Պոլինդրոմ բառերը այն բառերն են, որոնց ձախից աջ և աջից ձախ կարդալիս նույն բառն է ստացվում: Կդիտարկենք միայն 0 և 1 թվանշաններից բաղկացած պոլինդրոմ բառերը: Որպես ոչ տերմինալների բազմություն ընտրենք N = {S}, որպես տերմինալների բազմություն ընտրենք T = {0,1}, որպես սկզբնական նիշ ընտրենք S-ը, որպես օրենքների (կանոնների) P բազմություն ընտրենք հետևյալը՝ S
1, S :
Օրինակ՝ 11110001111
S

Օրինակ 2: Կառուցենք քերականություն, որը ճանաչում է թվաբանական արտահայտություններից կազմված լեզուն: Թվաբանական արտահայտություններում ենթադրում ենք, որ օգտագործվում է +,* նշանները, (,) փակագծերը, a և b տառերը, 1 և 0 թվանշանները: Ենթադրում ենք, որ արտահայտություններում կարելի է օգտագործել իդենտիֆիկատորներ, իսկ իդենտիֆիկատորը տառերի թվանշանների հաջորդականություն է, որ սկսվում է տառով: Որպես տերմինալների բազմություն ընտրենք՝ T = {1; 0; a; b; (; ); +; *}: Որպես ոչ տերմինալների բազմություն ընտրենք` N = {E, I}, որպես սկզբնական նիշ ընտրենք E-ն: Կանոների P բազմությունը կլինի հետևյալը՝

E I I a I Ia
E E+E I b I Ib

E E*E I I0
E (E) I I1




Պահանջվող լեզվին համապատասխան քերականությունը կլինի նշված N,T,P բազմությունների և S-ի G = (N,T,P,S) քառյակը: Օրինակ՝ (a1*(a+b))
E E + E



Ավտոմատը, որպես հաշվիչ մեքենայի մաթեմատիկական մոդել

Հիմնական գաղափարներ: Ավտոմատները իրենցից ներկայացնում են որոշակի դասի հաշվիչ մեքենաների մաթեմատիկական մոդելներ, որոնք բավարարում են հետևյալ սկզբունքներին՝

  1. Նրանցում ամեն ինչ կատարվում է ժամանակի առանձին պահերի, իսկ այդ պահերի միջև ընկած ժամանակահատվածում ոչինչ չի կատարվում: Ժամանակի այդ պահերը կնշանակենք 0,1,2...

  2. Մեքենան ունի մուտքի սարք, որով արտաքին միջավայրը ազդում է նրա վրա: Մոտքի սարքի վիճակների բազմությունը վերջավոր է:

  3. Մեքենանա ունի ելքի սարք, որով նա ազդում է արտաքին միջավայրի վրա: Ելքի սարքի վիճակների բազմությունը վերջավոր է:

  4. Մեքենան ունի ղեկավարող սարք, որը ղեկավարում է նրա ամբողջ աշխատանքը: Ղեկավարող սարքի վիճակների բազմությունը վերջավոր է:

  5. Ժամանակի յուրաքանչյուր t = 0,1,2… պահի մեքենայի ելքի վիճակը որոշվում է t պահին մեքենայի (ղեկավարող սարքի ) վիճակով և մեւտքի սարքի վիճակով:

  6. Ժամանակի յուրաքաչյուր t = 1,2... պահի մեքենայի վիճակը որոշվում է t-1 պահին մեքենայի վիճակով և մուտքի սարքի վիճակով:

Այդ մեքենան կարելիէ ներկայացնել հետևյալ սծեմայով՝


Ե

Մ

Ղեկավարող սարք

Որտեղ Մ-ն մուտքի սարքն է, Ե-ն՝ ելքի սարքը:

Տանք ավտոմատի մաթեմատիկական սահմանումը: Դիցուք տրված են A = {a1,a2,...an} վերջավոր բազմությունը, որը կանվանենք մուտք այբուբեն: B = {b1,b2,...bn} վերջավոր այբուբենը, որը կանվանենք ելքի այբուբեն: Q = {q1,q2,...qn} վերջավոր բազմությունը, որը կանվանենք ներքին վիճակների բազմություն: Տրված են` λ:Q×A Q և δ:Q×A B արտապատկերումը:

A, B,Q բազմությունների և λ,δ արտապատկերումների հնգյակը ֆիքսված q0 սկզբանական վիճակով կանվանենք ավտոմատ և կնշանակենք՝ (A,B,Q,λ,δ): Նկարագրենք ավտոմատի աշխատանքը մուտքի A այբուբենի X0X1...Xs բառի վրա: Ավտոմատը սկսում է աշխատանքը q0 սկզբնական վիճակով: q0 վիճակում նա կարդում է X0 տառը t = 0 պահին, այդ պահին ավտոմատի ելքի վիճակն է y0 = δ (q0,x0), ժամանակի t=1 պահին ավտոմատի վիճակն է՝ q(1) = λ(q0,x0): Այդ վիճակում ավտոմատը կարդում է x1 տառը, այդ պահին նրա ելքի վիճակն է՝ y1 = δ (q(1),x1): Ժամանակի t = 2 պահին ավտոմատի վիճակն է՝ q(2) = λ(q(1),x1): Այսպես շարունակ ավտոմատը ուննում է ելքի y2...ys ելքի վիճակներ: Ավտոմատն ավարտում է իր աշխատանքը հենց որ հանդիպոււմ է դատարկ նիշի: y0y1...ys ելքի այբուբենի բառը անվանում են ավտոմատի աշխատանքի արդյունք X0X1...Xs բառի վրա:

Այժմ նկարագրենք ավտոմատի աշխատանքը մեկ այլ ձևով: Ենթադրենք տրված են ձախից վերջավոր և աջից անվերջ երկու ժապավեններ, որոնք բաժանված են բջիջների և այդ բջիջները ձախից աջ համարակալված են 0,1,2… համարներով: Ժապավենները կնշանակենք M1-ով և M2-ով:


Ավտ.


Նկարագրենք ավտոմատի աշխատանքը X0X1...Xs բառի վրա: M1 ժապավենն անվանում են մուտքի ժապավեն, M2-ը՝ ելքի ժապավեն: Ժամանակի t = 0 պահին մուտքի ժապավենի ամենաձախ բջջից սկսած յւրաքանչյուր բջջում մեկական տառով գրված է X0X1...Xs բառը: M1 ժապավենի մնացած բջիջներում և M2 ժապավենի բոլոր բջիջներում գրված է դատարկ նիշ, որը ընդունված է նշանակել՝ ^:

t = 0 պահին ավտմատը կարդում է մուտքի ժապավենի X1 տառը q0 սկզբանակն վիճակում: լքի ժապավենի 0 համարով բջջում գրվում է ելքի այբուբենի y0 տառը, որը որոշվում է հետևյալ կերպ y0 = δ (q0,x0): Ժամանակի t = 1 պահին ավտոմատի վիճակն է՝ q(1) = λ(q0,x0): q(1) վիճակով ավտոմատը կարդում է X1 տառը ելքի ժապավենի 1 համար ունեցող բջջում տպում է y1 = δ (q(1),x1) տառը, շարժվում է մեկ բջջով աջ անցնելով q2 վիճակի: Այսպես շարունակ ժամանակի t = s պահին ավտոմատը qs վիճակում կարդում է Xs տառը և ելքի ժապավենի s համար ունեցող բջջում տպում է ys = δ (q(s),xs) տառը, մեկ բջջով տեղաշարժվում է աջ անցնելով q(s+1) = λ(q(s),xs) վիճակի, հանդիպում է դատարկ բջջի և ավարտում է աշխատանքը: y0y1...ys բառը ավտոմատի աշխատանքի արդյունքն է X0X1...Xs բառի վրա:







Ավտոմատի ներկայացման աղյուսակային

և ուրվապատկերային եղանակները

Քանի որ aqA,B,Q,λ,δ ավտոմատը որոշվում է A,B,Q բզմությունների և λ,δ արտապատկերումների հնգյակի միջոցով, ապա ավտոմատի ներկայացման ցսանկացած եղանակում անհրաժեշտ է տալ այդ հնգյակը: Ավտոմատը կարելի է ներկայացնել հետևյալ աղյուսակի միջոցով՝

A = {a1,a2,...an}

B = {b1,b2,...bn}

Q = {q1,q2,...qn}

Աղյուսակի առաջին մասի qi-ի համապատասխան տողի և aj համապատասխան սյան հատման տեղում գրվում է λ(qi,aj), այսինքն աղյուսակի առաջին մասով տրվում է λ:Q×A Q արտապատկերումը:

Աղյուսակի երկրորդ մասի qi-ի համապատասխան տողի և aj համապատասխան սյան հատման տեղում գրվում է δ(qi,aj), այսինքն աղյուսակի առաջին մասով տրվում է δ:Q×A B արտապատկերումը:

Ավտոմատը կարելի է տալ նաև հետևյալ միացյալ աղյուսակով՝

δ( )
λ( )

Ավտոմատը կարելի է ներկայացնել նաև ուրվապատկերի միջոցով, դրա համար հարթության վրա ավտոմատի վիճակին համապատասխանեցնում ենք զույգ առ զույգ չափվող շրջանակներ, շրջանակների ներսում գրելով վիճակների յուրաքանչյուր λ(qi,aj)=qk համապատասխանության համար qi վիճակի համապատասխանող շրջանակը ուղղորված աղեղով միացենենք qk գագաթին համապատասխան շրջանակի հետ ուղղություն ընտրելով qi-ից դետի qk`


Աղեղ վրա նշելով՝ (ajδ(qi,aj)):

Ավտոմատի օրինակներ:

Օրինակ 1: Կառուցենք ավտոմատ որը 0 և 1 թվանշանների կամայական հաջորդականության յուրաքանչյուր նիշին համապատասխանեցնում է 0 թվանշանը եթե մինչև այդ հանդիպած մեկերի քանակը զույգ է և համապատասխանեցնում է 1 թվանշանը, եթե մինչև այդ հանդիպած մեկերի քանակը կենտ է:


1

0

1

1

1


1

1

0

1

0




Ակնհայտ է, որ այս ավտոմատի համար մուտքի այբուբենը՝ A = {0,1} ելքի այբուբենը՝ B = {0,1}: Որպես վիճակներ ընտրենք qզ, qկ: qզ վիճակը կնշանակի, որ մինչև տվյալ պահը հանդիպած մեկ թվանշնների քանակը զույգ է, իսկ qկ վիճակը կնշանակի, որ մինչև այդ հանդիպած թվանշանների քանակը կենտ է: Որպես սկզբնական վիճակ կընտրենք qզ վիճակը: Ավտոմատին համապատասխան վիճակների բազությունը կլինի Q = { qզ , qկ }: ավտոմատին համապատասխան աղյուսակը կլինի հետևյալը՝



0 1

0 1


qզ

qզ qկ

0 1


qկ

qկ qզ

1 0



Ներկայացնենք ավտոմատին համապատասխան ուրվապատկերը՝

qկ

qզ

Օրինակ 2: Կառուցենք ավտոմատ, որը գումարում է երկուական համակարգի երկու բնական թվեր: Ենթադրենք այդ թվերն են՝ α = α0 α1 …αn և β = β0 β1… βn: Կարող ենք ենթադրել, որ երկու թվեր ունեն հավասար քանակով թվանշաններ, հակառակ դեպքում փոքր թվի առջևից կավելացնենք 0 թվանշաններ: Ենթադրենք նաև, որ թվերի յուրաքանչյուրի ձախից ավելացված է մեկ հատ 0 թվանշանը: Ավտոմատի մուտքին կտրվի՝ (αn, βn), (αn-1, βn-1),…, (α0, β0), հաջորդականությունը: Սա նշանակում է, որ ավտոմատի մուտքի այբուբենը հետևյալ նիշերի բազմությունն՝A = {(0,0), (0,1), (1,0), (1,1)}: Ելքի այբուբենն է՝ B = {0,1}: Որպես վիճակներ ընտրենք q0 և q1, որտեղ q0 վիճակը նշանակում է, որ նախորդ կարգում գումարման արդյունքում փոխանցվել է 0 թվանշանը (թվանշան չի փոխանցվել): q1 վիճակ նշանակում է, որ նախորդ կարգում գումարման արդյունքից փոխանցվել է 1 թվանշանը (թվանշան է փոխանցվել), հետևաբար վիճակների բազմությունը կլինի՝ Q = {q0, q1} : Ավտոմատին համապատասխան աղյուսակը կլինի հետևյալը՝

(0,0) (0,1) (1,0) (1,1)

(0,0) (0,1) (1,0) (1,1)



Կառուցենք ավտոմատի համապատասխան ուրվապատկերը՝



(0,1)(0)

(0,0)(0)

(0,1)(1)

(1,0)(1)

(1,1)(1)

(1,0)(0)

(1,1)(0)

(0,0)(1)








Ճանաչելի և կանոնական իրավիճակներ

Դիտարկենք կամայական ավտոմատ: Նշանակենք A* A այբուբենի բոլոր բառերի բազմությունը: Եթե ավտոմատի աշխատանքի արդյունքը մուտքի այբուբենի x0x1…xs բառի վրա ելքի այբուբենի y0y1…ys բառն է ապա ys-ը կանվանենք x0x1…xs բառի վրա ավտոմատի աշխատանքի արդյունք և կնշանակենք՝ 0x1…xs=ys : Կամայական z⊆A* ենթաբազմությունը A*-ից, կանվանենք իրավիճակ: Կասենք, որ ավտոմատը ճանաչում է z իրավիճակը, եթե հնարավոր է B բազմությունը տրոհել B1 և B2 ենթաբազմությունների (այսինքն B ներկայացնել B1,B2⊆B ենթաբազմությունների միջոցով, որ տեղի ունենա՝ B = B1 B2 և B1 B2 = ) այնպես, որ տեղի ունենա հետևյալ պայմանը՝ x0x1…xs A* բառի համար x0x1…xs z 0x1…xs B1

Սահմանում: z⊆A* իրավիճակը կանվանենք ճանաչելի եթե գոյություն ունի ավտոմատ, որը ճանաչում է այդ իրավիճակը: Ակնհայտ է հետևյալ թեորեմի իրավացիություն:

Թեորեմ: Որպեսզի z⊆A* իրավիճակը լինի ճանաչելի անհրաեշտ է և բավարար, որ գոյություն ունենա ավտոմատ, այնպես, որ x0x1…xs A* բառի համար x0x1…xs z 0x1…xs = “այո”:

Ներկայացնենք որոշ ճանաչելի իրավիճակներ՝

  1. Կամայական A = {a1,a2,…am} այբուբենի համար և A*իրավիճակները ճանաչելի են: Դատարկ իրավիճակը ճանաչող ավտոմատը հետևյալն է՝


a2 (“ոչ”)

an (“ոչ”)

a3 (“ոչ”)

a1 (“ոչ”)

A* իրավիճակը ճանաչող ավտոմատը հետևյալն է՝



a3 (“այո”)

a1 (“այո”)

a2 (“այո”)

an (“այո”)



  1. {a,b} այբուբենում կամայական մեկ բառից կազմված իրավիճակ ճանաչելի է: Այդ մեկ բառը ճանաչող ավտոմատը կառուցվում է հետևյալ սկզբունքով: {a} այս իրավիճակը ճանաչող ավտոմատը կլնի հետևյլաը՝


a (“այո”)


b (“ոչ”)

a (“ոչ”)

b (“ոչ”)





{ab} իրավիճակը ճանաչող ավտոմատը կլինի հետևյալը՝

a (“ոչ”)


b (“այո”)


b (“ոչ”)

a (“ոչ”)

b (“ոչ”)

b (“ոչ”)

a (“ոչ”)

a (“ոչ”)



{a,ab} իրավիճակը ճանաչող ավտոմատը կլինի հետևյալը՝


b (“այո”)

a (“ոչ”)

a (“ոչ”)


b (“ոչ”)

b (“ոչ”)

a (“ոչ”)



  1. Ցույց տանք, որ {0,1} այբուբենի 0 նիշը չպարունակող և կենտ թվով մեկերից կազմված բառերի բազմությունը ճանաչելի իրավիճակ է: Այդ իրավիճակը ճանաչող ավտոմատը հետևյալն է՝

1 (“այո”)



1 (“ոչ”)

0 (“ոչ”)

1 (“ոչ”)

0 (“ոչ”)

0 (“ոչ”)




Սահամնենք որոշ գործողություններ իրավիճակների նկատմամբ: Դիցուք տրված է z1 ⊆ A* և z2 ⊆ A* իրավիճակները՝

  1. z1 և z2 իրավիճակների գումար, որը կնշանակենք՝ z1 z2 , (գումար) կանվանենք այն իրավիճակը, որի յուրաքանչյուր բառ պարունակում է z1 իրավիճակին կամ z2 իրավիճակին:

  2. z1 և z2 իրավիճակների արտադրյալ, որը կնշանակենք՝ z1 • z2 , կանվանենք բոլոր և միայն այն բառերի բազմությունը, որոնք ունեն ԱԲ տեսքը, որտեղ Ա z1 և Բ z2:

  3. z1 իրավիճակի կրկնում (իտերացիա), որը կնշանակենք տեսքով բոլոր և միայն այն բառերի բազմությանը, որոնք ստացվում են z1-ի վերջավոր թվով բառեր իրար կցելով: Կատարենք հետևյալ նշանակումները՝ = z1, = z1• z1•… = • z1: Այս նշանակումները կներկայացվի հետևյալ տեսքով՝ =

Դիտարկենք A = { a1,a2,...an } այբուբենում իրավիճակների մի կարևոր դաս, որը էական դեր է խաղում իրավիճակների ճանաչելիության հարցում: Դա կանոնական իրավիճակների դասն է:

  1. դատարկ իրավիճակը կանոնական իրավիճակ է:

  2. Միայն մեկ բառից, որը մեկ տառից է բաղկացած, այսինքն {aj}(i = 1,2…n) իրավիճակը կանոնական է:

  3. Եթե z իրավիճակը կանոնական է, ապա կանոնական է նաև z* կրկնում իրավիճակը:

  4. Եթե z1 և z2 իրավիճակները կանոնական են, ապա կանոնական են նաև z1 z2 և z1 • z2 իրավիճակները:

  5. Այլ ձևով որոշվող կանոնական իրավիճակներ չկան, յուրաքանչյուր կանոնական իրավիճակ որոշվում է առաջին և երկրորդ կետում սահմանված տարրական կանոնական իրավիճակներից երրորդ և չորրորդ կետերում սահմանված գործողությունների միջոցով:

Թեորեմ: Իրավիճակը ճանաչելի է միայն և միայն այն դեպքում երբ այն կանոնական է:



















Ոչ կանոնական իրավիճակների օրինակներ

Ոչ բոլոր իրավիճակներն են կանոնական: Բերենք ոչ կանոնական իիրավիճակների օրինակներ:

Օրինակ 1: Դիտարկենք այն իրավիճակը {1} այբուբենում, որի բառերի երկարությունը բնական թվի քառակուսի է: Այդ իրաավիճակը նշանակենք X: Ակնհայտ է, որ X = {1,1111,111111111,…}:

l

Ապացուցենք, որ այս իրավիճակը կանոնական չէ: Ենթադրենք հակառակը, որ X իրավիճակը կանոնական է: Դա նշանակում է, որ գոյություն ունի այդ իրավիճակը ճանաչող իրավիճակ: Դիցուք այդ ավտոմատն է՝ , նշանակենք n = : Դիտարկենք կամայական բառ l երկարությամբ, որտեղ l-ը բնական թվի քառակուսի է: Նշանակենք այդ բառը Աl = 1…1: Ենթադրելով, որ l n :

Դա նշանակում է, որ ավտոմատը Աl բառը դիտարկելիս նրա որոշ ընդունած վիճակներ կրկնվում են: Դիտարկենք Աl բառի վրա ավտոմատի վիճակների փոփոխության հաջորդականությունը նշելով այդ փոփոխությունը: Ենթադրելով որ ql-1 վիճակը Աl բառը ավտոմատի կողմից դիտարկելիս առաջին կրկնվող վիճակն է:

Ենթադրենք ցիկլի երկարությունը a է, այսինքն ցիկլի մեջ կա a հատ վիճակ: Այդ դդեպքում ավտոմատը այո կասի բոլոր հետևյալ բառերի վրա՝ Աl, Աl+a, Աl+2a, Աl+3a… Հաշվենք երկու հաջորդական բնական թվերի քառակուսիների տարբերությունը՝ (m+1)2-m2 = 2m+1:
Սա նշանակում է, որ m-ի հաշվվման մեջ հաջորդական m և m+1 բնական թվերի քառակուսիների տարբերությունը աճում է, իսկ դա նշանակում է, որ գոյությւոն ունի t բնական թիվ, որ m2 2: Սա նշանակում է, որ ավտոմատը ճանաչեց նաև Աl+ta բառը, որի մեկերի քանակը բնական թվերի քառակուսի չէ: Դա նշանակում է նաև բառեր, որոնց մեկերի քանակը բնական թվի քառակուսի չէ, հետևաբար ստացված հակասությունը ցույց է տալիս, որ սխալ է այն ենթադրությունը թե X իրավիճակը կանոնական չէ:


Օրինակ 2: Դիտարկենք {01} այբուբենի հավասար քանակով զրոներ և մեկեր պարունակող բառերից բաղկացած իրավիճակը, կնշանակենք X : Ապացուցենք, որ այս իրավիճակը կանոնական չէ: Ենթադրենք հակառակը, որ այդ իրավիճակը կանոնական է հետևաբար այն ճանաչելի է, հետևաբար գոյություն ունի ավտոմատ, որը ճանաչում է այդ իրավիճակը:Ենթադրենք այդ ավտոմատն է՝

l

l

Նշանակենք n = (վիճակների քանակը): Դիցուք l n, այսինքն դիտարկենք 00…0 1…1 (0l1l) բառը: Դիտարկենք ավտոմատի վիճակների փոփոխությունը

ավտոմատը այս բառի վրա աշխատելիս, քանի որ l n-ից, ապա դիտարկվող բառի մեկերը դիտարկելիս ավտոմատի ընդունած որոշ վիճակները կկրկնվեն: Ենթադրենք վիճակների կրկնություն կատարվել է t1 և t2 պահերում, այդ դեպքում ավտոմատը կճանաչի հետևյալ բառերը՝

Ցիկլի երկարությունը՝ t2-t1:

Այսինքն ստացվեց, որ ավտոմատը ճանաչում է նաև բառեր, որոնցում մեկերի քանակը զրոների քանակից շատ է: Այս հակասությւոնը ցույց է տալիս, որ սխալ է այն ենթադրությունը, որ իրավիճակը կանոնական է հետևաբար այդ իրավիճակը կանոնական չէ:


Скачать

Рекомендуем курсы ПК и ППК для учителей

Вебинар для учителей

Свидетельство об участии БЕСПЛАТНО!