Ավտոմատների կիրառական տեսոթյուն
Ծրագրավորման լեզուների ընդհանուր նկարագիրը
Համակարգիչը հանդիսանում է հաշվողական գործընթացների իրականացման տեսանկյունից մարդու մոդել, այսինքն որոշակի առումներով կապված հաշվողական գործընթացների կազմակերպման հետ համակարգիչը նման օրինակում է մարդուն: Մարդու ուղեղի անալոգը համակարգչի պրոցեսորն է: Մարդու հիշեղության անալոգը համակարգչի հիշողությունն է: Շրջապատող միջավայրից մարդը լսողությամբ, տեսողությամբ, զգացողությամբ և այլ միջոցներով տեղեկատվություն է ստանում: Անալոգ ձևով համակարգիչը տեղեկատվություն է ստանում ներմուծման սարքերի միջոցով: Մարդը շրջապատող միջավայրին տեղեկատվություն է տալիս: Անալոգ ձևով համակարգիչը արտասման սարքերի միջոցով տեղեկատվություն է տալիս շրջապատող միջավայրին: Գարադարանների անալոգը համակարգչի համար ստանդարտ ենթածրագրերի գրադարանն է: Գրադարանների հետ աշխատելու համար կա գրադարանների կատալոգի համանման համակարգչում ևս կան կատալոգներ: Խոսակցական լեզուներին անալոգ համակրգչի համար նախատեսված են ծրագրավորման լեզուներ: Ծրագրավորման լեզուների կառուցվածքը ընդհանուր առմամբ նման է խոսակցական լեզուների կառուցվածքին: Ծրագրավորման լեզվի այբուբենը լատինական այբուբենի տառերն են, 0-9 թվանշանները, գործողության նշանները, փակագծերը և այլ թույլատրելի նիշերը: Ծրագրավորման լեզվի բառերը 2 հիմնական տիպի՝
Ծառայողական (ֆիքսված, ստանդարտ) բառեր և իդենտիֆիկատորներ: Ծառայողական բառերը ֆիքսված բառեր են, որոնք ստանդարտ ձևով օգտագործվում են տվյալ լեզվի հրամանների և այլ օբյեկտների գրառման համար: Այդ բառերը ֆիքսված են և փոփոխության ենթակա չեն: Իդենտիֆիկատորը տառերի, թվանշանների և որոշ թույլատրելի նիշերի հաջորդականություն է, որը սկսվում է տառով: Իդենտիֆիկատորը նշանակում է ծրագրավորողը: Նախադասության անալոգը ծրագրավորման լեզվի հրամանն է (օպերատորը):
Խոսակցական լեզվի տեքստի անալոգը ծրագիրն է: Խոսակցական լեզուների նման ծրագրավորման լեզուներն ունեն բառակազմական, շարահյուսական, իմաստաբանական օրենքներ: Բառակազմական օրենքները որոշում են թե որ բառերն են թույլատրելի տվյալ լեզվի համար: Շարահյուսական օրենքները որոշում են թե տվյալ հրամանը ընդունելի է արդյոք տվյալ ծրագրավորման լեզվի համար:Իմաստաբանական օրենքը հրամաններին տալիս են իմաստ: Խոսակցական լեզուների նման ծրագրավորման լեզուներն ունեն քերականություն:
Ծրագրավորման լեզուները ունեն որոշակի ընհանուրություններ: Այդ լեզուները մեկը մյուսի նկատմամբ ունեն որոշակի առավելություններ և թերություններ: Յուրքանչյուր ծրագրավորման լեզու իր հնրարավորություններվ հարմար է որոշակի բնագավառի խնդիրների լուծման համար:
Բոլոր ծրագրավորման լեզուները ունեն տվյալների ներմուծման, արտածման, կազմակեպման հնարավորություններ: Բոլոր լեզուներում կան հրամանների հաջորդական կազմակերպում (վերագրաման օպերտոր): Բոլոր լեզուներում կան ճյուղավորում և ցիկլիկ կազմակերպման հնարավոություն: Կա ենթածրագրեր (ֆունկցիաներ, պրոցեդուրաներ) կազմակերպելու հնարավորություն:
Ավտոմատների տեսության ներածություն
Ավտոմատների տեսությունը և բարդության տեսությունը կազմում են ինֆորմացիայի միջուկի ամենակարևոր մասերը: Վերջավոր ավտոմատները հանդիսանում են սարքավորումներ և ծրագրային ապահովումների շատ բաղադրիչների մոդելներ: Դիտարկենք “միացված-անջատված” փոխարկիչի (հոսանքափոխարկիչի) ավտոմատային մոդելը: Փոխարկիչն ունի երկու վիճակ՝ միացված և անջատված: Նար սկզբնական վիճակն անջատված վիճակն է: Սարքը յուրաքանչյուր պահի հիշում է իր վիճակը: Կատարվող հիմնական գործողությունը կոճակը սեխմելու գործողությունն է: Եթե սարքը գտնվում է անջատված վիճկում և կատարվում է կոճակի սեղմում գործողությունը, ապա սարքն անցնում է միացված վիճակի և հակառակը, եթե սարքը գտնվում է միացված վիճակում, ապա կոճակի սեղմում գործողության կատարման արդյունքում սարքն անցնում է անջատված վիճակի: Փոխարկիչ սարքի ավտոմատային մոդելը հետևյալն է՝
Սեղմում
Սեղմում
Սկիզբ
Միաց
Անջ.
Սովարաբար ավտոմատի վիճակների մեջ ֆիքսվում է որոշ վիճակներ, որոնց անվանում են եզրափակիչ կամ թույլատրելի վիճակներ: Եզրափակիչ վիճակները ընդունված է նշել կրկնակի շրջանակներով: Փոխարկիչ սարքի համար եզրափակիչ վիճակ կարող է լինել միացված վիճակը, քանի որ այդ վիճակը ազդարարում է փոխարկչին միացվածսարքավորման աշխատանքի սկսվելը: Գործողությունների հաջորդականությունը, որը բերում է ավտոմատի եզրափակիչ վիճակի կանվանենք գործողություների լավ հաջորդականություն: Ավտոմատները կարող են հանդիսանալ բառապաշարային վերլուծիչի (անալիզատոր) բաղադրիչ մաս: Օրինակ՝ ներկայացնենք ավտոմատ, որը ճանաչում է then բառը: Այդ ավտոմատը հետևյալն է՝
then
the
th
t
then
the
th
t
Սկիզբ
Վերջավոր ավտոմատները հանդիսանում են հաշվարկելիության սահմանների վերլուծության կարևոր գործիք: Համկարգչի համար կան երկու հիմնական պրոբլեմ՝
Ի՞նչ կարող է անել համակարգիչը:
Համակարգիչը ի՞նչ կարող է անել արդյունավետ ձևով:
Առաջին պրոբլեմը խնդիրների լուծելիության պրոբլեմն է: Այն խնդիրները որոնք հնարավոր է լուծել համակարգչով անվանում են լուծելի խնդիրներ: Այս պրոբլեմի հարցերով է զբաղվում ալգորիթմների տեսություն առարկան: Երկրորոդ պրոբլեմը խնդիրների հեշտությամբկամ ոչ հեշտությամբ լուծելու պրոբլեմն է: Ընդհանրապես համակարգչով խնդրի լուխման համար անհրաժեշտ ժամանակը ֆունկցիա է կախված խնդրի մուտքային տվյալների կոդի երկարությունից: Եթե այդ ֆունկցիան կոդի երկարությունից ունի բազմանդամային տեսքի կավածություն, ապա խնդիրն անվանում են հեշտ լուծվող խնդիր: ԲԱզմանդամության ֆունկցիան արգումենտից կախված բավականաչափ դանդաղ աճող ֆունկցիա է: Եթե այդ ֆունկցիան կոդի երկարությունից կախված ավելի արագ աճող ֆուննկցիա է քան կամայական բազմանդամ ապա համապատասխան խնդիրը անվանում են դժվար լուծվող խնդիր:
Վերջավոր ավտոմատների հիմնական գաղափարները
Վերջավոր ավտոմատների վերաբերող հիմնական գաղափարներն են այբուբեն, բառ (շղթա), լեզու: Այբուբենը ոչ դատարկ վերջավոր բազմություն է: Այբուբենը ընդունված է նշանակել ∑ (սիգմա) տառով: Դա այն բազմություննէ, որի միջոցով գրառում են ավտոմատին տրվող տվյալները: Այբուբենի օրինակ են՝ ∑ = {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
∑*) թե ոչ:
Դետերմինացված վերջավոր ավտոմատներ
Ավտոմատը ժամանակի յուրաքանչյուր պահի գտնվում է որոշակի վիճակում, այն մուտքում ստանում է մուտքային այբուբենի բառ հերթականությամբ ձախից աջ դիտարկում է բառում եղած տառերը և յուրաքանչյուր տառ դիտարկելուց հետո որոշակի օրենքով փոխում է իր վիճակը: Դետերմինացված վերջավոր ավտոմատը ժամանակի յուրաքանչյուր պահին գտնվում է մեկ վիճակում, այլ կերպ ասած դետերմինացված ավտոմատը գտնվելով որևէ ընթացիկ վիճակում և այդ վիճակում դիտարկելով բառի հերթական տառը անցնում է միայն մեկ վիճակի: Ոչ դետերմինացված ավտոմատը ժամանակի յուրաքանչյուր պահի կարող է գտնվել մի քանի վիճակներում: Տանք դետերմինացված վեջավոր ավտոմատի մաթեմատիկական սահմանումը: Ենթադրենք տրված է`
վիճակների վերջավոր բազմություն, որը նշանակենք Q
տրված է ոչ դատարկ մուտքի այբուբեն, որը նշանակենք՝ ∑
տրված է δ(դելտա) արտապատկերում, որը ցույց է տալիս թե տվյալ վիճակում տվյալ տառը կարդալիս ավտոմատը ինչ վիճակի է անցնում, այլ կերպ ասած տրված է՝ δ:Q×∑
Q:
տրված է q0 սկզբնական վիճակ
տրված է 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, ուրվապատկերի ներկայացումը՝
գագաթների Q բազմության, յուրաքանչյուր q գագաթին համապատասխան շրջանակի ներսում գրելով այդ վիճակը: Պատկերել այնպես, որ շրջանակները հատում չունենան
յուրաքանչյուր p= δ(q, a) համապատասխանության համար q գագաթին համապատասխան շրջանակը ուղղորդված աղեղով միացնում ենք p գագաթին համապատասխան շրջանակին ուղղությունն ընտրելով q գագաթից դեպի p գագաթ և աղեղի վրա գրելով a նիշը: Եթե q վիճակից p վիճակին կան անցումներ մի անի նիշերի համար, ապա a-ի վրա գրում ենք այդ նիշերի հավաքածուն:
Սկզբանական վիճակի ուղղված սլաք ենք նշում, որի վրա գրում ենք սկիզբ, այդ սլաքը ոչ մի գագաթից դուրս չի գալիս:
Ավտոմատի թույլատրելի վիճակները նշում են կրկնակի շրջանակներով, իսկ ոչ թույլատրելի վիճակները նշում ենք մեկ շրջանակով: 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 զույգով ավարտվող բառերի բազմությունը ճանաչող ավտոմատի համապատասխան աղյուսակը:
Սկիզբ
Ոչ դետերմինացված ավտոմատի վիճակի անցման ֆունկցիայի ընդհանրացումը
Ոչ դետերմինացված ավտոմատի թույլատրելի լեզվի սահմանման համար նախ սահմանենք նրա վիճակի անցման արտապատկերման ընդհանրացման գաղափարը: Ոչ դետերմինացված ավտոմատի վիճակի անցման ընդհանրացված արտապատկերումը կնշանակենք՝
: Այն վիճակի և մուտքի այբուբենի բառի զույգին համապատասխանեցնում է վիճակների բազմության բազմություն: Այլ կերպ ասած այն հետևյալ տեսքի արտապատկերում է՝
: 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* կանոնական արտահայտությունը: Այս կանոնական արտահայտության միջոցով տրվում է այն լեզուն, որը բաղկացած է մեկ հատ զրոյիցև նրան հաջորդող մեկերից բաղկացած կամ մեկ հատ մեկից և նրանց հաջորդող զրոներից բաղկացած բառերից:
Կան կանոնական արտահայտությունների համար երեք օպերատորներ և այդ կանոնական արտահայտություններին համապատասխան լեզուների համար երեք գործողություններ՝
L, M լեզուների միավորում, որը կնշանակենք՝ L
M տեսքով, կանվանենք բոլոր այն բառերի բազմությունը, որոնք պատկանում են L բազմությանը կամ M բազմությանը:
L, M լեզուների կոնկատենացիա կամ կցում, որը կնշանակենք L•M կամ (LM), կանվանենք բոլոր այն բառերի բազմությունը, որոնք ստացվում են L լեզվի բառերի աջից կցելով M լեզվի բառեր:
L լեզվի իտերացիա (կրկնում), որը կնշանակենք L*, կանվանենք բոլոր այն բառերի բազմությունը, որոնք ստացվում են L լեզվի վերջավոր թվով բառեր իրար կցելով:
Կանոնական արտահայտությունների կառուցումը: Ցանկացած հանրահաշիվ սահմանելու համար նախ սահմանվում են տարրական արտահայտություններ, հաստատուններ և փոփոխականններ, այնուհետև օպերատորների միջոցով տարրական արտահայտություններից կամ արդեն ստացված արտահայտություններից սահմանվում են ավելի բարդ արտահայտություններ: Արտահայտություններ սահմանելիս օգտագործում են նաև փակագծեր: Այս ձևով է սահմանվում նաև թվաբանության հանրահաշիվը նման ձևով է սահմանվում նաև կանոնական արտահայտությունների հանրահաշիվը:
Բազիս: Բաղկացած է երեք կետերից՝
ε և
հաստատունները հանդիսանում են կանոնական արտահայտութնուններ, որոնք համապատասխանաբար լեզուներն են՝ L(ε) = {ε} և L(
) =
(E կանոնական արտահայտության համապատասխան լեզուն նշանակում են L(E)-ով):
Եթե a-ն կամայական նշան է ապա այն կանվանենք կանոնական արտահայտություն, կնշանակենք՝ a: a կանոնական արտահայտության համապատասխան լեզուն է՝ L(a) = {a}:
Ընդունված է լեզուները նշանակել լատինական այբուբենի մեծատառ տեսքով:
Ինդուկցիա: Բաղկացած է չորս կետից: Առաջին երեք կետերը վերաբերում են կանոնական արտահայտությունների օպերատորներին, իսկ չորրորդ կետը վերաբերում է փակագծերի օգտագործմանը:
E, F կանոնական արտահայտությունների միավորում կնշանակենք E+F տեսքով: Նրան համապատասխան լեզուն որոշվում է հետևյալ կերպ՝ L(E+F) = L(E)
L(F):
E, F կանոնական արտահայտությունների կոնկատենացիա կնշանակենք E•F կամ (EF) տեսքով: Նրան համապատասխան լեզուն որոշվում է հետևյալ կերպ՝ L(EF) = L(E)•L(F):
E կանոնական արտահայտության իտերացիա կնշանակենք E* և նրան համապատասխան լեզուն որոշվում է հետևյալ կերպ՝ L(E*) = (L(E))*:
E կանոնական արտահայտության կանոնական արտահայտություն է նաև` (E), այն որոշում է նույն L(E) լեզուն՝ L((E)) = L(E):
Կանոնական արտահայտությունների նախապատվություն (приоритет): Ամենամեծ նախապատվություն ունի իտերացիայի * օպերատորը: Հաջորդ նախապատվելի գործողությունը իտերացիայից հետո համարվում է կոնկատենացիա՝ • : Այնուհետև + գործողությունը: Փակագծերը մտցվում են լրացուցիչ նախապատվություն, այսինքն սկզբից կատարվում են փակագծերում տրված օպերատորի հավաքածուն այնուհետև նրանից դուրս նշած օպերատորները:
Կոնտեքստից ազատ քերականություններ
Կոնտեքստից ազատ քերականությունը իրենից ներկայացնում է G = (N,T,P,S) քառյակը, որտեղ՝
T-ն իրենից ներկայացնում է քերականությանը համապատասխան լեզվի այբուբեն, այսինքն այբուբեն, որի նիշերի միջոցով գրառվում են տվյալ լեզվի բառերը: T-ն անվանում են տերմինալների բազմություն:
N-ը ոչ տերմինալների (փոփոխականների) բազմություն է: Ոչ տերմինալները լեզվին համապատասխան բառեր ստանալիս օգտագործվում են որպես միջանկյալ նիշեր: Ոչ տերմինալները լեզվի բառերի գրառման նիշեր չեն և N
T=
:
P-ն կանոնների բազմություն է, որոնց միջոցով արտածվում են լեզվին համապատասխան բառերը: Յուրաքանչյուր կանոն բաղկացած է երեք մասից՝
ա) ամենաձախ մասում կանոնի գրվում է ոչ տերմինալային նիշ
բ) ոչ տերմինալային նիշին հաջորդում է՝
նիշը:
գ)
նիշին աջից հաջորդում է տերմինալներից և ոչ տերմինալներից կազմված բառը:
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
Ավտոմատը, որպես հաշվիչ մեքենայի մաթեմատիկական մոդել
Հիմնական գաղափարներ: Ավտոմատները իրենցից ներկայացնում են որոշակի դասի հաշվիչ մեքենաների մաթեմատիկական մոդելներ, որոնք բավարարում են հետևյալ սկզբունքներին՝
Նրանցում ամեն ինչ կատարվում է ժամանակի առանձին պահերի, իսկ այդ պահերի միջև ընկած ժամանակահատվածում ոչինչ չի կատարվում: Ժամանակի այդ պահերը կնշանակենք 0,1,2...
Մեքենան ունի մուտքի սարք, որով արտաքին միջավայրը ազդում է նրա վրա: Մոտքի սարքի վիճակների բազմությունը վերջավոր է:
Մեքենանա ունի ելքի սարք, որով նա ազդում է արտաքին միջավայրի վրա: Ելքի սարքի վիճակների բազմությունը վերջավոր է:
Մեքենան ունի ղեկավարող սարք, որը ղեկավարում է նրա ամբողջ աշխատանքը: Ղեկավարող սարքի վիճակների բազմությունը վերջավոր է:
Ժամանակի յուրաքանչյուր t = 0,1,2… պահի մեքենայի ելքի վիճակը որոշվում է t պահին մեքենայի (ղեկավարող սարքի ) վիճակով և մեւտքի սարքի վիճակով:
Ժամանակի յուրաքաչյուր 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 թվանշանը, եթե մինչև այդ հանդիպած մեկերի քանակը կենտ է:
Ակնհայտ է, որ այս ավտոմատի համար մուտքի այբուբենը՝ 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 = “այո”:
Ներկայացնենք որոշ ճանաչելի իրավիճակներ՝
Կամայական A = {a1,a2,…am} այբուբենի համար
և A*իրավիճակները ճանաչելի են: Դատարկ իրավիճակը ճանաչող ավտոմատը հետևյալն է՝
a2 (“ոչ”)
an (“ոչ”)
a3 (“ոչ”)
a1 (“ոչ”)
A* իրավիճակը ճանաչող ավտոմատը հետևյալն է՝
a3 (“այո”)
a1 (“այո”)
a2 (“այո”)
an (“այո”)
{a,b} այբուբենում կամայական մեկ բառից կազմված իրավիճակ ճանաչելի է: Այդ մեկ բառը ճանաչող ավտոմատը կառուցվում է հետևյալ սկզբունքով: {a} այս իրավիճակը ճանաչող ավտոմատը կլնի հետևյլաը՝
a (“այո”)
b (“ոչ”)
a (“ոչ”)
b (“ոչ”)
{ab} իրավիճակը ճանաչող ավտոմատը կլինի հետևյալը՝
a (“ոչ”)
b (“այո”)
b (“ոչ”)
a (“ոչ”)
b (“ոչ”)
b (“ոչ”)
a (“ոչ”)
a (“ոչ”)
{a,ab} իրավիճակը ճանաչող ավտոմատը կլինի հետևյալը՝
b (“այո”)
a (“ոչ”)
a (“ոչ”)
b (“ոչ”)
b (“ոչ”)
a (“ոչ”)
Ցույց տանք, որ {0,1} այբուբենի 0 նիշը չպարունակող և կենտ թվով մեկերից կազմված բառերի բազմությունը ճանաչելի իրավիճակ է: Այդ իրավիճակը ճանաչող ավտոմատը հետևյալն է՝
1 (“այո”)
1 (“ոչ”)
0 (“ոչ”)
1 (“ոչ”)
0 (“ոչ”)
0 (“ոչ”)
Սահամնենք որոշ գործողություններ իրավիճակների նկատմամբ: Դիցուք տրված է z1 ⊆ A* և z2 ⊆ A* իրավիճակները՝
z1 և z2 իրավիճակների գումար, որը կնշանակենք՝ z1
z2 , (գումար) կանվանենք այն իրավիճակը, որի յուրաքանչյուր բառ պարունակում է z1 իրավիճակին կամ z2 իրավիճակին:
z1 և z2 իրավիճակների արտադրյալ, որը կնշանակենք՝ z1 • z2 , կանվանենք բոլոր և միայն այն բառերի բազմությունը, որոնք ունեն ԱԲ տեսքը, որտեղ Ա
z1 և Բ
z2:
z1 իրավիճակի կրկնում (իտերացիա), որը կնշանակենք
տեսքով բոլոր և միայն այն բառերի բազմությանը, որոնք ստացվում են z1-ի վերջավոր թվով բառեր իրար կցելով: Կատարենք հետևյալ նշանակումները՝
= z1,
= z1• z1•…
=
• z1: Այս նշանակումները կներկայացվի հետևյալ տեսքով՝
=
Դիտարկենք A = { a1,a2,...an } այբուբենում իրավիճակների մի կարևոր դաս, որը էական դեր է խաղում իրավիճակների ճանաչելիության հարցում: Դա կանոնական իրավիճակների դասն է:
դատարկ իրավիճակը կանոնական իրավիճակ է:
Միայն մեկ բառից, որը մեկ տառից է բաղկացած, այսինքն {aj}(i = 1,2…n) իրավիճակը կանոնական է:
Եթե z իրավիճակը կանոնական է, ապա կանոնական է նաև z* կրկնում իրավիճակը:
Եթե z1 և z2 իրավիճակները կանոնական են, ապա կանոնական են նաև z1
z2 և z1 • z2 իրավիճակները:
Այլ ձևով որոշվող կանոնական իրավիճակներ չկան, յուրաքանչյուր կանոնական իրավիճակ որոշվում է առաջին և երկրորդ կետում սահմանված տարրական կանոնական իրավիճակներից երրորդ և չորրորդ կետերում սահմանված գործողությունների միջոցով:
Թեորեմ: Իրավիճակը ճանաչելի է միայն և միայն այն դեպքում երբ այն կանոնական է:
Ոչ կանոնական իրավիճակների օրինակներ
Ոչ բոլոր իրավիճակներն են կանոնական: Բերենք ոչ կանոնական իիրավիճակների օրինակներ:
Օրինակ 1: Դիտարկենք այն իրավիճակը {1} այբուբենում, որի բառերի երկարությունը բնական թվի քառակուսի է: Այդ իրաավիճակը նշանակենք X: Ակնհայտ է, որ X = {1,1111,111111111,…}:
l
Ապացուցենք, որ այս իրավիճակը կանոնական չէ: Ենթադրենք հակառակը, որ X իրավիճակը կանոնական է: Դա նշանակում է, որ գոյություն ունի այդ իրավիճակը ճանաչող իրավիճակ: Դիցուք այդ ավտոմատն է՝
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABgAAAAVCAIAAADTi7lxAAABdklEQVR4nGP5//8/AzUAC1VMGTWIXIMuX77c3NzMxsb2+PHjX79+lZaWBgUFkWzQmTNngoODt2/frqWldfv2bTU1NR0dHZJdBExTiYmJWVlZQFMgTmNnZ1dWVibZoOPHj1+5ciUuLg7CBRqkoaHBzMxMskGnT5/m5+eXlJSEG6StrU2MKegGff36lYmJCc69ePEi0KfkGKSrq/v+/fulS5fa2dlNmjTpzp07ZLrIx8cH6ISMjAxLS8vi4uKenp7Vq1f7+voCnblkyZIXL158+vTp9evX06dPJ2AQIyPjPDCAcOEFw6lTp86fP9/b27t79+49e/YQdhEusGLFCqC7gIyrV68CvU++QW/evIEkAqBBubm5QMb69etZWVmB6R6e6IkyKCIiorCw0Nvb+8CBA1OnTgWKAH3a1NRUU1NDmkFeYPDv37+dO3cC8yBcHLl0JSH33717F+jBL1++8PDwGBgYbN682dDQkByDVFVVjx07BmFjlgcA0vGfmsX5PWMAAAAASUVORK5CYII=)
, նշանակենք n =
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB4AAAAUCAIAAAAVyRqTAAABtElEQVR4nGP5//8/Ayr4/fv3169fBQQEGIgDuNSzYCq9ePHiggULpkyZQqTRuNRjMZpaYKCN/vLly8yZMzdt2iQiIgJks7Oz19TUmJmZUWr0o0eP3N3dDQwMtmzZwsvLCxRZsWKFra3thg0bPD09yTcaGPs+Pj7CwsKLFy9mYYEqjoiIWL9+fUZGxv3795mYmMg0etasWZcvXz5x4gTcXAhwcnJatWrVlStX9PT0yDR66dKl2tra5ubmaOJAfwDJT58+4dGLz2hgbjp9+nRqaiqm1OPHj4GkhIQEmUa/ffv2z58/0tLSmFL79+8XFRVVVlYm02guLi5gLL179w5NHJhmduzYkZ2dzcjISL7RNjY2Bw8eRBMvLCwUFBQsLy/Ho5eA0UAwceJEe3v79vb2yspKIPfbt2/FxcWHDh3auHEj/oAmbDQwpwATX2lpqaWlJTC/XLt2LSoqClgeSUlJ4ddI2GggkJOTW7lyJZDR2tq6e/duBwcHYswlymg4KCsr27ZtGzArNjY2WllZYSZ28o1mZWUFuhqY44E5BS1zUmo0AzjNpKenE6kYi9EmYEC8fbjUAwCvSqd53DCtZQAAAABJRU5ErkJggg==)
: Դիտարկենք կամայական բառ l երկարությամբ, որտեղ l-ը բնական թվի քառակուսի է: Նշանակենք այդ բառը Ա
l = 1…1: Ենթադրելով, որ l n :
Դա նշանակում է, որ ավտոմատը Ա
l բառը դիտարկելիս նրա որոշ ընդունած վիճակներ կրկնվում են: Դիտարկենք Ա
l բառի վրա ավտոմատի վիճակների փոփոխության հաջորդականությունը նշելով այդ փոփոխությունը: Ենթադրելով որ q
l-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 =
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB4AAAAUCAIAAAAVyRqTAAABtElEQVR4nGP5//8/Ayr4/fv3169fBQQEGIgDuNSzYCq9ePHiggULpkyZQqTRuNRjMZpaYKCN/vLly8yZMzdt2iQiIgJks7Oz19TUmJmZUWr0o0eP3N3dDQwMtmzZwsvLCxRZsWKFra3thg0bPD09yTcaGPs+Pj7CwsKLFy9mYYEqjoiIWL9+fUZGxv3795mYmMg0etasWZcvXz5x4gTcXAhwcnJatWrVlStX9PT0yDR66dKl2tra5ubmaOJAfwDJT58+4dGLz2hgbjp9+nRqaiqm1OPHj4GkhIQEmUa/ffv2z58/0tLSmFL79+8XFRVVVlYm02guLi5gLL179w5NHJhmduzYkZ2dzcjISL7RNjY2Bw8eRBMvLCwUFBQsLy/Ho5eA0UAwceJEe3v79vb2yspKIPfbt2/FxcWHDh3auHEj/oAmbDQwpwATX2lpqaWlJTC/XLt2LSoqClgeSUlJ4ddI2GggkJOTW7lyJZDR2tq6e/duBwcHYswlymg4KCsr27ZtGzArNjY2WllZYSZ28o1mZWUFuhqY44E5BS1zUmo0AzjNpKenE6kYi9EmYEC8fbjUAwCvSqd53DCtZQAAAABJRU5ErkJggg==)
(վիճակների քանակը): Դիցուք l n, այսինքն դիտարկենք 00…0 1…1 (0
l1
l) բառը: Դիտարկենք ավտոմատի վիճակների փոփոխությունը
ավտոմատը այս բառի վրա աշխատելիս, քանի որ l n-ից, ապա դիտարկվող բառի մեկերը դիտարկելիս ավտոմատի ընդունած որոշ վիճակները կկրկնվեն: Ենթադրենք վիճակների կրկնություն կատարվել է t
1 և t
2 պահերում, այդ դեպքում ավտոմատը կճանաչի հետևյալ բառերը՝
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEUAAAAVCAIAAACfYbSJAAADt0lEQVR4nN1XOUhjQRh+arxCVBQVMcQDTzSgGCwUK4stjGChjaxssXg2iiCoiGARLxQMXuABFh5FIIoWCotYiGAnFoooNiqKEg+8D7y+fcMOk3ckcZ9ZYb8i/DPvn5nvm/+ffyaqt7c37otwd3enVqsVTnJ/f+/v70+bKoXTKeFxenoaFRWlcJ79/f2kpCTa/GQ9TU1NGo2msbFR0L+4uDg3N6fVajc3N0dHR318fLa3t9PS0sjXp6cnlUrl6enpdH6xJ3pYB1f1yBEVwMPDQ6/XE3tiYiImJiYnJwd2cHBwZ2cnEqOkpGRlZSU3NxfxgTPxxLTt7e0Q6ZSG2DMgIOD4+DgiIuJjeliiDrCxsVFaWkrs3d1dPz8/YhsMBmJcXFyQHKP7iiFWqzU+Pr6qqsrp5GLP0NDQnZ2dD+thiTrA3t5edHT05ORkV1cXtg0BMZlMg4OD2dnZ6+vrIyMjCQkJsbGx8Hx5eSFDUBIyMzOdipHzxBLX19e06aoeQtSxz+3tLZZEJL/zaGlpQUiLiorI1/T09IGBAbPZ3NPTU1dXR+sqTlRqaqpgqt7eXlQ/2kS6VlRUSHp6eXk9Pz/L6nl4eKitrQV7GMnJyVjb19eXEmU9X19fh4eH+/r6sAxllpKSIil1dXU1KysLRlhYGELN8QlMPm1tbWEhGLOzs9CAuOGMVVdXiyehnicnJ62trdBMaKBCyOqpr69H+Obn52Hn5+c3NDRAkpjo2tpad3f30dHR2dkZ7QRRsMFGkGOD+LBUlpaW0A+ftrY2sq/kE1LfYrEgkgUFBTc3N/39/ZI7wnoCgYGBpPPx8VH2/kHNQYrPzMyQZllZWXFxMZYXEAVQuKamppA8HR0ddPhPHpJUxP20Rv3gwfE7PT09LRkZgScLXGKRkZHSerDrkESvJyQrmugUEw0JCZFb1UWwm0rQ3NyMzFlYWCgsLHQ81mazHR4e4iZFqTw/P2cLr50eeOA3KCiIJX1wcKCQuiRQdpGu7NbiSLg4FodwbGyM2DjeNHU5gR5k1O+uP8eLGAiRAtqywO38KU9Hdkc4gR6SAxCAS5fj6y8nlRifBbKKQtDCQGCnh9zcqG/h4eEwrq6u8KvT6ZSv+s9gpycjIwP3DF6KcXFxHH+foKCh84u4/Q3s9IB9eXn5+Ph4Xl4emqjdaLov39wB4X2K12tNTY3RaMR7MTExEY9iyWG/eCwvL19eXlZWVuJQ4uXr7e3tfsJOINSDEA0NDTkd9o2Heygpwpf9P3UT/jc972DfqWtVkYzNAAAAAElFTkSuQmCC)
…
Ցիկլի երկարությունը՝ t2-t1:
Այսինքն ստացվեց, որ ավտոմատը ճանաչում է նաև բառեր, որոնցում մեկերի քանակը զրոների քանակից շատ է: Այս հակասությւոնը ցույց է տալիս, որ սխալ է այն ենթադրությունը, որ իրավիճակը կանոնական է հետևաբար այդ իրավիճակը կանոնական չէ: