Սովորական լեզուներ և վերջավոր վիճակի մեքենաներ: Վերջնական ավտոմատներ և կանոնավոր լեզուներ Պաշտոնական լեզուների տեսություն կեղծամների համար

Մենք գիտենք լեզուների համակցման գործողությունները: Եկեք սահմանենք կապակցման և կրկնման գործողությունները (երբեմն կոչվում է Kleene փակում):

Թող L 1-ը և L 2-ը լինեն այբուբենի լեզուներով

Հետո, այսինքն. լեզվի միացումբաղկացած է առաջին լեզվի բոլոր բառերի միացումներից երկրորդ լեզվի բոլոր բառերի հետ: Մասնավորապես, եթե , ապա , եւ եթե , ապա .

Ներկայացնենք L լեզվի «աստիճանների» նշում.

Այսպիսով, L i-ն ներառում է բոլոր բառերը, որոնք կարելի է բաժանել i-ի հաջորդական բառերի L-ից:

L լեզվի կրկնությունը (L) * ձևավորվում է բոլոր բառերով, որոնք կարելի է բաժանել մի քանի հաջորդական բառերի L-ից.

Այն կարող է ներկայացվել աստիճանների միջոցով.

Հաճախ հարմար է դիտարկել լեզվի «կտրված» կրկնությունը, որը չի պարունակում դատարկ բառը, եթե այն գոյություն չունի լեզվում. . Սա նոր գործողություն չէ, այլ պարզապես հարմար սղագրություն արտահայտության համար:

Նկատի ունեցեք նաև, որ եթե այբուբենը դիտարկենք որպես վերջավոր լեզու, որը բաղկացած է միատառ բառերից, ապա այբուբենի բոլոր բառերի, ներառյալ դատարկ բառերի բազմության համար նախկինում ներկայացված նշանակումը համապատասխանում է այս լեզվի կրկնության սահմանմանը:

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

Արտահայտությունը r	Լեզու Լ ր
	Լ ա = (ա)
Թող լինեն r 1 և r 2	L r1 և L r2 - ներկայացվող
կանոնավոր արտահայտություններ.	նրանց լեզուները։
Այնուհետեւ հետեւյալ արտահայտությունները
կանոնավոր են	և ներկայացնել լեզուները.
r=(r 1 +r 2)
r=(r 1 circr 2)
r=(r 1) *	L r =L r1 *

Ձայնագրելիս կանոնավոր արտահայտություններՄենք բաց կթողնենք կապակցման նշանը և կենթադրենք, որ * գործողությունն ունի ավելի մեծ առաջնահերթություն, քան կապակցումը և +ը, իսկ միացումն ունի ավելի առաջնահերթություն, քան +: Սա թույլ կտա շատ փակագծեր բաց թողնել: Օրինակ՝ կարելի է գրել 10(1 * + 0) .

Սահմանում 5.1. Երկու կանոնավոր արտահայտություններ r-ը և p-ն համարվում են համարժեք, եթե նրանց կողմից ներկայացված լեզուները նույնն են, այսինքն. L r = L p . Այս դեպքում գրում ենք r = p.

Հեշտ է ստուգել, ​​օրինակ, հետեւյալը կանոնավորի հատկություններըգործողությունները:

• r + p= p+ r (միության փոխադարձություն),
• (r+p) +q = r + (p+q) (միության ասոցիատիվություն),
• (r p) q = r (p q) (կապակցման ասոցիատիվություն),
• (r *) * = r * (կրկնվող անզորություն),
• (r +p) q = rq + pq(բաշխվածություն):

Օրինակ 5.1. Որպես օրինակ ապացուցենք ոչ այնքան ակնհայտ հավասարությունը՝ (r + p) * = (r * p *) *:

Թող L 1-ը լինի այն լեզուն, որը ներկայացված է ձախ կողմով, իսկ L 2-ը՝ աջով: Դատարկ բառը պատկանում է երկու լեզուներին: Եթե ​​բառը դատարկ չէ, ապա կրկնության սահմանմամբ այն կարող է ներկայացվել որպես լեզվին պատկանող ենթաբառերի միացում։ Բայց այս լեզուն L"=L r * L p * (ինչու՞) լեզվի ենթաբազմություն է . Ընդհակառակը, եթե բառը , ապա այն ներկայացվում է որպես L " լեզվին պատկանող ենթաբառերի միացում: Նման v ենթաբառերից յուրաքանչյուրը ներկայացված է ձևով. v= v 1 1 ... v k 1 v 1 2 ... v l 2

, որտեղ բոլորի համար i=1, ... , k-ն ենթաբառ է, իսկ բոլորի համար j=1, ... , l-ն ենթաբառ (հնարավոր է, որ k-ն կամ l-ն հավասար լինի 0-ի): Բայց սա նշանակում է, որ w-ը ենթաբառերի միացում է, որոնցից յուրաքանչյուրը պատկանում է և, հետևաբար, .

Սովորական լեզու Լեզվի տեսության մեջսովորական հավաքածու (կամ,կանոնավոր լեզվով

) կոչվում է ֆորմալ լեզու, որը բավարարում է հետևյալ հատկությունները. Այս պարզ հատկություններն այնպիսին են, որ կանոնավոր բազմությունների դասը հարմար է ուսումնասիրել որպես ամբողջություն, և ստացված արդյունքները կիրառելի են ֆորմալ լեզուների շատ կարևոր դեպքերում։ Այսինքն՝ կանոնավոր բազմություն հասկացությունը մաթեմատիկական կառուցվածքի օրինակ է։

Սովորական հավաքածուի սահմանում Թող Σ լինի վերջավոր այբուբեն։Սովորական հավաքածու

№.	R(Σ)-ը Σ այբուբենում սահմանվում է հետևյալ ռեկուրսիվ հատկություններով.	Սեփականություն
1		Նկարագրություն
2		Դատարկ բազմությունը Σ այբուբենի կանոնավոր բազմություն է
3		Միայն մեկ դատարկ տողից բաղկացած բազմությունը Σ այբուբենի կանոնավոր բազմություն է
4		Σ այբուբենի ցանկացած մեկ խորհրդանիշից բաղկացած հավաքածուն Ս այբուբենի կանոնավոր հավաքածու է
5		Եթե ​​Σ այբուբենում որևէ երկու բազմություն կանոնավոր է, ապա Ս այբուբենի կանոնավոր բազմություն է նաև դրանց միավորումը։
6		Եթե ​​Σ այբուբենում որևէ երկու բազմություն կանոնավոր է, ապա դրանց տարրերի զույգերի բոլոր հնարավոր համակցություններից կազմված բազմությունը նույնպես կանոնավոր բազմություն է Σ այբուբենում։
		Եթե ​​որեւէ բազմություն Σ այբուբենում կանոնավոր է, ապա նրա տարրերի բոլոր հնարավոր համակցությունների բազմությունը նույնպես կանոնավոր բազմություն է Σ այբուբենում։

Ոչ այլ ինչ, քան հետևյալը, կանոնավոր բազմություն է Σ այբուբենում

• Տես նաև

Ավտոմատների մոտեցման հիման վրա վերլուծիչի կառուցում

Վիքիմեդիա հիմնադրամ.

2010 թ.Տեսեք, թե ինչ է «Կանոնավոր լեզուն» այլ բառարաններում. կանոնավոր լեզու

- (լատիներեն regularius, regula կանոնից)։ Ճիշտ, ճիշտ դասավորված, պատրաստված։ Մեքենայի կանոնավոր աշխատանքը: Նույնիսկ կաթված: Կանոնավոր կյանք. Ճիշտ, պարկեշտ, միապաղաղ կյանք. Ռուսաց լեզվում ընդգրկված օտար բառերի բառարան... ... Ռուսաց լեզվի օտար բառերի բառարան

սմ… Հոմանիշների բառարան

Հին գրավոր լեզու- Երկար գրավոր ավանդույթներ ունեցող լեզու, այսինքն՝ մի քանի դար առաջ ստացել է տվյալ լեզվի կառուցվածքին հարմարեցված գրավոր լեզու, և լեզվի գրավոր տարբերակի գործունեությունը եղել է ոչ թե էպիզոդիկ, այլ կանոնավոր՝ հետ... . .. Սոցիալեզվաբանական տերմինների բառարան

