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

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

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

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

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

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

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

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

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

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

Սեղմում

Սեղմում

Սկիզբ

Միաց

Անջ.

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

then

the

th

t

then

the

th

t

Սկիզբ

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

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

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

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

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

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

Բառեր

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

∑⁺ = ∑¹ ∑² ∑³ …

∑* = ∑⁺ {ε}

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

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

Լեզուներ

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

L = {0ⁿ1ⁿ | 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. տրված է q₀ սկզբնական վիճակ

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

(Q,∑,δ, q₀,F) հնգյակը կանվանենք դետերմինացված վերջավոր ավտոմատ և կնշանակենք A = (Q,∑,δ,q₀,F) ( կամ կնշանակենք (Q,∑,δ,F) ): Նկարագրենք ավտոմատի աշխատանքը մուտքի այբուբենի a₁a_2…a_n բառի վրա: Ավտոմատը ճիշտ սկսում է աշխատանքը սկզբնական q₀ վիճակը: q₀ վիճակով դիտարկվում է բառի ամենաձախ a₁ տառը, որից հետո անցնում է δ(q₀, a₁), որը նշանակենք q₁, q₁= δ(q₀, a₁): q₁ վիճակով դիտարկում է a₂ տառը անցնում է q₂= δ(q₁, a₂), այսպես շարունակ ավտոմատը q_n-1 վիճակով դիտարկում է a_n տառը անցնում է q_n = δ(q_n-1, a_n) վիճակի: Ավտոմատն ավարտում է աշխատանքը հենց որ հանդիպում է դատարկ նիշի (հենց որ բառի տառերը ավարտվում են): Եթե q_n F ապա a₁a_2…a_n բառը թույլատրելի է ավտոմատի համար: Եթե q_n F, ապա a₁a_2…a_n բառը թույլատրելի չէ ավտոմատի համար:

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

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

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

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

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

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

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

δ(q₀, 1) = q₀

δ(q₀, 0) = q₂

δ(q₂, 0) = q₂

δ(q₂, 1) = q₁

δ(q₁, 0) = q₁

δ(q₁, 1) = q₀

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

Դետերմինացված ավտոմատի տրման եղանակներից , ավտոմատի ուրվապատկերով ներկայացման և աղյուսակով ներկայացման եղանակները: Տրված է ՝ A = (Q,∑,δ,q₀,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 = {q_0, q_1, …q_r} ∑ = { a_1,a_2,…,a_n }: Այդ դեպքում աղյուսակը կլինի հետևյալը՝

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

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

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

x_m

x₂

x₁

Սկիզբ

Ավտոմատի լեզուն խիստ սահմանելու համար նախ սահմանենք վիճակի անցման δ ֆունկցիայի ընդհանրացումը, որը կնշանակենք՝ : Եթե δ-ն հետևյալ տեսքի արտապատկերում է՝ δ: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-երի քանակը զույգ են}: ԿԱռուցենք ավտոմատ որ համար այս լեզուն թույլատրելի է:

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

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

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

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

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

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

A = ({q_0, q_1,q_2, q_3,}, {0,1}, δ, q_0, {q₀}): Այս ավտոմատը ուրվապատկերով կներեկայացվի հետևյալ կերպ՝

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

(q₀,ε) = q₀

(q₀,1) = δ( (q₀,ε),1) = δ(q₀,1) = q₁

(q₀,11) = δ( (q₀,1),1) = δ(q₁,1) = q₀

(q₀,110) = δ( (q₀,11),0) = δ(q₀,0) = q₂

(q₀,1101) = δ( (q₀,110),1) = δ(q₂,1) = q₃

(q₀,11010) = δ( (q₀,1101),0) = δ(q₃,0) = q₁

(q₀,110101) = δ( (q₀,11010),1) = δ(q₁,1) = q₀

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

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

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

δ(q₀,0) = {q₀, q₁}

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

Սկիզբ

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

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

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

Սկիզբ

	0	1
	{q0, }
*

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

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

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

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

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

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

(q₀,ε) = {q₀}

(q₀,0) = δ(q,0) = { q_0,q₁}

(q₀,00) = δ(q₀,0) δ(q₁,0) = { q_0,q₁} = { q_0,q₁}

(q₀,001) = δ(q₀,1) δ(q₁,1) = { q₀} {q₂} = { q_0,q₂}

(q₀,0010) = δ(q₀,0) δ(q₂,0) = { q_0,q₁} = { q_0,q₁}

(q₀,00101) = δ(q₀,1) δ(q₁,1) = { q₀} {q₂} = { q_0,q₂}

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

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

L(A) = {W | (q₀,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 = {a₁,a₂,...a_n} վերջավոր բազմությունը, որը կանվանենք մուտք այբուբեն: B = {b₁,b₂,...b_n} վերջավոր այբուբենը, որը կանվանենք ելքի այբուբեն: Q = {q₁,q₂,...q_n} վերջավոր բազմությունը, որը կանվանենք ներքին վիճակների բազմություն: Տրված են` λ:Q×A Q և δ:Q×A B արտապատկերումը:

A, B,Q բազմությունների և λ,δ արտապատկերումների հնգյակը ֆիքսված q₀ սկզբանական վիճակով կանվանենք ավտոմատ և կնշանակենք՝ (A,B,Q,λ,δ): Նկարագրենք ավտոմատի աշխատանքը մուտքի A այբուբենի X₀X₁...X_s բառի վրա: Ավտոմատը սկսում է աշխատանքը q₀ սկզբնական վիճակով: q₀ վիճակում նա կարդում է X₀ տառը t = 0 պահին, այդ պահին ավտոմատի ելքի վիճակն է y₀ = δ (q_0,x₀), ժամանակի t=1 պահին ավտոմատի վիճակն է՝ q(1) = λ(q_0,x₀): Այդ վիճակում ավտոմատը կարդում է x₁ տառը, այդ պահին նրա ելքի վիճակն է՝ y₁ = δ (q_(1),x₁): Ժամանակի t = 2 պահին ավտոմատի վիճակն է՝ q(2) = λ(q_(1),x₁): Այսպես շարունակ ավտոմատը ուննում է ելքի y₂...y_s ելքի վիճակներ: Ավտոմատն ավարտում է իր աշխատանքը հենց որ հանդիպոււմ է դատարկ նիշի: y₀y₁...y_s ելքի այբուբենի բառը անվանում են ավտոմատի աշխատանքի արդյունք X₀X₁...X_s բառի վրա:

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

Ավտ.

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

t = 0 պահին ավտմատը կարդում է մուտքի ժապավենի X₁ տառը q₀ սկզբանակն վիճակում: լքի ժապավենի 0 համարով բջջում գրվում է ելքի այբուբենի y₀ տառը, որը որոշվում է հետևյալ կերպ y₀ = δ (q_0,x₀): Ժամանակի t = 1 պահին ավտոմատի վիճակն է՝ q(1) = λ(q_0,x₀): q(1) վիճակով ավտոմատը կարդում է X₁ տառը ելքի ժապավենի 1 համար ունեցող բջջում տպում է y₁ = δ (q_(1),x₁) տառը, շարժվում է մեկ բջջով աջ անցնելով q₂ վիճակի: Այսպես շարունակ ժամանակի t = s պահին ավտոմատը q_s վիճակում կարդում է X_s տառը և ելքի ժապավենի s համար ունեցող բջջում տպում է y_s = δ (q_(s),x_s) տառը, մեկ բջջով տեղաշարժվում է աջ անցնելով q(s+1) = λ(q_(s),x_s) վիճակի, հանդիպում է դատարկ բջջի և ավարտում է աշխատանքը: y₀y₁...y_s բառը ավտոմատի աշխատանքի արդյունքն է X₀X₁...X_s բառի վրա:

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

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

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

A = {a₁,a₂,...a_n}

B = {b₁,b₂,...b_n}

Q = {q₁,q₂,...q_n}

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

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

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

δ( )
λ( )

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

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

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

Օրինակ 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: Կառուցենք ավտոմատ, որը գումարում է երկուական համակարգի երկու բնական թվեր: Ենթադրենք այդ թվերն են՝ α = α₀ α₁ …α_n և β = β₀ β₁… β_n: Կարող ենք ենթադրել, որ երկու թվեր ունեն հավասար քանակով թվանշաններ, հակառակ դեպքում փոքր թվի առջևից կավելացնենք 0 թվանշաններ: Ենթադրենք նաև, որ թվերի յուրաքանչյուրի ձախից ավելացված է մեկ հատ 0 թվանշանը: Ավտոմատի մուտքին կտրվի՝ (α_n, β_n), (α_n-1, β_n-1),…, (α₀, β₀), հաջորդականությունը: Սա նշանակում է, որ ավտոմատի մուտքի այբուբենը հետևյալ նիշերի բազմությունն՝A = {(0,0), (0,1), (1,0), (1,1)}: Ելքի այբուբենն է՝ B = {0,1}: Որպես վիճակներ ընտրենք q₀ և q_1, որտեղ q₀ վիճակը նշանակում է, որ նախորդ կարգում գումարման արդյունքում փոխանցվել է 0 թվանշանը (թվանշան չի փոխանցվել): q₁ վիճակ նշանակում է, որ նախորդ կարգում գումարման արդյունքից փոխանցվել է 1 թվանշանը (թվանշան է փոխանցվել), հետևաբար վիճակների բազմությունը կլինի՝ Q = {q₀, q₁} : Ավտոմատին համապատասխան աղյուսակը կլինի հետևյալը՝

(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 այբուբենի բոլոր բառերի բազմությունը: Եթե ավտոմատի աշխատանքի արդյունքը մուտքի այբուբենի x₀x₁…x_s բառի վրա ելքի այբուբենի y₀y₁…y_s բառն է ապա y_s-ը կանվանենք x₀x₁…x_s բառի վրա ավտոմատի աշխատանքի արդյունք և կնշանակենք՝ ₀x₁…x_s=y_s : Կամայական z⊆A* ենթաբազմությունը A*-ից, կանվանենք իրավիճակ: Կասենք, որ ավտոմատը ճանաչում է z իրավիճակը, եթե հնարավոր է B բազմությունը տրոհել B₁ և B₂ ենթաբազմությունների (այսինքն B ներկայացնել B₁,B₂⊆B ենթաբազմությունների միջոցով, որ տեղի ունենա՝ B = B₁ B₂ և B₁ B₂ = ) այնպես, որ տեղի ունենա հետևյալ պայմանը՝ x₀x₁…x_s A* բառի համար x₀x₁…x_s z ₀x₁…x_s B₁

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

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

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

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

a₂ (“ոչ”)

a_n (“ոչ”)

a₃ (“ոչ”)

a₁ (“ոչ”)

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

a₃ (“այո”)

a₁ (“այո”)

a₂ (“այո”)

a_n (“այո”)

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 (“ոչ”)

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

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

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

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

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

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

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

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

4. Եթե z₁ և z₂ իրավիճակները կանոնական են, ապա կանոնական են նաև z₁ z₂ և z₁ • z₂ իրավիճակները:

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

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

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

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

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

l

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

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

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

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

l

l

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

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

Ցիկլի երկարությունը՝ t₂-t₁:

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