Այս տերմինն այլ իմաստներ ունի, տես Կեչուա։ Կեչուա Ինքնանվանումը` Qhichwa Simi, Runa Simi Երկրներ ... Վիքիպեդիա

Շենքի շրջանակը՝ սյուների կամ սյուների ցանցով, որը հիմնված է նույն չափի (բուլղարերեն, Български) միատեսակ կմախքի (չեխերեն, Čeština) pravidelný skelet (գերմաներեն, գերմաներեն) regelmäßiges Skelett (հունգարերեն, մագյարերեն) szabályos... ... Շինարարական բառարան

- [FRENCH PARK] այգի, որն ունի երկրաչափական կանոնավոր դասավորություն, սովորաբար առանցքային դասավորություն (բուլղարերեն; Български) frenski park (չեխերեն; Čeština) francouzský park (գերմաներեն; Deutsch) regelmäßiger Park; Französischer Park…… Շինարարական բառարան

Կեչուա Ինքնանունը՝ Qhichwa Simi, Runa Simi Երկրներ՝ Արգենտինա, Բոլիվիա, Կոլումբիա, Պերու, Չիլի, Էկվադոր Տարածաշրջաններ՝ Անդեր Պաշտոնական կարգավիճակ՝ Պերու ... Վիքիպեդիա

Տագալերեն լեզու- (tagal, tagala, tagalo; tagalog) ֆիլիպինյան լեզուներից մեկը։ Սկզբնական բաշխման տարածքը գտնվում է Ֆիլիպինների Հանրապետության քաղաքական, տնտեսական և մշակութային ամենակարևոր շրջանում՝ կղզու կենտրոնական և հարավային հատվածներում... ... Լեզվաբանական հանրագիտարանային բառարան

Գրքեր

• Ածանցյալ բայեր. Ֆիններեն քերականության գաղտնիքները. Դասագիրք, Safronov V.D.. Ձեռնարկը նվիրված է ռուսալեզու կրթական գրականության ֆիննական քերականության ամենահետաքրքիր և անբավարար ներկայացված բաժիններից մեկին` ածանցյալ բայերին: Կազմվում են բայերից և անուններից...

Կանոնավոր քերականությունները, վերջավոր ավտոմատները և կանոնավոր բազմությունները (և դրանք ներկայացնող կանոնավոր արտահայտությունները) կանոնավոր լեզուները նշելու երեք տարբեր եղանակներ են:

Հայտարարություն

Լեզուն PM է, եթե և միայն այն դեպքում, եթե այն նշված է ձախ-գծային (աջ-գծային) քերականությամբ: Լեզուն կարող է սահմանվել ձախ-գծային (աջ-գծային) քերականությամբ, եթե և միայն այն դեպքում, եթե այն կանոնավոր բազմություն է:

Լեզուն PM է, եթե և միայն այն դեպքում, եթե այն նշված է վերջավոր վիճակի մեքենայի կողմից: Լեզուն ճանաչվում է պետական ​​մեքենայի կողմից, եթե և միայն այն դեպքում, եթե դա վարչապետ է:

Այս երեք մեթոդներն էլ համարժեք են։ Կան ալգորիթմներ, որոնք թույլ են տալիս այս եղանակներից մեկով սահմանված լեզվին կառուցել մեկ այլ մեթոդ, որը սահմանում է նույն լեզուն: Այս ալգորիթմների մանրամասն նկարագրությունը հասանելի է գրականության մեջ (տես ցանկը):

Օրինակ՝ աջ-գծային քերականությամբ սահմանված լեզվի համար կանոնավոր արտահայտություն գտնելու համար անհրաժեշտ է կառուցել և լուծել կանոնավոր գործակիցներով հավասարումների համակարգ։

Ծրագրավորման լեզուների տեսության մեջ ամենակարևոր դերը խաղում է CA-ների և կանոնավոր քերականությունների համարժեքությունը, քանի որ նման քերականություններն օգտագործվում են ծրագրավորման լեզուների բառարանային կառուցվածքները սահմանելու համար: Հայտնի քերականության վրա հիմնված ավտոմատ ստեղծելով՝ մենք ստանում ենք տվյալ լեզվի ճանաչող։ Այս կերպ հնարավոր է լինում լուծել լեզվի բառապաշարների վերլուծության խնդիրը։

Հայտնի կանոնավոր քերականության վրա հիմնված CA կառուցելու համար այն պետք է վերածվի ավտոմատ ձևի: Ավտոմատի վիճակների բազմությունը կհամապատասխանի քերականության ոչ տերմինալ նշանների բազմությանը։ 2.3.2 Կանոնավոր լեզուների հատկությունները

Բազմությունը ինչ-որ գործողության դեպքում կոչվում է փակ, եթե նրա որևէ տարրի վրա այս գործողությունը կատարելու արդյունքում ստացվում է նույն բազմությանը պատկանող նոր տարր։

Կանոնավոր բազմությունները փակվում են հատման, միացման, գումարման, կրկնության, շաղկապման, սիմվոլների անունները փոխելու և նշանների համար տողերի փոխարինման գործողությունների ներքո:

Սովորական լեզուների համար շատ խնդիրներ կարող են լուծվել, որոնք անլուծելի են այլ տեսակի լեզուների համար։ Օրինակ, հետևյալ խնդիրները լուծելի են, անկախ նրանից, թե որ ձևով է նշված լեզուն.

Համարժեքության խնդիր. Տրված է երկու կանոնավոր լեզու՝ L 1 (V) և L 2 (V): Պետք է որոշել, թե արդյոք դրանք համարժեք են։

Լեզվին պատկանելու շղթայի խնդիրը. Տրվում է կանոնավոր լեզու L(V)՝ V * նիշերի շարան։ Պետք է ստուգել՝ արդյոք այս շղթան պատկանում է լեզվին։

Լեզվի դատարկության խնդիրը. Տրվում է կանոնավոր լեզու L(V): Անհրաժեշտ է ստուգել, ​​թե արդյոք այս լեզուն դատարկ է, այսինքն. գտեք առնվազն մեկ շղթա՝ L(V):

Երբեմն անհրաժեշտ է ապացուցել, թե արդյոք որոշակի լեզուն կանոնավոր է: Եթե ​​հնարավոր է նշել այս լեզուն դիտարկված ձևերից մեկով, ապա այն կանոնավոր է։ Բայց եթե նման մեթոդ հնարավոր չէ գտնել, անհայտ է, թե լեզուն կանոնավոր չէ, թե՞ պարզապես հնարավոր չէր գտնել այն հստակեցնելու միջոց։ Գոյություն ունի պարզ մեթոդ՝ ստուգելու, թե արդյոք տվյալ լեզուն կանոնավոր է։ Ապացուցված է, որ եթե որոշակի լեզվի համար այսպես կոչված ընդլայնման լեմմա, ապա այն կանոնավոր է: Եթե ​​այս լեմման բավարարված չէ, լեզուն կանոնավոր չէ։

Աճի լեմման ձևակերպված է հետևյալ կերպ. Եթե ​​տրվի այս լեզվին պատկանող կանոնավոր լեզու և բավականին երկար խորհրդանիշների շղթա, ապա դրանում կարելի է գտնել ոչ դատարկ ենթաշար, որը կարող է կրկնվել այնքան անգամ, որքան ցանկանաք, և այս կերպ ստացված բոլոր շղթաները նույնպես կպատկանեն կանոնավոր լեզվի հարցը:

Ձևականորեն լեմման գրված է հետևյալ կերպ. Եթե ​​տրված է L լեզու, ապա p>0 հաստատունն այնպիսին է, որ եթե L և p, ապա շղթան կարող է գրվել այն ձևով, որտեղ 0.

Օրինակ. Դիտարկենք L=(a n b n n>0) լեզուն: Փաստենք, որ դա կանոնավոր չէ՝ օգտագործելով լեզուների տարածման լեմման։

Թող այս լեզուն կանոնավոր լինի, ապա դրա համար պետք է պահպանվի ընդլայնման լեմման: Վերցնենք այս լեզվի մի շղթա = a n b n և գրենք ձևով: Եթե ​​a + կամ b + , ապա i-ի շղթան չի պատկանում որևէ i-ի լեզվին, ինչը հակասում է լեմայի պայմաններին: Եթե ​​a + b + , ապա 2-րդ շղթան նույնպես չի պատկանում L լեզվին։ Մենք ստացել ենք հակասություն, հետևաբար՝ լեզուն կանոնավոր չէ։

Սովորական հավաքածուներև կանոնավոր արտահայտություններ

Սովորական հավաքածուներ

Այս բաժնում մենք կքննարկենք վերջավոր բառարանի վրա գտնվող շղթաների մի շարք, որոնք շատ հեշտ է նկարագրել ինչ-որ բանաձևերով: Այս հավաքածուները կոչվում են կանոնավոր:

Սահմանում 1.Թող V 1 Եվ V 2 - շատ շղթաներ. Սահմանենք երեք գործողությունայս հավաքածուների վրա:

Միություն՝ V 1 V 2 =(|   V 1 ) կամ   V 2:

Միացում (արտադրանք, սոսնձում)՝ Vl V2 = (|  V 1 ,  V 2 ) Միացման գործողության նշանը սովորաբար բաց է թողնվում։

Օրինակ՝ V, = (abc, ba), V 2 = (b, cb): V1V2 =(abcb, abccb, bab, bacb):

Նշենք V-ով n n բազմությունների արտադրյալը V:V n =VV...V,V° =() (այստեղ  դատարկ շղթա է):

Օրինակ՝ V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc):

3. Կրկնություն՝ V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

Օրինակ՝ V = (a, bc), V* = (, a, bc, aa, abc, bcbc, bca, aaa, aabc,...):

Սահմանում 4.13.Սովորական բազմությունների դաս՝ վերջավոր բառարանի վրաՎ սահմանելգնում է այսպես.

միություն ST;

ST միացում;

կրկնություն S* և T*.

5. Եթե բազմությունը չի կարող կառուցվել 1-4 կանոնների վերջավոր թվով կիրառություններով, ապա այն անկանոն է։

Կանոնավոր բազմությունների օրինակներ՝ (ab, ba)* (aa); (բ) ((c)(d, ab)*): Անկանոն բազմությունների օրինակներ. (a n b n | n > 0); ( | շղթայում  a և b նշանների քանակը համընկնում է):

Կանոնավոր արտահայտություններ

Կանոնավոր բազմությունները լավ են, քանի որ դրանք կարելի է շատ պարզ նկարագրել բանաձևերով, որոնք մենք կանվանենք կանոնավոր արտահայտություններ։

Սահմանում 2.Կանոնավոր արտահայտությունների դաս վերջավոր բառարանի վրաՎ սահմանելգնում է այսպես.

դրանց գումարը R1+R2;

նրանց արտադրանքը R1R2;

դրանց կրկնությունը R1* և R2*։

4. Եթե արտահայտությունը չի կառուցվում 1-3 կանոնները վերջապես կիրառելով, ապա այն կանոնավոր չէ։

Աշխատանքի խորհրդանիշը կարող է բաց թողնել: Փակագծերի քանակը նվազեցնելու համար, ինչպես ցանկացած հանրահաշիվում, օգտագործվում են գործողության առաջնահերթությունները. աշխատանքը ավելի քիչ առաջնահերթություն ունի. ավելացումն ունի ամենացածր առաջնահերթությունը:

Կանոնավոր արտահայտությունների օրինակներ՝ ab + bа*; (aa)*b + (c + dab)*.

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

Թող R^ լինի կանոնավոր բազմություն, որը համապատասխանում է R կանոնավոր արտահայտությանը: Ապա.

Այսպիսով, կանոնավոր արտահայտությունը վերջավոր բանաձեւ է, որը սահմանում է անսահման թվով շղթաներ, այսինքն՝ լեզու։

Դիտարկենք կանոնավոր արտահայտությունների օրինակներ և դրանց համապատասխան լեզուները:

Կանոնավոր արտահայտություն	Համապատասխան լեզու
	Բոլոր տողերը, որոնք սկսվում են b-ով, որին հաջորդում են կամայական թվով նիշեր a
	a-ի և b-ի բոլոր տողերը, որոնք պարունակում են b-ի ուղիղ երկու երևույթ
	a և b-ի բոլոր շղթաները, որոնցում b նշանները հայտնվում են միայն զույգերով
(ա+բ)*(աա+բբ)(ա+բ)*	a և b-ի բոլոր շղթաները, որոնք պարունակում են առնվազն մեկ զույգ հարակից a կամ b
(0+1)*11001(0+1)*	11001 ենթաշղթա պարունակող 0 և 1 բոլոր շղթաները
	a-ի և b-ի բոլոր տողերը՝ սկսած a-ով և վերջացրած b-ով

Ակնհայտ է, որ տողերի բազմությունը կանոնավոր է, եթե և միայն այն դեպքում, երբ այն կարող է ներկայացվել կանոնավոր արտահայտությամբ: Այնուամենայնիվ, շղթաների միևնույն խումբը կարող է ներկայացվել տարբեր կանոնավոր արտահայտություններով, օրինակ՝ a խորհրդանիշներից բաղկացած և առնվազն երկու a պարունակող շղթաների մի շարք կարող է ներկայացվել հետևյալ արտահայտություններով՝ aa*a; ա*աաա*; աաա*; a*aa*aa* և այլն:

Սահմանում 3.Երկու կանոնավոր արտահայտություն R1 Եվ R2 կոչվում են համարժեք (նշվում է Rl = R2) հետո և միայն այն ժամանակ, երբՌ1 ^ = Ռ2 ^ .

Այսպիսով, aa*a = a*aaa* = aaa* = a*aa*aa*: Հարց է առաջանում, թե ինչպես կարելի է որոշել երկու կանոնավոր արտահայտությունների համարժեքությունը։

Թեորեմ1 . Ցանկացած կանոնավոր արտահայտությունների համարՌ, Ս ԵվՏ արդար:

Այս հարաբերությունները կարելի է ապացուցել՝ ստուգելով համապատասխան շղթաների բազմությունների հավասարությունը։ Դրանք կարող են օգտագործվել կանոնավոր արտահայտությունները պարզեցնելու համար: Օրինակ՝ b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b: Այստեղից բ (b + aa*b) = ba*b, որն ակնհայտ չէ։

Քլինի թեորեմը

Կանոնավոր արտահայտությունները վերջնական բանաձևերն են, որոնք սահմանում են կանոնավոր լեզուներ: Բայց վերջավոր վիճակի մեքենաները նույնպես ունեն նմանատիպ հատկություն՝ նրանք նաև սահմանում են լեզուներ: Հարց է առաջանում՝ ինչպե՞ս են միմյանց հետ առնչվում վերջավոր վիճակի մեքենաներով և կանոնավոր արտահայտություններով սահմանված լեզուների դասերը։ Նշենք Եվ շատ ավտոմատ լեզուներ, R-ն կանոնավոր լեզուների ամբողջություն է։ Ամերիկացի մաթեմատիկոս Սթիվեն Քլինն ապացուցեց հետևյալ թեորեմը.

Թեորեմ2 . (Քլինի թեորեմ:) Կանոնավոր բազմությունների և ավտոմատ լեզուների դասերը համընկնում են, այսինքն. A = Ռ .

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

Եկեք ներկայացնենք անցումային գրաֆիկի մոդելը որպես վերջավոր ավտոմատ մոդելի ընդհանրացում։ Անցումային գրաֆիկն ունի մեկ սկզբնական և կամայական թվով վերջնական գագաթներ, և ուղղորդված եզրերը նշվում են, ի տարբերություն վերջավոր ավտոմատի, ոչ թե սիմվոլներով, այլ կանոնավոր արտահայտություններով։ Անցումային գրաֆիկը ընդունում է a շղթա Ապատկանում է մի շարք շղթաների, որոնք նկարագրված են R 1 R 2 ...R n կանոնավոր արտահայտությունների արտադրյալով, որոնք նշում են սկզբնական գագաթից մինչև վերջնական գագաթներից մեկը ուղին։ Անցումային գրաֆիկով թույլատրված շղթաների բազմությունը կազմում է նրա կողմից թույլատրված լեզուն։

Բրինձ. 1. Անցումային գրաֆիկ

Նկ. Նկար 1-ը ցույց է տալիս անցումային գրաֆիկ, որը թույլ է տալիս, օրինակ, շղթայական abbca, քանի որ s->r->p->s->r->q ուղին, որը տանում է դեպի վերջնական q վիճակ, նշված է շղթայով. կանոնավոր արտահայտություններ ab* c*a. Վերջավոր վիճակի մեքենան անցումային գրաֆիկի հատուկ դեպք է, և, հետևաբար, բոլոր լեզուները, որոնք ընդունվում են վիճակի մեքենաների կողմից, նույնպես աջակցվում են անցումային գրաֆիկներով:

Թեորեմ 3.Յուրաքանչյուր ավտոմատ լեզու սովորական հավաքածու է, A  Ռ.

Ապացույց. Մեկ սկզբնական և մեկ վերջնական գագաթով անցումային գրաֆիկը, որում սկզբնականից մինչև վերջնական գագաթը պիտակավորված է R կանոնավոր արտահայտությամբ, ընդունում է R^ լեզուն (նկ. 1):

Բրինձ. 2. Անցումային գրաֆիկ, որն ընդունում է սովորական լեզու FT

Այժմ ապացուցենք, որ յուրաքանչյուր ավտոմատ լեզու կանոնավոր բազմություն է՝ կրճատելով անցումային ցանկացած գրաֆիկ՝ առանց փոխելու այն լեզուն, որը թույլ է տալիս համարժեք ձևի (նկ. 2):

Ցանկացած վերջավոր ավտոմատ և ցանկացած անցումային գրաֆիկ միշտ կարող է ներկայացվել նորմալացված ձևով, որտեղ կա միայն մեկ սկզբնական գագաթ՝ միայն ելքային եզրերով և միայն մեկ վերջնական գագաթ՝ միայն մուտքային եզրերով (նկ. 3):

Բրինձ. 3. Անցումային գրաֆիկ մեկ սկզբնական և մեկ վերջնական գագաթով

Նորմալացված ձևով ներկայացված անցումային գրաֆիկով կարող են կատարվել երկու կրճատման գործողություններ՝ եզրերի կրճատում և գագաթի կրճատում, մինչդեռ պահպանելով այս անցումային գրաֆիկով թույլատրված լեզուն.

ա) կողերի կրճատում.

Բ ) գագաթի կրճատում (փոխարինումը կատարվում է p գագաթով անցնող յուրաքանչյուր ուղու համար, որին հաջորդում է դրա հեռացումը որպես անհասանելի վիճակ).

Ակնհայտ է, որ յուրաքանչյուր կրճատման գործողություն չի փոխում անցումային գրաֆիկի կողմից ճանաչված լեզուն, այլ նվազեցնում է կամ եզրերի կամ գագաթների քանակը, և վերջում կրճատումները անցումային գրաֆիկը կբերեն Նկ. 2. Թեորեմն ապացուցված է՝ յուրաքանչյուր ավտոմատ լեզու կանոնավոր բազմություն է։

Օրինակ

Թող վերջավոր A մեքենան տրվի.

Մենք կառուցում ենք համարժեք անցումային գրաֆիկ՝ նորմալացված ձևով:

Vertex կրճատում 3:

Աղեղների կրճատում և R = R կանոնի կիրառում:

Vertex կրճատում 2:

Աղեղի և գագաթի կրճատում 1:

Այսպիսով, ավտոմատ A-ի կողմից ճանաչված լեզուն տրվում է կանոնավոր արտահայտությամբ՝ R A = b+(a+bb)(b+ab)*a:

Եկեք ապացուցենք Քլինի թեորեմը հակառակ ուղղությամբ։

Թեորեմ 2.Յուրաքանչյուր սովորական հավաքածու ավտոմատ լեզու է. R Ա.

Ապացույց.Եկեք ցույց տանք, որ R յուրաքանչյուր կանոնավոր արտահայտության համար կարող է կառուցվել վերջավոր ավտոմատ A r (հնարավոր է ոչ որոշիչ), որը ճանաչում է R-ի կողմից նշված լեզուն: Նման ավտոմատները մենք կսահմանենք ռեկուրսիվորեն:

(Ա-ի սկզբնական և վերջնական վիճակները միավորված են):

Օրինակ(շարունակություն)