ufydb[bkjs hfbvt cbv,jkjt,bc cfchekb cbvhfdkt å ^ hjvtkcfw deojljs fkaf,tnb& fkaf,tnb ufvjb.tyt,f yt,bcvbth ,eyt,hbd se ajhvfkeh tyfib& cbv,jkjc mdti buekbc[vt,f yt,bcvbthb ybifyb^ hjvtkbw itb’kt,f itud[dltc ntmcnib& cbv,jkjsf yt,bcvbth cfchek vbvltdhj,fc deojljs ]fzdb ~pju]th vfc eojlt,ty cbn.dfc fy cnhbmjyc`& bcts ]fzdc^ hjvtkbw fh itbwfdc fhwths cbv,jkjc deojljs wfhbtkb ]fzdb lf fdqybiyjs e cbv,jkjsb& ]fzdt,bc yt,bcvbth cfchek vbvltdhj,fc deojljs ntmcnb& buekbc[vt,f^ hjv ]fzdt,b ntmcnib thsbvtjhbcfufy ufvj.jabkbf cgtwbfkehb [fhdtpbc ybiybs& [fhdtpbc ybiyfl ajhvfkeh tyt,ib ufvjb.tyt,f cbv,jkj # ^ [jkj ntmcnib vbc fqcfybiyfdfl ufvjb.tyt,f wfhbtkb flubkb& ntmcnib ufvj.tyt,ek wfhbtk flubkc xdty xfdsdkbs cbv,jkjl& [fhdtpbc ybifyb fh itb’kt,f itlbjltc ]fzdib^ hflufyfw bub ufvjb.tyt,f ]fzdt,bc ufyvfwfkrtdt,kfl^ vfuhfv bub .jdtksdbc itlbc fkaf,tnib& wfkrtek cbv,jkjt,c pjuflfl a, b, c, d fcjt,bs fqdybiyfds^ [jkj ]fzdt,c t, u, v, w, x, y, lf z fcjt,bs fqdybiyfds& cⁱ-sb fqdybiyfds ]fzdc^ hjvtkbw i hfjltyj,f c cbv,jkjcfufy itlut,f& se udfmdc jhb x lf y ]fzdb^ vfiby xy ]fzdc x lf y ]fzdt,bc rjyrfntyfwbf tojlt,f lf y-bc x-bc vfh]dybd vbothbs vbbqt,f& xdty fh ufvjdb.tyt,s cgtwbfkeh cbv,jkjc rjyrfntyfwbbc jgthfwbbc fqcfybiyfdfl& itvjnfybkb itsfy[vt,t,blfy ufvjvlbyfhtj,c^ hjv a⁰ =e lf a²=aa. htrehcbekfl^ hfbvt ]fzdb å fkaf,tnib ufybcfpqdht,f itvltuyfbhfl%

1& e fhbc ]fzdb å fkaf,tnib*

2& se x fhbc ]fzdb å fkaf,tnib lf a Î å , vfiby xa fhbc ]fzdb å -ib*

3& hfbvt z ]fzdb fhbc ]fzdb å -ib v[jkjl lf v[jkjl vfiby^ se bub 1 lf 2 otct,bs vbbqt,f&

buekbc[vt,f^ hjv ex=xe=x& se x=c₁c₂...c_n^ vfiby c_nc_n-1...c₁ ]fzdc tojlt,f x-bc it,heyt,ekb ]fzdb lf x^R-bs fqdybiyfds& se udfmdc yxz ]fzdb^ vfiby y-c tojlt,f yxz-bc ghtabmcb^ [jkj z-c tojlt,f yxz-bc ceabmcb^ [jkj x-c byabmcb tojlt,f& x ]fzdbc cbuh’t | x| -bs fqdybiyjs lf ufydvfhnjs itvltuyfbhfl% se x=e, vfiby | x| = 0* se x=a₁a₂...a_n^ vfiby | x| =n. vfufkbsfl^ | aabcd| =5. ]fzdt,bc L hfbvt cbvhfdktc å fkaf,tnib deojljs L tyf å
fkaf,tnib& tc ufyvfhnt,f vjbwfdc hjujhw ajhvfkeh tyt,c fctdt ,eyt,hbd tyt,cfw& å * -bs fqdybiyjs tyf^ hjvtkbw vjbwfdc .dtkf ]fzdc å fkafdbnblfy e ]fzdbc xfsdkbs^ [jkj å * - bs fqdybiyjs cbvhfdkt å * -{ e} ^ t&b& å * cbvhfdkt wfhbtkb ]fzdbc ufhlf& å * - c eojlt,ty eybdthcfkeh tyfc å fkaf,tnib^ hflufy yt,bcvbthb L tyf å fkaf,tnib fhbc vbcb mdtcbvhfdkt& lfghjuhfvt,bc FORTRAN tyf fhbc tyf xdtyb ufyvfhnt,bs FORTRAN-bc fkaf,tnib^ se ]fzdt,fl fdbqt,s cbynfmcehfl cojh ghjuhfvt,c& fctdt mfhsekb tyf fhbc tyf xdtyb ufyvfhnt,bs mfhsek fkaf,tnib^ se cojh mfhsek obyflflt,t,c fdbqt,s ]fzdt,fl&

ajhvfkehb uhfvfnbrt,b

hjujhw obyf gfhfuhfablfy erdt dbwbs yt,bcvbthb L ajhvfkehb tyf itb’kt,f xfbothjc fct%
LÍ å * ^ cflfw å hfbvt fkaf,tnbf& fctsb tyf .jdtksdbc ecfchekjf^ se xdty fh itdpqelfds ]fzdbc cbuh’tc& hflufy xdty itvlujvib lfudfbynthtct,c bctsb tyt,b^ hjvtksf ]fzdt,c fmds cfchekb cbuh’t^ fvbnjv xdty .jdtksdbc dbuekbc[vt,s^ hjv | x| £ n^ cflfw n fhfefh.jabsb vstkb hbw[dbf lf xÎ L& hfbvt L tybc vjwtvf
itb’kt,f vbcb ]fzdt,bc xfvjsdkbs^ se tyf cfchekbf& vfufkbsfl^ fcts itvs[dtdfibw rb vje[th[t,tkbf tybc vjwtvf vbcb ]fzdt,bc xfvjothbs& fvbnjv^ ,eyt,hbdbf vjb’t,yjc bctsb [th[b^ hjvtkbw chekfl fqothlf tyfc lf vfhnbdb bmyt,jlf bvbc itcfvjovt,kfl^ tresdybc se fhf hfbvt x ]fzdb fv tyfc& pju]th itcf’kt,tkbf L tyf
xfbothjc hfbvt ajhvekbs^ vfufkbsfl { aⁿ bⁿ c^{n |} n ³ 0} & vfuhfv ajhvekbs tybc ofhvjlutyf [th[lt,f bidbfs itvs[dtdt,ib& fvbnjv^ eylf vjb’t,yjc c[df [th[b& ths-ths fcts [th[c ofhvjflutyc tybc vjwtvf ofhvjvmvytkb uhfvfnbrbc cfiefkt,bs& vtjht upfc ofhvjflutyc tybc vjwtvf rth’j fkujhbsvbs^ hjvtkbw fvsfdht,c veifj,fc se ]fzdb tresdybc tyfc& xdty itdxthlt,bs gbhdtk [th[pt^ rth’jl [jvcrbc uhfvfnbrt,pt& f[kf^ xdty itdelut,bs fctsb uhfvfnbrt,bc fqothfc ]th fhfajhvfkehfl^ itvltu rb pecnfl ufydvfhnfds
vfs&
hfbvt L tybc fqcfothfl ufydb[bkjs jhb cbvhfdkt& thsb cbvhfdktf fv tybc fkaf,tnb å ^ hjvtkcfw deojlt,s nthvbyfkeh cbv,jkjsf cbvhfdktc lf vtjht cbvhfdktf cbv,jkjsf N cbvhfdkt^ hjvtkbw fctdt cfchekbf lf deojlt,s fhfnthvbyfkeh cbv,jkjsf cbvhfdktc& ufydb[bkjs otct,bc P cfchekb cbvhfdkt^ hjvtkbw ofhvjflutyc ~a , b ` o.dbksf cbvhfdktc^ cflfw ~a , b ` ~N È å `* N ( N È å ) * C ( N È ) * cbvhfdkbc  hfbvt tktvtynbf& t&b& otcbc gbhdtkb tktvtynb fewbkt,kfl itbwfdc
ths fhfnthvbyfkeh cbv,jkjc vfbyw^ vfiby hjwf vtjht tktvtynb itb’kt,f b.jc wfhbtkb ]fzdb& otcb
itb’kt,f xfbothjc fctw a ® b . xdty itvlujvib ufvjdb.tyt,s otcbc xfothbc vtjht cf[tc& N cbvhfdktib fhct,j,c cgtwbfkehfl ufvj.jabkb cbv,jkj^ hjvtkcfw S-bs fqdybiyfds lf deojlt,s cfo.bc cbv,jkjc& .jdtksdbc dbo.t,s L tybc hfbvt ]fzdbc vbqt,fc P cbvhfdkbc hfbvt otcbs^ hjkvtkcfw fmdc cf[t S ® a lf itvltu a -ib ~a = a <sub>1b a 2</sub>` vbc hfbvt mdt]fzdc b -c dwdkbs g -sb^ cflfw b ® g  P –c hfbvt otcbf& vbdbqt,s ]fzdc a _{1g a 2} fctdt dbmwtdbs fv ]fzdbc vbvfhsfw^ cfyfv fh lfcheklt,f tc ghjwtcb& se itltufl vbdbqts ]fzdb^ hjvtkbw v[jkjl nthvbyfkeh cbv,jkjt,c itbwfdc^ vfiby vfc dfw[flt,s L tybc x ]fzdfl& .dtkf fctsb x
]fzdt,bc thsj,kbj,f ufycfpqdhfdc L tyfc lf vfc tojlt,f ptvjs fqothbkb uhfvfnbrbs ufycfpqdhekb tyf& ptvjs fqothbkb uhfvfnbrf ajhvfkehfl ufybcfpqdht,f itvltuyfbhfl% G=(N , å , R , S ) js[tekc deojlt,s uhfvfnbrfc^ cflfw
1& N - fhfnthvbyfkehb cbv,jkjt,bc cfchekb cbvhfdktf*

3& P fhbc ~ N È å ) * N ( N È å ) * C ( N È å ) * cbvhfdkbc cfchekb mdtcbvhfdkt*

4& SÎ N ufvj.jabkb cbv,jkjf^ hjvtkcfw cfo.bcb cbv,jkj tojlt,f&

G uhfvfnbrf ufycfpqdhfdc L ( G ) tyfc^ hjvtkcfw G uhfvfnbrbs ufycfpqdhekb tyf tojlt,f& itvjdbnfyjs htrehcbekfl cgtwbfkehb cf[bc ]fzdt,b^ hjvtksfw G uhfvfnbrbc ufvj.dfyflb ]fzdt,b tojlt,fs%

1& S - ufvj.dfyflb ]fzdbf*

2& se a b g - ufvj.dfyflb ]fzdbf lf b ® d tktvtynbf P-cb^ vfiby a d g ufvj.dfyflb ]fzdbf fuhtsdt&

ufvj.dfyflb ]fzdb^ hjvtkbw fh itbwfdc fhfnthvbyfkeh cbv,jkjt,c tojlt,fs G uhfvfnbrbs ofhvjmvybkb nthvbyfkehb ]fzdt,b&
nthvbyfkeh ]fzdsf thsj,kbj,f mvybc G uhfvfnbrbs ofhvjmvybk L tyfc lf fqbybiyt,f L (G )-bs& f[kf itvjdbnfyjs Þ lfvjrblt,ekt,f bvbcfsdbc^ hjv vfhnbdfl xfdothjs L(G ) tyf& se a₁ba₂ ufvj.dfyflb ]fzdbf G uhfvfnbrfib lf b ® g Î R ^ vfiby a₁ba_2Þ a₁ga₂& Þ lfvjrblt,ekt,bc nhfypbnekb xfrtndf fdqybiyjs Þ + -bs^ [jkj nhfypbnekb lf htaktmcehb xfrtndf Þ * -sb& fvbc itvltu L ( G ) tyf itb’kt,f xfbothjc itvltuyfbhfl% L(G) = { w | w Î å * , SÞ * w} . ufydb[bkjs uhfvfnbrbc vfufkbsb^ hjvtkbw ufycfpqdhfdc fhbsvtnbrek ufvjcf[ekt,fsf tyfc^ hjvtkbw itbwfdc fhbsvtnbrek jgthfwbt,c itrht,fc lf ufvhfdkt,fc^
bltynbabrfnjhc a-c lf vhudfk ahx[bkt,c& dsmdfs G₁= ( { E , T , F } , { a, + , * , ( ,) } , R , E ) , cflfw P itbwfdc otct,c

E ® E + T | T
T ® T * E | F
F® ( E ) | a

vfufkbsfl^ ]fzdb ~ a+ a )* a tresdybc L(G₁)-c^ hbc xdtyt,fw vfhnbdbf itvltub ufvj.dfybs%
E Þ T Þ T * FÞ F* FÞ ( E ) * FÞ ( E + T ) * FÞ ( T + T ) * FÞ ( F+ T ) * FÞ (
a+ T) * FÞ (a+ F)* FÞ ( a+ a)+FÞ ( a+a)* a. itdybiyjs^ hjv fhct,j,c c[df ufvj.dfyt,bw^ hjvkt,bw vjudwtvty bubdt itltuc& bcbyb vbbqt,bfy ufvj.tyt,ekb otct,bc hbubc itwdkbs^ hjwf fhct,j,c hfvjltybvt fknthyfnbdf& tc uhfvfnbrf cfbynthtcjf bvbs^ hjv se xdty vfc lfdevfnt,s f[fk otct,c c[df fhbsvtnbrekb jgthfwbt,bcfsdbc vfsb ghbjhbntnt,bc ufsdfkbcobyt,bs^ itb’kt,f vbdbqjs uhfvfnbrf ghjuhfvbht,bc afhsjl wyj,bk tyt,ib fhbsvtnbrekb ufvjcf[ekt,bc ufycfcfpqdhfdfl& fv vfufkbsib xdty ufvjdb.tyts
otct,bc itvjrkt,ekb xfothf& cfpjufljl^ se xdty udfmdc otct,b%

a ® b _{1
a ® b 2}
&
&
&
a ® b _n

a ® b 1 | b 2 | . . . | b n.

dsmdfs^ vjwtvekbf uhfvfnbrf G=( N , å , R , S). se xdty P-c otct,c lfdflt,s ufhrdtek itpqeldt,c^ vbdbqt,s c[dflfc[df nbgbc uhfvfnbrt,c^ hjvkt,bw afhsjl wyj,bkbf ajhvfkeh uhfvfnbrfsf stjhbfib lf itvjnfybkbf [jvcrbc vbth& uhfvfnbrfc tojlt,f vfh]dybd ohabdb^ se vbc .jdtk otcc fmdc cf[t
 A® XB fy A® X, cflfw A,BÎ N lf C Î å * ^& uhfvfnbrfc tojlt,f rjyntmcnbcfufy sfdbceafkb fy rjyntmcnbcflvb fhfvuh’yj,bfht se vbc .jdtk otcc fmdc cf[t% A® a , cflfw AÎ N , a Î ( N È å ) * . uhfvfnbrfc tojlt,f rjyntmcnpt lfvjrblt,ekb fy rjyntmcnbcflvb vuh’yj,bfht^ pju]th fhflfvjrkt,flb se vbc .jdtk otcc fmdc cf[t a ® b , cflfw | a | £ | b | .  

sdbstekb nbgbc uhfvfnbrf ufycfpqdhfdc ufhrdtekb rkfcbc tyt,c^ hjvtksfw ufhrdtekb sdbct,t,b uffxybfs& cfpjufljl itdybiyjs^ hjv rjyrhtnekb L tyf ufybcfpqdht,f wfkcf[fl hfbvt uhfvfnbrbs^ t& b& se L tyf ufybcfpqdht,f G uhfvfnbrbs tc bvfc fh ybiyfdc^ hjv fh fhct,j,c hfbvt G₁ uhfvfnbrf G uhfvfnbrbcfufy
ufyc[dfdt,ekb^ hjvtkbw bubdt L tyfc ufycfpqdhfdc& fy c[dfyfbhfl^ se L(G₁)= L(G₂), vbe[tlfdfl fvbcf se L tyf ufybcfpqdht,f hfbvt nbgbc uhfvfnbrbs^ xdty itudb’kbf dbkfgfhfrjs L tybc ufhrdtek sdbct,t,pt& lfdbo.js evfhnbdtcb uhfvfnbrt,bs- vfh]dybd ohabdb uhfvfnbrt,bs lf dfxdtyjs^ hjv vfs vbth ufycfpqdhekb tyt,b fhbfy htuekfhekb cbvhfdktt,b lf gbhbmbs yt,bcvbthb htuekfhekb cbvhfdkt ufybcfpqdht,f hfbvt vfh]dybd ohabdb uhfvfnbrbs&

2& { e} fhbc htuekfhekb cbvhfdkt å fkaf,tnib*

3& { a} fhbc htuekfhekb cbvhfdkt å fkaf,tnib^ cflfw aÎ å *

5. regularuli simravleebia, mxolod is simravleebi, romlebic miiRebian 1 - 4 wesebiT. regularuli simravleebi gamoisaxebian regularuli gamosaxulebebiT. regularuli gamosaxuleba å alfabetSi moicema Semdegi rekursiuli gansazRvrebebiT: 1. f aRniSnavs regularul simravles f . 2. e aRniSnavs regularul simravles {e}. 3. a aRniSnavs regularul simravles {a}, sadac a Î å . 4. Tu P da q regularuli gamosaxulebebia, romlebic aRniSnaven regularul simravleebs PP da Q Sesabamisad, maSin (p+q), (pq) da (p)* agreTve regularuli gamosaxulebebia, romlebic aRniSnaven regularul simravleebs R ∪Q, R Q da P* Sesabamisad. 5. regularuli gamosaxulebebia mxolod is gamosaxulebebi, romlebic miiRebian 1 – 4 wesebiT. regularul gamosaxulebaTaTvis a , b da g samarTliania Semdegi tolobebi, romelTa damtkiceba advilia:

a e= ea = a f * = e

arsebobs mWidro kavSiri ragularul simravleebsa da marjvnivwrfiv gramatikebs Soris. samarTliania debuleba, rom nebismieri P regularuli simravlisaTvis SeiZleba aigos Sesatyvisi marjvnivwrfivi gramatika G iseTi, rom L(G)=P da piriqiT, nebismieri G marjvnivwrfivi gramatikiT gansazRvruli ena L(G) aris regularuli simravle. Aam debulebis sruli damtkiceba ixileT [ ]-Si. Cven aq mxolod am debulebis pirvel nawils ganvixilavT, romelic xSirad gamoiyeneba praqtikaSi mocemuli P regularuli simravliT G marjvnivwrfivi gramatikis asagebad, romlisTvisac L(G)=P. ganvixiloT regularuli simravleebi: f , { e} da { a} aÎ å da avagoT maTTvis marjvnivwrfivi gramatikebi, romlebic am simravleebs gansazRvraven. 1.GganvixiloT marjvnivwrfivi gramatika = ( { S} , å , f , S ) cxadia L(G)=f . 2.GganvixiloT G=({S, å ,{S® e},S) . es gramatika marjvnivwrfivia da cxadia L(G)={e}. 3. ganvixiloT G=({S}, å ,{S® a},S). igulisxmeba aÎ å . cxadia L(G)={a} da G marjvnivwrfivi gramatikaa. P AA Q

axla vaCvenoT Tu L₁ da L₂ marjvnivwrfivi enebia, maSin:

1. L₁∪L₂; 2. L₁L₂; 3. L₁*

1. vTqvaT, LL₁ marjvnivwrfiv enas gansazRvravs. marjvnivwrfivi gramatika G1=(N₁, å , P₂,S₁) da L₂ marjvnivwrfiv enas gansazRvravs G2=(N₂, S , P₂,S₂)..avagoT axali marjvnivwrfivi gramatika G3=(N_1È N₂ ∪{S3}, P_1È P₂ {S₃ ® S₁ ç S2},S₃). vaCvenoT, rom L(G₃)=L(G₁) È L(G₂). Yyoveli S₃ Þ *W-saTvis gramatikaSi G₃ arsebobs gamoyvana S_1Þ *W G_1-Si da S_2Þ *W G₂ –Si e. i. WÎ L_1È L₂.. radganac S₃ Þ *W C₃ Si niSnavs S₃ Þ S₁ Þ *W an S₃ Þ S₂ Þ *W G3-Si.

2. vTqvaT G₃=(N₁ È N₂, å ,P₃,S1) marjvnivwrfivi gramatikaa, sadac P₃ gansazRvrulia Semdegnairad:

a). Tu A® xB ekuTvnis P₁-s, maSin igi ekuTvnis aseve P₃-s. b).Tu A ® X ekuTvnis P₁ –s, maSin A® xS₂ ekuTvnis P₃-s. c) yvela wesebi P₂ –dan ekuTvnis P₃-s.

cxadia, rom Tu S₁ Þ ⁺W G₁ –Si, maSin S₁ Þ ⁺WS₂ G₃ –Si. Tu S_2Þ ⁺V G₂-Si, maSin S_1Þ ⁺WV G₃-Si. Ee.i. L(G₁) L (G₂) Í L(G₃).

Aaxla vTqvaT S_1Þ ⁺W G₃-Si. radgan G₃-Si ara gvaqvs A® X wesi, amitom S₁ Þ ⁺xS₂ Þ ⁺xy=W, sadac xÎ L₁ da yÎ L₂. Aamgvarad, L(G₃) L(G₁)L(G₂) da sabolood L(G₃)=L(G₁)L(G₂). 3. vTqvaT G_a=(N₁ È S_{a, å} , P_a,S_a), sadac S_a ar ekuTvnis N₁-da P_a agebulia Semdegnairad:

Tu A ® xB ekuTvnis P₁-s, maSin igi ekuTvnis aseve P_a-s.

Tu A® x ekuTvnis P_1-s, maSin A® X S_a da A® X ekuTvnian P_a – s.

cxadia, S_aÞ ⁺x₁S_aÞ ⁺x₁x₂S_aÞ ⁺…Þ ⁺x₁x₂…x_nS_aÞ x₁x₂…x_n miiReba G_a-Si maSin da mxolod maSin, roca S_{1 Þ} ⁺x₁, S₁ Þ ⁺x₂,…, S_1Þ +x_n G₁-Si. Ees ki niSnavs, rom L(G_a)=(L(G₁))*.

sasruli avtomati warmoadgens regularuli simravlis warmodgenis erT-erT saSualebas. Mmisi saSualebiT Cven SegviZlia iolad warmovadginoT nebismieri regularuli simravle kompiuterze. sasruli avtomati Cven SegviZlia avagoT rogorc mowyobiloba, romelsac aqvs Sesasvleli firi da mmarTveli mowyobiloba sasruli mexsierebebiT. Ffirze modebulia Tavaki, romelsac SeuZlia waikiTxos firidan mocemul momentSi erTi ujredi da Tavaks SeuZlia gadaadgileba erTi ujredidan meoreze. Sesasvleli firi dayofilia ujredebad da TviTeul ujredSi SeiZleba iyos Cawerili alfabetis erTi romelime simbolo. simartivisaTvis Cven vigulisxmebT, rom Tavaks SeuZlia moZraoba firze marcxnidan marjvniv mimarTulebiT. Aaseve vigulissxmoT, rom firs aqvs usasrulo sigrZe, sadac sigrZis qveS igulisxmeba ujredebis raodenoba firze. MmmarTveli mowyobiloba Sedgeba mdgomareobaTa sasruli raodenobisagan. mdgomareobas Cven vuwodebT kvanZs da Cveni mowyobiloba mocemul momentSi SeiZleba imyofebodes erT romelime kvanZSi da am mowyobilobas SeuZlia gadaadgildes erTi kvanZidan meoreSi imisdamixedviT Tu ra simboloa modebuli Tavakze. Tavdapirvelad vigulisxmoT, rom mowyobiloba imyofeba raime kvanZSi da mas vuwodoT sawyisi kvanZi (mdgomareba). Aaseve mowyobilobaSi moniSnulia raime kvanZebis qvesimravle, romlebsac ewodeba saboloo mdgomareobebi. AaseT mowyobilobas ewodeba sasruli avtomati. ujredSi SeiZleba Cawerili iyos raime simbolo, winaaRmdeg SemTxvevaSi aseT ujreds ewodeba carieli ujredi. carieli ujredis SemTxvevaSi Cven vambobT, rom masSi Cawerilia carieli simbolo. simboloebis simravles, romlebic SeiZleba Segvxvdnen firis ujredebSi vuwodebT alfabets. carieli simbolo ar ekuTvnis alfabets.simboloebis sasrul mimdevrobas vuwodoT sityva. Cven vityviT, rom raime sityva modebulia sasrul avtomatze, Tu avtomati imyofeba sawyis mdgomareobaSi da Tavaki uTiTebs sityvis pirvel simbolos firze. sasruli avtomati grafikulad Cven SegviZlia warmovidginoT Semdegnairad: sasruli avtomatis mdgomareobebi aRvniSnoT wertilebiT, romlebic moniSnulia q_i,…,q_n niSnebiT. es niSnebi ar ekuTvnian alfabets. q_i mdgomareoba SevaerToT q_j mdgomareobasTan rkaliT, romelic moniSnulia raime a_k simboloTi a_k Î å (å aRniSnavs alfabets) da rkali mTavrdeba isriT, romelic mimarTulia q_i mdgomareobaSi, Tavaki uTiTebs a_k simbolos, maSin sasrul avtomats SeuZlia gadavides q_j mdgomareobaSi da Tavaki gadaadgildeba erTi ujrediT marjvniv. wyvils (q_j, W) vuwodoT sasruli avtomatis konfiguracia, sadac q_j mimdinare mdgomareobaa da W aris striqoni, romelic sasrul avtomats jer ar waukiTxavs firidan, e. i. Ffirze Cawerilia W=a_i1…a_ik striqoni da Tavaki uTiTebs a_i1 –s. vTqvaT q₁ sasruli avtomatis sawyisi mdgomareobaa, W₁=a₁…a_n firze Cawerili striqonia da sasruli avtomati sawyis mdgomareobaSi uTiTebs a₁ simbolos, maSin sawyisi konfiguracia iqneba (q₁,W₁). GganvixiloT konfiguraciaTa Semdegi mimdevroba (q₁,W₁), (q₂,W₂),…,(q_n,W_n),(q_n+1,e), sadac W_i=a_i…a_n (i=1,…,n). Tu q_n+1 saboloo mdgomareobaa, maSin Cven vityviT, rom sasruli avtomati uSvebs W₁ striqons. GganvixiloT damokidebuleba (q_i,W_i) ├ (q_i+1,W_i+1), sadac (I=1,2,…,n) da W_n+1=e. Canaweri (q_i,W_i) ├ (q_i+1,W_i+1) aRniSnavs sasruli avtomatis q_j mdgomareobidan q_i+1 mdgomareobaSi gadasvlas a_I simboloTi. Ees imas niSnavs, rom sasruli avtomatis diagramaze a_i kvanZi SeerTebulia q_i+1 kvanZTan rkaliT isriT q_i+1 –ken da es rkali moniSnulia a_i simboloTi. Canaweri (q₁,W₁)├*(q_n+1,e) aRniSnavs Semotanili damokidebulebis tranzitul-refleqsur Caketvas. GgaSlili saxiT igi ase Caiwereba (q₁,W₁) ├ (q₂,W₂) ├ … ├ (q_n,W_n) ├ (q_n+1,e). Tu q₁ sawyisi mdgomareobaa da q_n+1 saboloo mdgomareoba, maSin vityviT rom W₁=a₁…a_n striqons uSvebs mocemuli sasruli avtomati, an rac igivea W₁Î L(A), sadac A mocemuli avtomatia da L(A) aris am avtomatiT gansazRvruli ena. yvela aseTi W_1-ebi qmnian L(A) enas L(A)={W_1ç (q₁,W₁)├*(q_n+1,e) }. GganvixiloT magaliTi. vTqvaT mocemulia sasruli diagrama:

                                                                        diagrama 1

isriT miTiTebulia sawyisi mdgomareoba, xolo kvanZebi romlebic aRniSnulia OO wreebiT arian saboloo mdgomareobebi. maSasadame q₁ sawyisi mdgomareobaa, xolo q₆, q₇ da q₁₀ saboloo mdgomareobebi. Tu am diagramiT gansazRvrul avtomats aRvniSnavT A-Ti, maSin

L(A)-{saxli, saxlma, saxls, saxe, saxemⁿ, saxesⁿ, sari} aq n aris nebismieri naturaluri ricxvi. SevniSnoT, rom q₇ mdgomareobidan s da m simboloebiT avtomati isev q₇ mdgomareobaSi rCeba, xolo q₂ mdgomareobidan S simboloTi sasrul avtomats SeuZlia gadavides q₃ mdgomareobaSi an q₈ mdgomareobaSi. Aamitom es avtomati uSvebs saxem, saxemm da a. S… SemovitanoT ganmarteba: Tu sasrul avtomats raime mdgomareobidan erTi da igive simboloTi SeuZlia erTze met mdgomareobaSi gadasvla, maSin aseT sasrul avtomats ewodeba aradeterministuli, winaaRmdeg SemTxvevaSi deterministuli. diagramaze gamosuli sasruli avtomati aradeterministulia.

Aamis Semdeg SemovitanoT sasruli avtomatis mkacri ganmarteba. A = ( Q, å , d , q₀,F) aris aradeterministuli sasruli avtomati, sadac

Q aris mdgomareobaTa sasruli simravle,

q₀ – sawyisi mdgomareobaa da q_0Î Q ,

F – saboloo mdgomareobaTa simravlea da F Í Q,

aris Q X å dekartuli namravlis gadasaxva (Q) – Si e. i. simravleSi, romlis elementebia Q – s qvesimravleebi.

A=({q₁,q₂,q₃,q₄,q₅,q₆,q₇,q₈,q₉,q₁₀,q₁₁}, {s,a,r,x,i,m,l,e}, d ,q₁,{q₆,q₇,q₁₀}), sadac

d (q₁, s)={q₂}, d (q₂, a)={q₃,q₈},

d (q₃,x)={q₄}, d (q₄,l)={q₅}, d (q₅,i)={q₆}

d (q₅,m)={q₁₁}, d (q₁₁,a)={q₆}, d (q₄,e)={q₇)

d (q_7,m)={q₇}, d (q₇, s)={q₇}, d (q₈,r)={q₉} da

d (q₉,i)={q₁₀}.

A sasruli avtomatis araterministulobaze miuTiTebs is, rom d (q₂,a) simravle Seicavs or elements. Aaxla Cven SegviZlia A sasruli avtomatis konfiguracia ganvmartoT ase: (q,W)Î Q X å *, sawyisi konfiguracia iqneba (q₀,W) da damamTavrebeli konfiguracia iqneba (q,e), sadac qÎ F. binaluri damokidebuleba ├ ganisazRvreba ase: Tu d (q,a) simravle Seicavs q₁ –s, maSin (q,aW). Ees niSnavs imas, rom Tu A sasruli avtomti imyofeba q mdgomareobaSi da Tavaki miuTiTebs ujreds, romelSic Cawerilia a simbolo, maSin sasruli avtomati gadadis q₁ mdgomareobaSi da Tavaki gadaadgildeba erTi ujrediT marjvniv. Cven vityviT, rom A sasruli avtomati uSvebs W striqons, roca (q0,W)├*(qe) da qÎ F. aseT SemTxvevaSi WÎ L(A).

Ees aris A sasruli avtomatis cxriluri warmodgena. Ddiagrama 1 warmodgenili A saruli deterministuli avtomati gadavaqcioT sasrul deterministul avtomatad A₁ ise, rom L(A)=L(A₁). amisaTvis saWiroa, rom q₈ davamTxvioT q₃ – s da q_3- dan unda gamodiodes is rkalebi, romlebic gamodioda q₈-dan. Amis Semdeg q₈- saerTod amovardeba mdgomareobaTa simravlidan. AaseTnairad miRebuli axali sasruli avtomati A₁iqneba determinirebuli da L(A)=L(A₁).sazogadod, mtkicdeba Teorema, romelic ambobs, rom nebismieri araterminirebuli A sasruli avtomati SeiZleba gardaiqmnas axal determnirebul sasrul avtomatad ise, rom L(A)=L(A₁). Ddamtkiceba ixileT [1]-Si. radganac determinirebuli sasruli avtomatis SemTxvevaSi d (q,a) simravle, yoveli aÎ å da qÎ Q-sTvis, ar Seicavs erTze met elements, amitom nacvlad d (q,a)={p} SegviZlia SemoklebiT davweroT d (q,a)=P. da roca d (q,a)=f (carieli simravlea) maSin vityviT, rom d (q,a) ganusazRvrelia.

SeiZleba martivad damtkicdes Semdegi Teorema: Tu raime determinirebuli sasruli avtomati M uSvebs L(M) enas, maSin arsebobs iseTi marjvnivwrfivi gramatika G, rom L(G)=L(M).

vTqvaT M=(Q,å ,d ,q₀,F) da G=(Q,å ,P,q₀) sadac P ganisazRvreba Semdegnairad:

Tu d (q,a)=r, maSin P Seicavs wess q® ar da Tu q_1Î F, maSin q® e ekuTvnis P-s. aseTnairad agebuli G gramatika uSvebs igive enas, rasac M deterministuli sasruli avtomati, ris damtkicebac advilia. PpiriqiT zemoT moyvanili wesebis SebrunebiT gamoyenebiT marjvnivwrfivi gramatikisaTvis SeiZleba aigos determinirebuli sasruli avtomati, romelic gansazRvravs igive enas rasac mocemuli marjvnivwrfivi gramatika. Aaseve SeiZleba nebismieri regularuli simravlisaTvis aigos iseTi deterministuli sasruli avtomati, romelic uSvebs mocemul regularul simravles. Aaqedan gamomdinareobs, rom sasruli avtomatebiTa da marjvnivwrfivi gramatikebiT gansazRvruli enebi arian regularuli simravleebi. visac ainteresebs sasruli avtomatebis minimizaciis sakiTxi (garkveuli azriT) da regularul simravleebTan dakavSirebuli gadawyvetadi problemebi vurCevT [1]-s.

regularuli gamosaxulebebi farTod gamoiyenebian Perl enaze daweril programebSi. Aam TavSi Cven aRvwerT regularul gamosaxulebebs PPerl –is mixedviT. regularuli gamosaxulebebis Semotanis wyalobiT Perl aris bunebrivi teqstebis damuSavebis mZlavri saSualeba. aqamde aRwerili regularuli gamosaxulebebi mniSvnelovnad aris gafarToebuli Perl-Si. Perl-is regularuli gamosaxuleba aris raime striqoni, romelic aRwers raime nimuSs. NnimuSebi gamoiyenebian teqstSi konkretuli striqonis mosaZebnad, mis Sesacvlelad sxva striqoniT, teqstidan misi amosagdebisaTvis, an teqstis ufro rTuli gardaqmnisaTvis.

Cven daviwyebT umartivesi regularuli gamosaxulebis gansazRvriT, vaCvenebT mis gamoyenebas da SemdegSi TandaTanobiT gavafarToebT am cnebas. Uumartivesi regularuli gamosaxulebaa niSnebis raime mimdevroba raime winaswar mocemul alfabetSi. regularuli gamosaxuleba SemosazRvruli daxrili xazebiT (/). magaliTad, /ab1/ aris nimuSi, romelic Seicavs ab1 regularul gamosaxulebas ASCI I standartiT gansazRvrul alfabetSi. imisaTvis, rom ganvsazRvroT raime nimuSi eTanadeba Tu ara mocemul teqsts, amisaTvis gamoiyeneba operatori = ~ , romlis marjvena mxareSi iwereba nimuSi, xolo marcxena mxareSi iwereba teqsti brWyalebSi an cvladi, romelic Seicavs teqsts. = ~ operatori warmatebiT sruldeba an rac igivea eTanadeba Sablons Tu SabloniT gansazRvruli regularuli gamosaxuleba gvxvdeba am operatoris marcxena mxariT gansazRvrul teqstSi, winaaRmdeg SemTxvevaSi operatori ganicdis marcxs (Sabloni ar eTanadeba teqsts). MmagaliTad, instruqcia

² this is a text ² = ~ /is/;

warmatebiT sruldeba, radganac is regularuli gamosaxuleba pirvelad gvxvdeba this sityvaSi. Ooperatori ! ~ warmatebiT sruldeba Tu mis marjvena mxareSi moTavsebuli gamosaxuleba ar gvxvdeba marcxena mxareSi. M

magaliTad, ² this is a text ² = ~ /at / ar eTanadeba;

² this is atext ² = ~ /at / eTanadeba.

Aalfabetis niSnebi regularul gamosaxulebaSi iwereba ise, rogorc isini gvxvdeba alfabetSi, gamonakliss warmoadgenen zogierTi niSnebi, romlebic gamoiyenebian regularul gamosaxulebaSi specialuri daniSnulebiT. AaseT niSnebs ewodebaT metaniSnebi. MmetaniSnebia: [ ] ( ) { } Ù + * ?. imisaTvis rom raime metaniSani gagebuli iyos rogorc Cveulebrivi niSani, mas win unda davuweroT \ (Sebrunebuli daxrili xazi). MmagaliTad \[ gaigeba rogorc gaxsnili kvadratuli frCxili an \+ gaigeba rogorc + niSani da a. S.

² a . b * c ² = ~ / a . b * c / ar eTanadeba.

² a . b * c ² = ~ / a \ . b \ * c / eTanadeba.

\\ regularul gamosaxulebaSi aRniSnavs \ (Sebrunebul daxril xazs). ASCI I niSanTa simravlis niSnebi, romelTa kodebia 0¸ 31, aqvT specialuri aRniSvnebi. magaliTad, \n aRniSnavs axal striqonze gadasvlas, \t aRniSnavs tabulacias da sxva. Ees aRniSvnebi SeiZleba gamoyenebul iqnes aseve regularul gamosaxulebebSic. NniSnis nacvlad SesaZlebelia gamoyenebul iqnes misi kodi TeqvsmetobiT an rvaobiT sistemaSi. TeqvsmetobiTi kodi warmoidgineba \ox n₁n_2, sadac n₁ da n₂ TeqvsmetobiTi cifrebia, an \o n₁ n₂ n₃ rogorc rvaobiTi kodi, sadac \ n₁ n₂ da n₃ rvaobiTi cifrebia, sadac o aris o aso da ara nuli. MmagaliTad \ ox f 5 an \ o 125. TviT \ (Sebrunebuli daxrili xazi) aris metaniSani da mis warmosadgenad, rogorc Cveulebrivi niSani saWiroebs niSans-\. Aase, rom \\ aris daxrili xazis Cveulebriv niSnad warmodgena. magaliTad, ‘a \ b’ = ~ / a \\ b / eTanadeba, e.i. warmatebiT Sesruldeba. MmagaliTad, miviRoT, rom TariRs warmovadgenT teqstSi, rogorc Tve: ricxvi: weli, sadac TvisTvis da ricxvisTvis gamoyofilia ori aTobiTi cifri, xolo wlisaTvis oTxi aTobiTi ricxvi: magaliTad, 09: 28: 1973 niSnavs 28 seqtemberi 1973 weli. AaseT SemTxvevaSi teqstSi rom vipovoT raime TariRi saWiroa misTvis SevadginoT Semdegi nimuSi: / dd: dd: dddd / sadac d niSnavs nebismier aTobiT cifrs. igulisxmeba, rom Tve moTavsebulia diapazonSi 01-12 da Tve-01: 31. es, rom gaviTvaliswinoT, maSin dagvWirdeba ufro rTuli nimuSis Sedgena.

regularul gamosaxulebaSi SeiZleba gvqondes cvladebic. Parl-Si skalaruli cvladis saxeli iwyeba $ niSniT. MagaliTad, $ name da $ day. Arian cvladis saxelebi. cvladisTvis mniSvnelobis miniWeba xdeba = operatoriT. MmagaliTad, $ day=¢ 15`; teqsturi konstantebis warmosadgenad gvaqvs ori saSualeba: teqstis moTavseba erTmag brWyalebSi an ormag brWyalebSi. Tu teqsti moTavsebulia erTmag brWyalebSi, maSin igi gaigeba, rogorc warmodgenili niSnebis ubralo mimdevroba. magaliTad, ‘ a \ . + 5`, xolo Tu igi moTavsebulia ormag brWyalebSi, maSin mxedvelobaSi miiReba metasimboloebis mniSvnelobebi da cvladebis mnivnelobebi. aseT SemTxvevaSi amboben, rom xdeba teqstis interpolireba. MmagaliTad aviRoT " a \ n b $day ² . Mmisi interpolirebis Sedegad miiReba " a \ n 5 ² Tu $ day=’ 15 `; da \ n gaigeba rogorc erTi niSani, romelic niSnavs axal striqonze gadasvlas, xolo ‘ a \ n b $day` niSnavs im niSnebis mimdevrobas, romelic mocemulia brWyalebSi. Tu Cven gvinda rom ormag brWyalebSi mocemuli igive iyos rac erTmag brWyalebSi mocemuli teqsti, maSin unda CavweroT ase: ‘’a \\ n b \ $day’’. vTqvaT, $ day = ‘ Sunday ` ; maSin

‘today is Sunday ` = ~ / $day / eTanadeba.

‘today is Sunday ` = ~ / is Sunday / eTanadeba.

‘today is Sunday ` = ~ / ${ day } eTanadeba.

Mmesame SemTxveva aris Perl –is xeSmasivis elementis saxiT warmodgena- $ { day }-is mniSvnelobaa ` Sunday ‘.Tu Cven gvinda, rom regularuli gamosaxuleba emTxveodes mocemuli teqstis nawils dasawyisidanve maSin regularuli gamosaxuleba unda daviwyoT niSniT Ù , xolo Tu gvinda, rom mocemuli regularuli gamosaxulebiT damTavrdes teqsti , maSin regularul gamosaxulebas boloSi unda davuweroT $ niSani. magaliTad,

‘ regular day ` = ~ / Ù regular / EeTanadeba

‘ regular day ` = ~ / Ù day / ar eTanadeba

‘ regular day ` = ~ / day $ / eTanadeba

‘ regular day ` = ~ / Ù day / ar eTanadeba

regularul gamosaxulebaSi SeiZleba niSanTa klasebis gamoyeneba, rac mTel rig SemTxvevebSi saSualebas gvaZlevs ufro mokled daiweros regularuli gamosaxuleba. Kkvadratul frCxilebSi moTavsebuli niSnebis simravles ewodeba niSanTa klasi. MmagaliTad, [a b c ] da igi niSnavs am simravlidan aRebul nebismier niSnis Sexvedras teqstis mimdinare poziciaSi. magaliTad, / r [ a b c ] d / eTanadeba rad-s, r b d an r c d. Tu Cven aviRebT / r [ c b a ] d / -s maSin igi eTanadeba r c d-s, r b d an rad. e.Ei. igives, magram gansxvavdeba Sedarebis rigiT. Aaseve,

/ [ D d A a Y y ] / eTanadeba day –s registris miuxedavad: Day, dAy, DAY da a.S.., e. i. maT nebismier kombinacias. [\$ a] klasi Sedgeba ori niSnisagan $ a. [a b c d e] klasi SegviZlia CavweroT SemoklebiT [a-e]. es im SemTxvevaSi Tu gvaqvs mimdevrobiT yvela niSnebi klasSi. MmagaliTad, [ a-e g u-x] warmoadgens klass [ a b c d e g u v x]. Tu klasis elementia ‘ – ‘ niSani, maSin igi unda Caiweros bolo niSnad. MmagaliTad, [ a – c ] niSnavs [a b c ] klass. klasi laTinuri alfabetisaTvis Caiwereba ase: [ a – z a – z ]. niSanTa zogierTi klasebisaTvis gamoiyeneba Semoklebebi: \ d aRniSnavs nebismier cifrs da warmoadgens [ 0 – 9 ] klass.

\ S aris xarvezis niSanTa klasi da warmoadgens [ \ \ t \ r \ f ]

\ w aris alfacifrul niSanTa klasi da warmoidgineba [ 0-9a-zA-

z _-]

\ D aris ara \d. e. i. nebismieri niSani garda cifrisa, rac niSnavs \d \ namravlis damatebas universalur simravlemde.

\ S aris ara \s.

\ W aris ara \w.

. (wertili) niSnavs nebismier niSans garda \ n. es Semoklebebi SeiZleba gamoviyenoT rogorc klasis SigniT aseve mis gareT regularul gamosaxulebaSi. MagaliTad [ \ s \d ] niSnavs xarvezis niSanTa klass an cifrs.

‘ Ù ‘ niSani klasis SigniT dasawyisSi niSnavs am klasiT warmodgenili niSnebis damatebas universalur simravlemde. Ee. i. nebismier niSans, romelic gansxvavdeba klasSi warmodgenili niSnebisagan. MmagaliTad, [ Ù a b c ] aris nebismieri niSani, garda ¢ a¢ ,¢ b ¢ . Aan ¢ c ¢ - i. [ a b c Ù ] aris ¢ a ¢ , ¢ b ¢ , ¢ c ¢ an ¢ Ù ¢ ^{. e. i.} ¢ Ù ¢ klasSi dasawyisis garda nebismier adgilas niSnavs TavisTavs. MmagaliTebi:

/ \ w \ w \ w / -eTanadeba sam asocifrul niSans.

/ . . / - eTanadeba or nebismier niSans.

/ \ . / - eTanadeba wertils ¢ . ¢ .

/ [ Ù a b ] / - eTanadeba nebismier niSans garda ¢ a¢ da ¢ b¢ -si.

zogierTi niSnebi aRniSnaven teqstSi garkveul adgils da ar moiTxoven raime niSanTan damTxvevas. AaseTebs Cven ukve gavecaniT rogoricaa ¢ Ù ¢ da ¢ $ ¢ , romlebic miuTiTeben striqonis dasawyiss da damTavrebas Sesabamisad.Kkidev aris \ b ¢ niSani, romelic miuTiTebs asocifruli sityvis sazRvars (dawyebas an damTavrebas ) , e.i. W klasis dawyebas an damTavrebas. magaliTad, / \ b \ w / miuTiTebs teqstSi adgils, romlis Semdeg gvaqvs asocifruli niSani, romlis uSualod win araa asocifruli niSani. magaliTebi:

¢ : - a b ¢ = ~ / \ d \w / eTanadeba ¢ a ¢ - s.

¢ ¢ ¢ ¢ = ~ / Ù $ / eTanadeba.

¢ ¢ ¢ ¢ = ~ / . / ar eTanadeba.

¢ ¢ \ n ¢ ¢ = ~ / Ù . $ / ar eTanadeba.

¢ ¢ a ¢ ¢ = ~ / Ù . $ / eTanadeba.

¢ ¢ a \ n ¢ ¢ = ~ / Ù . $ / eTanadeba.

Mmodifikatorebi . roca regularuli gamosaxuleba moTavsebulia daxril xazebs Soris ( / / ) da bolo daxril xazs ar mosdevs raime niSani Cven vambobT, rom es aris standartuli nimuSi da mas ar gaaCnia raime modifikatori. Tu // xazebs mosdevs specialuri niSnebi, romlebsac Cven qvemoT CamovTvliT, maSin vambobT, rom regularuli gamosaxuleba modificirebulia e. i. igi iqceva SeTanxmebisas sxvanairad imisdamixedviT Tu ra niSnebi mosdevs.

// S niSnavs, rom SesaTanadebeli striqoni ganixileba, rogorc erTi grZeli striqoni da ¢ . ¢ eTanadeba nebismier niSans garda ¢ \ n ¢ - is win.

// m niSnavs, rom gvaqvs ramodenime grZeli striqoni, romelic Seicavs mraval striqons. AaseT SemTxvevaSi ¢ . ¢ eTanadeba nebismier niSans garda ¢ \ n ¢ -sa. ¢ Ù ¢ da ¢ $ ¢ niSnebs SeuZliaT SeuTanaddnen nebismieri striqonis dasawyissa da daboloebas Sesabamisad mTlian grZel striqonSi.

\\ sm niSnavs rom amuSavebs erT grZel striqons, magram mis SigniT aRmoaCens mraval striqons. ¢ . ¢ eTanadeba nebismier niSans ¢ \ n ¢ - sac. ¢ Ù ¢ da $¢ SeuZliaT SeeTanadon nebismieri striqonis dasawyissa da daboloebas striqonis SigniT. magaliTebi:

MmagaliTad, / [ d e f ] / igivea rac / d ½ e ½ f /.

¢ skami ¢ = ~ / skami½ s½ ¢ sk / eTanadeba ¢ skami ¢

¢ skami ¢ = ~ / s½ sk ½ skami ½ eTanadeba ¢ s¢ -s:

/ ( a½ ga ½ Ca ) ( mo \) / # eTanadeba amo, a, gamo, ga, Camo, Ca an ara aqvs zmniswini.

/ aca ½ ac½ ca½ c½ Ra½ ave½ ve \ / # eTanadeba romelime nawilaks an ara aqvs nawilaki.

Perl- Si TviTeul mrgval frCxilebSi moTavsebul gamosaxulebas Seesabameba $ n cvladi, sadac n naturaluri ricxvia. $ n –Si inaxeba me – n –e mrgval frCxilebSi moTavsebuli gamosaxulebis Sesatyvisi teqsti. MmagaliTad, $1 iqneba pirvel mrgval frCxilebSi moTavsebul regularul gamosaxulebasTan SeTanadebuli numeracia. iwyeba erTidan da gadainomreba marcxnidan marjvniv gaxsnili frCxilebi. MmagaliTad, SeTanadebis instruqciaSi

¢ ¢ saxlisaTvis¢ ¢ = ~ m / Ù (( ^. W +) (is) (Tvis \) (ac\)) $ /

frCxilebi gadainomreba ase: / Ù (₁(₂ W+)₂ (₃ is )₃ (₄ Tvis)₄ (₅ ac ½ )₅)₁ $ /

M = ( Q, å , D , d , q_0, F ), sadac

Q – aris mdgomareobaTa simravle,

q₀ - sawyisi mdgomareobaa,

d - aris Q X ( å È { e } simravlis gadasaxva Q X D * simravlis qvesimravleTa simravleSi.

A sasruli avtomatis analogiurad ganimarteba sasruli gardamqmnelis konfiguracia. Mmxolod aq konfiguracias daemateba axali elementi – gamosasvleli striqoni. Aamgvarad, sasruli gardamqmnelis konfiguraciaa sameuli (q, x, y ), sadac q aRniSnavs gardamqmnelis mdgomareobas, x – aris Tavdapirveli Sesasvleli striqonis darCenili nawili mocemuli momentisaTvis, e. i. misi sufiqsi, xolo y aris mocemuli momentisaTvis gamotanili striqoni anu Tavdapirveli striqonis prefiqsi.

sasruli gardamqmneli yoveli taqtis Sesrulebisas gadadis erTi konfiguraciidan meoreSi. Ddamokidebuleba, romelic gansazRvravs sasruli gardamqmnelis gadasvlas erTi konfiguraciidan meoreSi aRvniSnoT ├ -iT. Aanalogiurad, sasruli avtomatisa, aq Cven SemovitanoT am damokidebulebisaTvis ├ ⁱ , ├ ⁺ da ├ * operatorebi. ├ damokidebuleba ganisazRvreba ase: ( q, a x, y )├ ( r, x yz ) sadac

q Î Q da r Î Q, a Î ( å È { e }, x Î å * da y Î Ñ *, xolo d ( q, a ) simravle unda Seicavdes ( r, z ) elements. Aamis Semdeg Cven SegviZlia ganvsazRvroT M sasruli gardamqmneliT mocemuli t (M) Targmani:

( x, y ) wyvilSi igulisxmeba, rom y aris x - is Targmani. miaqcieT yuradReba, rom sasruli gardamqmneli amTavrebs warmatebiT muSaobas, roca Sesasvleli striqoni dacarieldeba. magaliTi. S® a + Sï a - Sï + Sï -ï a

Q = { q₀,q₁,q₂,q₃,q₄ } FF

å = { a , + , - }

uhfvfnbrfib itb'kt,f b.jc hfvjltybvt ufvj.dfyf tmdbdfktynehb bv ufut,bs hjv .jdtk vfsufyib thsb lf bubdt ufvj.dfybc otct,b ufvjb.tyt,f thsb lf bubdt flubkt,ib^vfuhfv ufyc[dfdt,ekb hbubs& tmdbdfktynj,bc wyt,bc ufyvfhnt,f jhb ufvj.dfybcfsdbc yt,bcvbthb cf[bc uhfvfnbrbcfsdbc hsekbf^ vfuhfv CF uhfvfnbrbcfsdbc itb'kt,f itvjdbnfyjs tmdbdfktyneh ufvj.dfyfsf rkfcbc vj[th[t,ekb uhfabrekb ofhvjlutyf^ hjvtkcfw tojlt,f ufvj.dfybc [t& ufvj.dfybc [t CF uhfvfnbrfib tc fhbc lfkfut,ekb [t^ hjvkbc .jdtkb odthj vjybiyekbf hfbvt cbv,jkjsb cbvhfdkblfy& se ibuf odthj vjybiyekbf A cbv,jkjsb^ [jkj vbcb gbhlfgbhb isfvjvfdkt,b- cbv,jkjt,bs^vfiby fhbc fv uhfvfnbrbc otcb&

ufyvfhnt,f& vjybiyek lfkfut,ek D [tc tojlt,f ufvj.dfybc [t ~fy ufhxtdbc [t` CF uhfvfnbrfib se itchekt,ekbf itvltub gbhj,t,b% 1&D [bc 'bhb vjybiyekbf A cbv,jkjsb& 2& se D₁,D₂,...,D_k mdt[tt,bf lf D_i [bcf vjybiyekbf -sb^ vfiby otcbf fqt,ekb P cbvhfdkblfy& eylf b.jc ufvj.dfybc [t CF uhfvfnbrfib se fhfnthvbyfkbf lf itlut,f thsflthsb odthjcfufy^ hjvtkbw vjybiyekbf -sb^se nthvbyfkbf& 3&se [bc 'bhc uffxybf thsflthsb isfvjvfdfkb vjybiyekb e-sb^ vfiby tc isfvjvfdfkb mvybc [tc^hjvtkbw itlut,f thsflthsb odthjcfufy lf otcbf fqt,ekb P cbvhfdkblfy&

vfufkbsb 2& 19& 2&8 yf[fppt ufvjcf[ekbf ufvj.dfybc [tt,b G=G(S) uhfvfnbrfib otct,bs

SaSbS/bSaS/e.

s s s s

e a s b s a s b s

b s a s e a s b s

e e e e

itdybiyjs^hjv fhct,j,c lfkfut,ekb [bc odthjt,bc thlflthsb lfkfut,f^hjvtkibw odthjt,bc gbhlfgbhb isfvjvfdkt,b kfult,bfy vfhw[yblfy vfh]dybd^ufydvfhnjs tc lfkfut,f itvltuyfbhfl&lfdeidfs^hjv n fhbc odthj lf n₁,n2,...,nk vbcb gbhlfgbhb isfvjvfdkt,bf^vfiby se i<j odthj lf .dtkf vbcb isfvjvfdkt,b bsdkt,f ufykfut,ekfl

(a) S, (b) e, (c) abab, (d) abab. f[kf dfxdtyjs^ hjv ufvj.dfybc [tt,b fltmdfnehfl ofhvjflutyty ufvj.dfyt,c bv fphbs^hjv CF uhfvfnbrfib G a ufvj.dfybkb ]fzdbc .jdtkb ufvj.dfybcfsdbc itb'kt,f fbujc ufvj.dfybc [t G-ib a rhjybs lf gbhbmbs&fvbcfsdbc^ itvjdbnfyjs hfvjltybvt f[fkb wyt,f& dsmdfs^ D fhbc ufvj.dfybc [t CF uhfvfnbrfib G=(N,å ,P,S).

ufyvfhnt,f: D [bc rdtsf deojljs D [bc bcts C cbvhfdktc^ hjv

1& fhwthsb jhb odthj C -lfy fh 'tdc thscf lf bvfdt upfpt D-ib_&.

2. D [bc fhwthsb odthjc lfvfnt,f fh itb'kt,f C cbvhfdkbcfsdbc^ hjv fh lfbhqdtc (1) sdbct,f&

ufyvfhnt,f& ufydvfhnjs D [bc rdtsbc rhjyb hjujhw ]fzdb^hjvtkbw vbbqt,f vfhw[yblfy vfh]dybd bv odthjt,bc vjybidyt,bs rjyrfntyfwbbs^hjvkt,bw mvybfy hjvtkbvt rdtsfc& vfufkbsfl^ aba SbS bv rdtsbc ufvj.dfybc [bc rhjybf^hjvtkbw yfxdtyt,bf 2&9 yf[-pt&

2&12& ktvf& lfdeidfs S=a ₀,a ₁,...,a _n fhbc a _n ]fzdbc CF uhfvfnbrfib G=(N,å ,P,S). vfiby G-ib itb'kt,f fbujc ufvj.dfybc [t D, hjvkbcsdbcfw a _n-rhjybf^[jkj a ₀,a ₁,...,a _n-1 hjvtkbvt rdtst,bc

rhjyt,bf&lfvnrbwt,f&fdfujs D_i(o£ i£ n) ufvj.dfybc [tt,bc bctsb vbvltdhj,f^hjv a _i b.jc rhjyb D_i [bcf&dsmdfs D₀ fhbc [t^hjvtkbw itlut,f thsflthsb odthjcfufy^ hjvtkbw vjybiyekbf S-bs&

lfdeidfs hjv a _i=b _iAg _i lf A® X₁X₂...X_k otcbc ufvj.tyt,bc itvltu ufvj.jabk A yfobkpt vbbqt,f a _{i+1=b i}X₁X₂...X_{kg i} vfiby D_i+1 [t vbbqt,f D_i-cfufy se A-sb vjybiyek ajsjkpt (bub fhbc (| b _i| +1) cbv,jkj D_i [bc rhjybcf) lfevfnt,s K gbhlfgbh isfvjvfdkt,c lf vfs vjdybiyfds X₁,X₂,...,X_k-sb itcf,fvbcfl& w[flbf hjv D_i+1 [bc rhjyb bmyt,f a _i+1& D_n [t bmyt,f cf'bt,tkb ufvj.dfybc [t& lfdfvnrbwjs itchekt,ekb ktvf 2&12^t&b& dfxdtyjs^ hjv.jdtkb ufvj.dfybc [bcfsdbc G-ib fhct,j,c thsb vfbyw itcf,fvbcb ufvj.dfyf&

2&13&ktvf& dsmdfs D - ufvj.dfybc [tf CF uhfvfnbrfib G=(N,å ,P,S) rhjybs a &vfiby S Þ ^*a .

lfvnrbwt,f&dsmdfs C₀,C₁,...C_n D [bc bctsb rdtst,bf^hjv

1& C₀ itbwfdc v[jkjl D [bc 'bhc&

2& C_i+1 (O£ i< < n) vbbqt,f C_i_lfy vfcib thsthsb fhfnthvbyfkehb odthjc itwdkbs vbcb gbhlfgbhb isfvjvfdkt,bs&

3& C_n _ fhbc D [bc rhjyb&

w[flbf^ hjv thsb vfbyw fctsb vbvltdhj,f fhct,j,c& se a _i fhbc C_i_cb^ vfiby a ₀^a ₁^&&&^a _n fhbc a _n ]fzdbc ufvj.dfyf a ₀-lfy G-ib&

ufyvfhnt,f& se 2&13 ktvbc lfvnrbwt,fib C_i+1 vbbqt,f C_i_cfufy vbcb .dtkfpt vfhw[tyf fhfnthvbyfkehb odthjc itwdkbs vbcb gbhlfgbhb isfvjvfdkt,bs^vfiby cfsfyflj ufvj.dfyfc a ₀^a ₁^&&&^a _n tojlt,f G uhfvfnbrfib a ₀-cfufy a ₀-cfufy a _n ]fzdbc vfhw[tyf ufvj.dfyf& vfh]dtyf ufvj.dfyf ufybvfhnt,f fyfkjubehfl^ cfzbhjf v[jkjlobyf obyflflt,fib .dtkfpt vfhw[tyf odthjc yfwdkfl ufydb[bkjs .dtkfpt vfh]dtyf odthj& itdybiyjs hjv vfhw[tyf (fy vfh]dtyf) ufvj.dfyf ufybcfpqdht,f wfkcf[fl ufvj.dfybc [bs&

se S=a ₀,a ₁,...,a _n=W fhbc W ]fzdbc vfhw[tyf ufvj.dfyf^ vfiby a _i-c(o£ i< n). fmdc cf[t X_iA_iB_i cflfw X_{iÎ å} ^A_iÎ N lf b _iÎ (NÈ å )^.

.jdtkb itvlujvb vfhw[tyf ufvj.dfybc a _i+1 ]fzdb vbbqt,f a _i-cfufy vbcb vfhw[tyf fhfnthvbyfkehb A_i cbv,jkjc itwdkbs hjvtkbvt otcbc vfh]dtyf v[fhbs& vfh]dtyf ufvj.dfyfib bwdkt,f vfh]dtyf fhfnthvbyfkb&

2&21& vfufkbsb& ufydb[bkjs CF G₀ uhfvfnbrf otct,bs

E® E+T| T

T® T*F| F

F® (E)| a

ufvj.dfybc [t^ hjvtkbw yfxdtyt,bf 2&11 yf[-pt^ a+a ]fzdbc 10 tmdbdfktynehb ufvj.dfyt,bc ofhvjlutyff&

E® E+T® T+T® F+T® a+T® a+F® a+a

E® E+T® E+F® E+a® T+a® F+a® a+a.

ufyvfhnt,f& a ]fzdc deojlt,s vfhw[ybd ufvj.dfyflc (G uhfvfnbrfib)^ se fhct,j,c S=a ₀,a ₁,...,a _n=a vfhw[tyf ufvj.dfyf lf lfdothjs SÞ ^*_GLa ( fy SÞ ^*_La , hjwf w[flbf se hjvtkbvt G uhfvfnbrf buekbc[vt,f). fyfkjubehfl a -cdeojlt,s vfh]dybd ufvj.dfyflc^ se fhct,j,c vfh]dtyf ufvj.dfyf S=a ₀,a ₁,...,a _n=a lf doths SÞ _Gr^*a (fy SÞ _r^*a ). vfhw[tyf ufvj.dfybc ths yf,b]c fqdybiyfds Þ _L, [jkj vfh]dtyf ufvj.dfybcfc Þ _r-bs&

2&11 stjhtvf& dsmdfs G=(N,å ,P,S) CF uhfvfnbrff& SÞ ^*a vfiby lf v[jkjl vfiby^ hjwf G-ib fhct,j,c ufvj.dfybc [t rhjybs a &

itdybiyjs^ hjv xdty sfdb fdfhblts bvbc smvfc^hjv se vjwtvekbf ufvj.dfyf SÞ ^*a CF uhfvfnbrfib^ vfiby itb'kt,f dbgjdjs G-ib thsflthsb ufvj.dfybc [t rhjybs a & fvbc vbptpb vlujvfhtj,c bvfib^ hjv fhct,j,ty CF uhfvfnbrt,b^ hjvtksfw itb'kt,f /mjylts hfvltybvt ufyc[dfdt,ekb ufvj.dfybc [tt,b thsb lf bvfdt rhjybs& fctsbf uhfvfnbrf 2&19 vfufkbsblfy& yf[&2&8-pt yfxdtyt,bf c[dflfc[df ufvj.dfybc [tt,b (d) lf (u) thsblfbubdt rhjybs&

ufyvfhnt,f& CF uhfvfnbrfc G tojlt,f fhfwfkcf[f se fhct,j,c thsb vfbyw WÎ L(G) ]fzdb^ hjvtkbw fhbc jhb fy vtnb ufyc[dfdt,ekb ufvj.dfybc [bc rhjyb G-ib& tc bubdtf^hjv hjvtkbvt WGL(G) ]fzdc fmdc jhb fy vtnb vfhw[tyf (vfh]dtyf) ufvj.dfyf^obyffqvltu itvs[dtdfib CF uhfvfnbrfc G-c wfkcf[f uhfvfnbrf tojlt,f&

2&4&2& CF uhfvfnbrfsf ufhlfmvyt,b&

[ibhfl cfzbhjf vjwtvekb uhfvfnbrbc bctsb vjlbabwbht,f^hjv vbc vbth ofhvjmvybkvf tyfv vbbqjc cfzbhj cnhemnehf&ufydb[bkjs vfufkbsfl^ L(G₀) tyf& bub itb'kt,f vbdbqjs G uhfvfnbrbc otct,bs

E® E+T| E*T| T

T® (E)| a

G uhfvfnbrbc vtjht yfrkb^hjvtkbw uffxybf fuhtsdt G₁ uhfvfnbrfc^bvfib vlujvfhtj,c^hjv + lf * jgthfwbt,c fmds thsb lf bubdt ghbjhbntnb&c[dfyfbhfl hjv dsmdfs^ a+a*a lf

a*a+a ufvjcf[ekt,t,bc cnhemnehf^hjvtkcfw fybzt,c vfs G₁ uhfvfnbrf^ uekbc[vj,c jgthfwbt,bc itchekt,bc bubdt hbuc^ hfcfw ufvjcf[ekt,t,ib (a+a)*a l f (a*a)+a itcf,fvbcfl&

hjv vbdbqjs + lf * jgthfwbt,bc xdtekt,hbdb ghbjhbntnb^ hjvkbc lhjcfw * oby ecoht,c + jgthfwbfc lf ufvjcf[ekt,f a+a*a ufbut,f hjujhw a+(a*a)-pt cfzbhjf uflfdblts G₀ uhfvfnbrfpt&

lfdbo.js .dtkfpt w[flbs^vfuhfv vybidytkjdfyb ufhlfmvyt,bs& pjubths itvs[dtdt,ib CF uhfvfnbrf itb'kt,f itbwfdltc ecfhut,kj cbv,jkjt,c otct,c& vfufkbsfl^G=({S,A},{a,b},P,S) uhfvfnbrfib^cflfw P={S® a,A® b}, fhfnthvbyfkb A lf b fh itb'kt,f itud[dltc fhwths ufvj.dfyfl ]fzdib& fvudfhfl^ fv cbv,jkjt,c fhf fmds fhfdbsfhb lfvjrblt,ekt,f L(G) tyfcsfy lf bcbyb itb'kt,f fvjdfuljs G uhfvfnbrbc ufycfpqdhblfy bct^ hjv fh itdt[js L(G) tyfc&

ufyvfhnt,f& XÎ NÈ å cbv,jkjc deojljs ecfhut,kj CF uhfvfnbrfib G=(N,å ,P,S) se vfcib fh fhct,j,c SÞ ^*WXg cf[bc ufvj.dfyf^cflfw W,X,g tresdybfy å ^*-c&

bvbcfsdbc^hjv lfdflubyjs A fhfnthvbyfkb ecfhut,kjf se fhf sfdlfgbhdtkfl fdfujs fkujhbsvb^hjvtkbw uffhrdtdc itb'kt,f se fhf fhfnthvbyfkb /mjyltc hjvtkbvt nthvbyfkeh ]fzdc^t&b& hjvtkbw [cybc { W| A® ^*W,WÎ å ^*} cbvhfdkbc cbwfhbtkbc ghj,ktvfc&fctsb fkujhbsvbc fhct,j,blfy ufvjvlbyfhtj,c CF uhfvfnbrbcfsdbc cbwfhbtkbc gh,ktvbc uflfo.dtnbkt,f&

2&7& fkujhbsvb&wfhbtkbf se fhf L(G) tyf(

itcfcdktkb& CF uhfvfnbrf G=(N,å ,P,S).

ufvjcfcdktkb& ² lbf[² ^ se L(G) ¹ Æ . ² fhf² obyffqvltu itvs[dtdfib&

vtsjlb& dfut,s N₀, N₁,... cbvhfdktt,c htrehcbekfl%

1& lfdeidfs N₀=Æ lf i=1.

2. fdfujs N_i={ A| A® a Î P lf a Î (N_{i-1È å} )^{*} } È} N_i-1

3. se N_i-1, vfiby ufdpfhljs i thsbs lf uflfdblts (2) yf,b]pt& obyffqvltu itvs[dtdfib vbdbqjs N_e=N_i.

4. se SÎ N_e, vfiby ufvjcfcdktkpt ufvjdbnfyjs ² lbf[ ² ^ obyffqvltu itvs[dtdfib ² fhf ² & ’

hflufy N_eÍ N, fvbnjv 2&7 fkujhbsvb eylf ufxthltc .dtkfpt vtnb n+1-]th (2) yf,b]bc ufyvtjht,bc itvltu^se N itbwfdc n hfjltyj,f fhfnthvbyfkc& lfdfvnrbwjs 2&7 fkujhbsvbc rjhtmnekj,f& lfvnrbwt,f vfhnbdbf lf itvlujvib ufvjlut,f hjujhw vjltkb hfvjltybvt fyfkjubehb lfvnrbwt,t,bcfsdbc&

2&12 stjhtvf& fkujhbsvb 2&7 fv,j,c ² lbf[² v[jkjl lf v[jkjl vfiby^ hjwf SÞ ^*W hjvtkbvt WÎ å ^* ]fzdbcfsdbc&

lfvnrbwt,f& sfdlfgbhdtkfl lfdfvnrbwjs i-c vb[tldbs bylemwbbs^ hjv

(2.4.1). se AÎ N_i, vfiby AÞ ^*W hjvtkbvt WÎ å ^* ]fzdbcfsdbc&

,fpbcb% i=0, fh cfzbhjt,c lfvnrbwt,fc^ hflufy N_{0¹ Æ} .

dbuekbc[vjs^ hjv (2.4.1) ztivfhbnbf i-csdbc^ lf fdbqjs AÎ N_i+1. se A tresdybc fuhtsdt N_i_c^ vfiby bylemwbbc yf,b]b nhbdbfkehbf& se AÎ N_i+1-N_i, vfiby fhct,j,c otcb A® X₁X₂...X_k^ cflfw .jdtkb X_i cbv,jkj tresdybc fy å fy N_i-c& fvudfhfl^ .jdtkb X_j-csdbc itb'kt,f dbgjdjs bctsb W_j ]fzdb^ hjv X_jÞ ^*W se X_{jÎ å} , vfiby W=X_j, obyffqvltu itvs[dtdfib W_j -c fhct,j,f ufvjvlbyfhtj,c (2.4.1)- lfy& fldbkfl xfyc^ hjv

AÞ X₁...X_kÞ ^*W₁X₂...X_kÞ ^*...Þ ^*W₁W₂...W_k

itvs[dtdf K=0 ( t&b& A® e otcb) fhff ufvjhbw[ekb& bylemwbbc yf,b]b lfvsfdht,ekbf&

N_i cbvhfdktt,bc ufyvfhnt,f epheydtk.jac^ hjv se N_i=N_i+1, vfiby N_i=N_i+1=... xdty eylf dfxdtyjs^ hjv se AÞ ^*W hjvtkbvt WÎ å ^* ]fzdbcfsdbc^ vfiby AÎ N_e. ptvjs ufrtst,ekb itybidybc 'fkbs .dtkfathb^ hbc xdtyt,fw cfzbhjf tcff bc^ hjv AÎ N_i hjvtkbvt i-csdbc& n-bc vb[tldbs bylemwbbs lfdfvnrbwjs^ hjv

(2.4.2) se, AÞ ⁿW, vfiby AÎ N_i hjvtkbvt i-csdbc& ,fpbcb%n=1, nhbdbfkehbf^ hflufy fv itvs[dtdfib i=1. lfdeidfs^hjv (2.4.2) ztivfhbnbf n-csdbc^lf dsmdfs AÞ ⁿ⁺¹W. vfiby itb'kt,f lfbothjc AÞ X₁...X_kÞ ⁿW, cflfw W=W₁...W_k ]fzdb bctsbf^ hjv X_iÞ ^njW_j .jdtkb j-cf lf n_j£ n-csdbc&

(2.4.2)-bc sfyf[vfl^ se X_jÎ N, vfiby X_jÎ N_i hjvtkbvt j-csdbc& se X_{jÎ å} , vfiby i_j=0. lfdeidfs i=1+max(i₁,...,i_k), vfiby ufyvfhnt,bc sfyf[vfl AÎ N_i lf bylemwbf lfvsfdht,ekbf&

xfdcdfs A=S (2.4.1)-cf lf (2.4.2)-ib lf vbdbqt,s stjhtvbc lfvnrbwt,fc&”

itltub& G rjyntmcnbcfufy sfdbceafkb uhfvfnbrbcfsdbc L(G) tybc cbwfhbtkbc ghj,ktvf uflfo.dtnflbf&”

ufyvfhnt,f& XÎ (NÈ å ) cbv,jkjc deojljs vbeqotdflb CF uhfvfnbrfib G=(N,å P,S), se X fh ud[dlt,f fhwths ufvj.dfyfl ]fzdib&

vbeqotdflb cbv,jkjt,b itb'kt,f vjdbwbkjs CF uhfvfnbrblfy itvltub fkujhbsvbc cfiefkt,bs%

itcfcdktkb& CF uhfvfnbrf G=(N,å ,P,S).

ufvjcfcdktkb& CF uhfvfnbrf G¢ =(N,¢ å ¢ ,P¢ ,S) hjvkbcsdbcfw

1&L(G¢ )=L(G),

2. .jdtkb XÎ N¢ È å ¢ - fhct,j,c bctsb a lf b ]fzdt,b (N¢ È å ¢ ) -lfy^ hjv SÞ _G1^* a Xb .

1& lfdeidfs V₀={ S} lf i=1.

2. lfdeidfs V_i={ X| P-ib fhbc A® a Xb lf AÎ V_{i-1} È} V_i-1.

3. se V_i¹ V_i-1, vfiby lfdeidfs i=i+1 lf uflfdblts (2) yf,b]pt& obyffqvltu itvs[dtdfib^ dsmdfs

N¢ =V_iÇ N,

å ¢ =V_{iÇ å}

P¢ itlut,f P cbvhfdkbc bctsb otct,bcfufy^ hjvkt,bw itbwfdty v[jkjl cbv,jkjt,c V_i-cfufy^ G¢ =(N¢ ,å ¢ ,P¢ ,S).–

2.7 lf 2&8 fkujhbsvt,b 'fkbfy udfyfy thsbvtjhtc&itdybiyjs hjv 2&8 fkujhbsvbc vt-2 yf,b]b itb'kt,f ufdbvtjhjs v[jkjl cfchekj hbw[d]th^ hflufyfw V_i£ NÈ å . ufhlf fvbcf^ i-c vb[tldbs bylemwbbs gbhlfgbhb lfvnrbwt,f udbxdtyt,c^ hjv SÞ G' a Xb , vfiby lf v[jkjl vfiby^hjwf XÎ V_i hjvtkbvt i-csdbc& f[kf xdty itudb'kbf vjdbwbkjs CF uhfvfnbrblfy .dtkf ecfhut,kj cbv,jkj&

itcfcdktkb& CF uhfvfnbrf G=(N,å ,P,S), hjvtkbw L(G)¹ Æ .

ufvjcfcdktkb&CF uhfvfnbrf G¢ =(N¢ ,å ¢ ,P¢ ,S), hjvkbcsdbcfw L(G¢ )=L(G) lf (N¢ È å ¢ )-ib fhff ecfhut,kj cbv,jkjt,b&

1& G-pt 2&7 fkujhbsvbc ufvj.tyt,bs vbdbqjs N_e.lfdeidfs G₁=(NÇ N_e,å ,P₁,S), cflfw P₁ itlut,f P cbvhfdkbc bctsb otct,bcfufy^hjvkt,bw itbwfdty v[jkjl N_{eÈ å} -c cbv,jkjt,c&

2& G-pt 2&8 fkujhbsvbc ufvj.tyt,bs vbdbqjs G¢ =(N¢ ,å ¢ ,P¢ ,S).–

2.9 fkujhbsvbc 1 yf,b]pt G-c xfvjcwbklt,f .dtkf bctsb fhfnthvbyfkt,b^hjvkt,bw fh ofhvjij,ty nthvbyfkeh ]fzdt,c& itvltu 2 yf,b]pt xfvjcwbklt,bfy .dtkf vbeqotdflb cbv,jkjt,b& .jdtkb X cbv,jkj vbqt,ekb uhfvfnbrblfy eylf vjyfobktj,ltc ths vfbyw SÞ ^*WXYÞ ^*WXY cf[bc ufvj.dfyfib& itdybiyjs^ hjv se sfdlfgbhdtkfl ufvjdb.tyt,s 2&8 fkujhbsvc lf itvltu 2&7- fkujhbsvc^ vfiby .jdtksdbc dth vbdbqt,s uhfvfnbrfc^hjvtkbw fh itbwfdc ecfhut,kj cbv,jkjt,c&

2&13 stjhtvf& G¢ uhfvfnbrf^hjvtkcfw fut,c 2&9 fkujhbsvb fh itbwfdc ecfhut,kj cbv,jkjt,c lf

L(G)=L(G¢ ).

lfvnrbwt,f& bvbc lfvnrbwt,fc^ hjv L(G)=L(G¢ ) vfhnbdbf& dbuekbc[vjs^ hjv AÎ N¢ ecfhut,kj cbv,jkjf&vfiby ecfhut,kj cbv,jkjc ufyvfhnt,bc sfyf[vfl itb'kt,f ofhvjudblutc jhb itvs[dtdf%

1 itvs[dtdf% SÞ _G1^*a Ab ufvj.dfyf ite'kt,tkbf hjujhbw fh eylf b.jc a lf b & fcts itvs[dtdfib A cbv,jkjc xfvjwbkt,f vj[lt,f 2&9 fkujhbsvbc vt-2 yf,b]bc lhjc&

2 itvs[dtdf% SÞ _G1^*a Ab hjvtkbvt a lf b -csdbc^ vfuhfv AÞ _G1^*W ufvj.dfyf WÎ å ¢ ^* fh fhct,j,c& vfiby A fh xfvjcwbklt,f vt-(2) yf,b]pt lf^ ufhlf fvbcf^ se AÞ _G^*g Bd , vfiby B-w fh xfvjcwbklt,f vt-(2) yf,b]pt& fvudfhfl^ se AÞ _G^*W, vfiby AÞ _G1^*W.

fmtlfy itb'kt,f lfdfcrdyfs^ hjv AÞ _G^*W WÎ å ^*-csdbc fh fhct,j,c lf A xfvjcwbklt,f (1) yf,b]pt&

bvbc lfvnrbwt,f hjv G¢ -bc fhwthsb nthvbyfkb fh itb'kt,f fh itb'kt,f b.jc ecfhut,kj xfnfhlt,f fyfkjubehfl&–

2&22 vfufkbsb& ufydb[bkjs G=({ S,A,B} ,{ a,b} ,P,S) uhfvfnbrf^cflfw P itlut,f otct,bcfufy%

S® a| A

A® AB

B® b

ufvjdb.tyjs G-c vbvfhs 2&9 fkujhbsvb&(1) yf,b]pt vbdbqt,s N_e={ S,B} lf G₁=({ S,B} ,{ a,b} ,{ S® a,B® b} ,S).

2.8 fkujhbsvbc ufvj.tyt,bs^vbdbqt,s V₂=V₁={ S,a} . fvudfhfl G¢ =({ S} ,{ a} ,{ S® a} ,S).

se G-c vbvfhs ufvjdb.tyt,s ]th 2&8 fkujhbsvc ^vfiby fqvjxylt,f^hjv .dtkf cbv,jkj vbewotdflbf^fct hjv uhfvfnbrf fh itbwdkt,f& itvltu 2&7 fkujhbsvbc ufvj.tyt,f vjudwtvc N_e={ S,B} lf itltufl udtmyt,f uhfvfnbrf G₁, hjvtkbw ufyc[dfdlt,f G¢ -cfufy&–

[ibhfl [tkcf.htkbf CF uhfvfnbrblfy G vjdbwbkjs e otct,b^ t&b& A® e cf[bc otct,b&vfuhfv se eÎ L(G), vfiby w[flbf^ hjv A® e cf[bc otct,c dth vjdbwbkt,s&

ufyvfhnt,f& deojljs CF uhfvfnbrfc G=(N,å ,P,S) uhfvfnbrf e otct,bc ufhtit ( fy fhflfgfnfhfdt,flb), se fy

1&P fh itbwfdc e otct,c^fy

2& fhct,j,c pecnfl thsb e otcb S® e lf S fh ud[dlt,f lfyfhxtyb otct,bc v[fhtib&

2&10 fkujhbsvb& e otct,bc ufhtit uhfvfnbrfl ufhlfmvyf&

itcfcdktkb& CF uhfvfnbrf G=(N,å ,P,S).

ufvjcfcdktkb& tmdbdfktynehb CF uhfvfnbrf G¢ =(N¢ ,å ,P¢ ,S¢ ) e otct,bc ufhtit&

(1) fdfujs N_e={ A| AÎ N lf AÞ ⁺_Ge} tc fyfkjubehbf bvbcf^hfw b.j 2&7 lf 2&8 fkujhbsvt,ib lf dnjdt,s lfvnrbwt,bc ufhtit&

(2) fdfujs P¢ bct^ hjv

a. se A® a ₀B_{1a 1}B_{2a 2}...B_{ka k} tresdybc P,K³ O lf B_iÎ N_e 1£ i£ k, [jkj fhwthsb a _j ]fzdbcf cbv,jkj fh tresdybc (O£ J£ K) fh tresdybc N_e-c^ vfiby Pⁱ-ib xfdhsjs .dtkf otct,b A® a ₀X_{1a 1}X₂...a _k-1X_{ka k}, cflfw X_i fhbc fy B_i fy e, vfuhfv fh xfdhsjs A-e otcb (tc itb'kt,f bv itvs[dtdfib^ se .dtkf a _i njkbf e-cb).

b. se SÎ Ne, vfiby P¢ -ib xfdhsjs otcb

S¢ ® e| S,

cflfw S¢ f[fkb cbv,jkjf lfdeidfs N¢ =NÈ { S¢ } .

obyffqvltu itvs[dtdfib lfdeidfs hjv N¢ =N lf S¢ =S.

(3) vbdbqjs ^ hjv G¢ =(N¢ ,å ,P¢ ,S¢ ).–

2.23 vfufkbsb& ufydb[bkjs uhfvfnbrf 2&19 vfufkbsblfy otct,bs

S® aSbS| bSaS| e fv uhfvfnbrbcfsdbc 2&10 fkujhbsvbc ufvj.tyt,bs^ vbdbqt,s uhfvfnbrfc

S¢ ® S| e

S® aSbS| bSaS| aSb| abS| ab| bSa| baS| ba” .

2& 14 stjhtvf& 2&10 fkujhbsvb udf'ktdc uhfvfnbrfc e otct,bc ufhtit^ hjvtkbw itcfdfkb uhfvfnbrbc tmdbdfktynehbf&

lfvnrbwt,f& eiefkjl xfyc^hjv 2&10 fkujhbsvb udf'ktdc G¢ uhfvfnbrfc e otct,bc ufhtit& bvbc cfxdtyt,kfl^ hjv L(G)=L(G¢ ), cfrvfhbcbf lfdfvnrbwjs bylemwbbs W ]fzdbc cbuh'bc vb[tldbs^ hjv

AÞ · _G1W vfiby lf v[jkjl vfiby^hjwf W¹ e lf AÞ · _GW. (2.4.3) hbc lfvnrbwt,fw vfhnbdbf& xfdcdfs S A-c yfwdkfl (2.4.3)-ib& d[tlfds^ hjv WÎ L(G) W¹ e-csdbc v[jkjl lf v[jkjl vfiby^hjwf WÎ L(G¢ ). w[flbf hjv eÎ L(G) v[jkjl lf v[jkjl vfiby^ hjwf eÎ L(G¢ ). fvudfhfl L(G)=L(G¢ ). ”

uhfvfnbrbc c[df cfcfhut,kj ufhlfmvyff A® B cf[bc otct,bc vjwbkt,f^ hjvkt,cfw xdty deojlt,s ]fzdeh otct,c&

itcfcdktkb& CF uhfvfnbrf G e otct,bc ufhtit&

ufvjcfcdktkb& tmdbdfktynehb CF uhfvfnbrf G¢ e otct,bcf CF

]fzdehb otct,bc ufhtit&

1& .jdtkb AÎ N-csdbc fdfujs N_A={ B| AÞ · B}

a. vbdbqjs N₀={ A} lf i=1.

b. vbdbqjs N_i={ C| B® c tresdybc P lf BÎ N_{i-1} È} N_i-1.

c. se N_i¹ N_i-1 lfdeidfs i=i+1 lf (b) yf,b]b ufdbvtjhjs& obyffqvltu itvs[dtdfib vbdbqjs N_A=N_i.

2. fdfujs P¢ fct% se B® a tresdybc P-c lf bub ]fzdehb otcb fhff^ xfdhsjs P¢ -ib A® a otcb .dtkf bctsb A-csdbc^ hjv BÎ N_A.

3& vbdbqjs G¢ =(N,å ,P¢ ,S). •

2&24 vfufkbsb&ufvjdb.tyjs 2&11 fkujhbsvb G₀ uhfvfnbrbcfsdbc^hjvkbc otct,bf

E® E+T| T

T® T*F| F

F® (E)| a

(1) yf,b]pt N_E={ E,T,F} , N_T={ T,F} , N_F={ F} . (2) yf,b]bc itvltu P¢ cbvhfdkt bmyt,f fctsb%

E® E+T| T*F| (E)| a

T® T*F| (E)| a

F® (E)| a. •

2&15 stjhtvf& G¢ uhfvfnbrfc^ hjvtkcfw fut,c 2&11 fkujhbsvb udf'ktdc G¢ uhfvfnbrfc^ hjvtkcfw ]fzdehb otct,b fh uffxybf&

sfdlfgbhdtkfl dfxdtyjs^ hjv L(G¢ )£ L(G). dsmdfs^ WÎ L(G¢ ). vfiby G¢ uhfvfnbrfib fhct,j,c ufvj.dfyf SÞ a _{0Þ a 1Þ} ...Þ a _n^W se a _i-lfy a _i+1-pt uflfcdkbcfc A® b otcb ufvjb.tyt,f^ vfiby fhct,j,c bctsb cbv,jkj BÎ N itcf'kt,tkbf B=(A), hjv AÞ · _GB

lf BÞ _Gb . fvudfhfl^ AÞ · _Gb lf a _{iÞ · Ga i+1} fmtlfy ufvjvlbyfhtj,c^ hjv SÞ · _GW lf WÎ L(G), bct hjv L(G¢ )£ L(G).

f[kf dfxdtyjs^ hjv L(G)£ L(G¢ ). dsmdfs WÎ L(G) lf SÞ _{ea 0Þ ea 1Þ e}...Þ _{ea n}=W- W ]fzdbc vfhw[tyf ufvj.dfyff G uhfvfnbrfib& itb'kt,f dbgjdjs i₁,i₂,...i_k byltmct,bc vbvltdhj,f^ hjvtkbw itlut,f pecnfl bv J-cufy^ hjvtksfsdbcfw yf,b]pt a _{j-1Þ ea j} ufvjb.tyt,f fhf ]fzdehb otcbs&

hflufyfw xdty db[bkfds vfhw[tyf ufvj.dfyfc^fvbnjv ]fzdehb otct,bc vbvltdhj,bs ufvj.tyt,f wdkbfy cbv,jkjc^ hjvtkcfw ezbhfdc thsb lf bubdt gjpbwbf vfhw[tyf ufvj.dfyfl ]fzdt,ib& fmtlfy cxfyc^hjv SÞ _{G1a i1Þ a i2Þ G1}...Þ _{G1a ik}=W. fvudfhfl^ WÎ L(G¢ ), hfw bvfc ybiyfdc^ hjv L(G¢ )=L(G). –

ufyvfhnt,f& CF uhfvfnbrfc G=(N,å ,P,S) tojlt,f uhfvfnbrf wbrkt,bc ufhtit^se vfcib fhff ufvj.dfyf AÞ ⁺A AÎ N. G uhfvfnbrfc tojlt,f lf.dfybkb^ se bub fh itbwfdc wbrkt,c^ e-otct,c lf ecfhut,kj cbv,jkjt,c&

e-otct,bc fy wbrkt,bc vmjyt uhfvfnbrt,bc fyfkbpt,b pju]th eahj 'ytkbf^ dblht e-otct,bc fh vmjyt lf ewbrkj uhfvfnbrt,bc fyfkbpb& ufhlf fvbcf^ yt,bcvbth ghfmnbrek cbnefwbfib ecfhut,kj cbv,jkjt,b fewbkt,kj,bc ufhtit phlbfy fyfkbpfnjhbc vjwekj,fc& fvbnjv cbynfmcehb fyfkbpbc pjubthsb fkujhbsvt,bcfsdbc^ xdty vjdbs[jds^ hjv vfsib abuehbht,ekb uhfvfnbrt,b b.dyty lf.dfybkyb& lfdfvnrbwjs^ hjv fv vjs[jdybc vbe[tlfdfl vfbyw ufyb[bkt,f yt,bcvbthb CF tyt,b&

2&16 stjhtvf& se L-CF tyff^vfiby L=L(G) hjvtkbvt lf.dfybkb CF uhfvfnbrbcfsdbc G.

lfvnrbwt,f& ufvjdb.tyjs fkujhbsvt,b 2&8-2&11 CF uhfvfnbrbcfsdbc^ hjvtkbw ufycfpqdhfdc L tyfc&–

ufyvfhnt,f&CF uhfvfnbrbc A otcb tojlt,f A® a cf[bc otcc (fh futhbjs A otcb e-otcib^ hjvtkcfw fmdc cf[t B® e.

itvjdbnfyjs rbltd ufhlfmvyf^ hjvkbc cfiefkt,bsfw itb'kt,f fvjdfuljs uhfvfnbrblfy thsb A® a Bb cf[bc otcb& bvbcfsdbc^ hjv fvjdfuljs tc otcb^ cfzbhjf uhfvfnbrfc lfdevfnjs f[fkb otct,b^ hjvkt,bw vbbqt,f vfcib B fhfnthvbyfkbc itwdkbs vfh]dtyf v[fhbs .dtkf B otcblfy&

2&14 ktvf& dsmdfs G=(N,å ,P,S)-CF uhfvfnbrff lf P itbwfdc otcc A® a Bb , cflfw BÎ N, [jkj a lf b tresdybfy (NÈ å )^*. dsmdfs B® g _{1| g 2|} ...| g _k fv uhfvfnbrbc .dtkf B otcbf& dsmdfs

G¢ =(N,å ,P¢ ,S), cflfw

P¢ =(P-{ A® a Bb } )È { A® a g _{1b | a g 2b |} ...| a g _{kb }}

vfiby L(G)=L(G¢ ). lfvnrbwt,f vfhnbdbf& –

2&25 vfufkbsb& vjdbwbkjs A® aAA otcb G uhfvfnbrblfy^ hjvkbc .dtkf A otcbf A® aAA| b. 2.14 ktvbc ufvj.tyt,bs dbuekbc[vjs a =a,B=A lf b =A lf vbdbqjs G¢ uhfvfnbrf otct,bs A® aaAAA| abA| b

aabbb ]fzdbcfsdbc ufvj.dfybc [tt,b G lf G¢ uhfvfnbrt,ib yfxdtyt,bf 2&12 yf[fnpt& itdybiyjs^ fv ufhlfmvybc tatmnb vlujvfhtj,c 2&12 a yf[fnpt vjwtvekb [bc 'bhbc vbot,t,fib vbc vtjht gbhlfgbh isfvjvfdfksfy&•

A A

a A A a a A A A

a A A b b b b

b b

a b

yf[&2&12& ufvj.dfybc [tt,b% a- G uhfvfnbrfib* b- G¢ uhfvfnbrfib&

ufyvfhnt,f& CF uhfvfnbrfc G=(N,å ,P,S) tojlt,f uhfvfnbrf [jvcrbc yjhvfkeh ajhvfib ( fylf ,byfhek yjhvfkeh ajhvfib), se .jdtk otcc P- lfy fmdc ths-thsb itvltub cf[tt,blfy%

1& A® BC, cflfw A,B lf C tresdybfy N-c^

2& A® a, cflfw aÎ å ,

3. S - e, se eÎ L(G) lf S fh ud[dlt,f c[df otct,bc vfh]dtyf v[fhtib& dfxdtyjs^hjv .jdtkb CF tyf vbbqt,f [jvcrbc yjhvfkehajhvbfyb uhfvfnbrblfy& tc itltub cfcfhut,kjf bv itvs[dtdt,ib^ hjwf udzbhlt,f CF tybc ofhvjlutybc vfhnbdb ajhvf&

itcfcdktkb& lf.dfybkb CF uhfvfnbrf G=(N,å ,P,S).

ufvjcfcdktkb& CF uhfvfnbrf G¢ [jvcrbc yjhvfkeh ajhvfib^ hjvtkbw G-c tmdbdfktynehbf^ t&b& L(G¢ )=L(G).

vtsjlb& uhfvfnbrf G¢ but,f G-cufy itvltuyfbhfl%

1& xfdhsjs P¢ -ib A® a cf[bc .jdtkb otcb P-lfy&

2& xfdhsjs P¢ -ib A® BC cf[bc .jdtkb otcb P-lfy&

3& xfdhsjs P¢ -ib A® e otcb^ se bub b.j P-ib&

4& A® X_i...X_k cf[bc .jdtkb otcbcfsdbc P-lfy^ cflfw K> 2 xfdhsjs P¢ -ib otct,b

A® X¢ _1< X₂...X_k>

< X₂...X_{k> ®} X¢ _2< X₃...X_k>

.

< X_k-2 X_k-1X_{k> ®} X¢ _k-2< X_k-1X_k>

< X_k-1X_{k> ®} X¢ _k-1X¢ _k

cflfw X¢ _i=X_i, se X_iÎ N; X¢ _i- f[fkb fhfnthvbyfkbf^se X_{iÎ å} ;

< X_i...X_{k> -} f[fkb fhfnthvbyfkbf&

5& A® X₁X₂ cf[bc .jdtkb otcbcfsdbc P-lfy^ cflfw thsb vfbyw X₁X₂ cbv,jkjt,blfy tresdybc å ^ xfdhsjs P¢ -ib A® X¢ ₁X¢ ₂ otcb&

6& a¢ cf[bc .jdtkb fhfnthvbyfkbcsdbc^ hjvkt,bw itvjnfybkbf (4) lf (5) yf,b]t,pt^ xfdhsjs P¢ -ib a¢ ® a otcb& lf,jkjc^ N¢ itbwfdc N-c lf .dtkf f[fk fhfnthvbyfkt,c^ hjvkt,bw itvjnfybkbf P¢ fut,bc lhjc& vfiby cf'bt,tkb uhfvfnbrf bmyt,f G¢ =(N¢ ,å ,P¢ ,S).–

2.17 stjhtvf& dsmdfs L fhbc CF tyf& vfiby L=L(G¢ ) hjvtkbvt CF uhfvfnbrbcfsdbc G¢ [jvcrbc yjhvfkeh ajhvfib&

lfvnrbwt,f& 2&16 stjhtvbc sfyf[vfl L ufybcfpqdht,f lf.dfybkb G uhfvfnbrbs& fkujhbsvb 2&12 G-lfy fut,c G¢ uhfvfnbrfc^ hjvtkbw^ w[flbf^ ofhvjlutybkbf [jvcrbc yjhvfkehb ajhvbs& lfudhxtybf dfxdtyjs^ hjv L(G)=L(G¢ ). tc vnrbwlt,f 2&14 ktvbc ufvj.tyt,bs G¢ uhfvfnbrbc .jdtkb otcbcfsdbc^ hjvtksf vfh]dtyf v[fhtib itlbc a¢ , lf itvltu otct,bcfsdbc < X_i...X_j> cf[bc fhfnthvbyfkt,bs& –

2&26 vfufkbsb& dsmdfs G lf.dfybkb uhfvfnbrff^ ufycfpqdhekb otct,bs S® aAB| BA

A® BBB| a

B® AS| b

dfut,s P¢ 2&12 fkujhbsvbs^dnjdt,s hf otct,c S® BA, A® a,B® AS lf B® b. dwdkbs S® aAB otct,bs

S® a¢ < AB> lf < AB> ® AB, [jkj A® BBB-c otct,bs- A® B< BB> lf < BB> ® BB. lf ,jkjc^devfnt,s a¢ ® a, itltufl dbqt,s uhfvfnbrfc G¢ =(N¢ ,{ a,b} ,P¢ ,S), cflfw

N¢ ={ S,A,B,< AB> ,< BB> ,a¢ } , [jkj P¢ itlut,f otct,bcfufy

S® a¢ < AB> | BA

A® B< BB> | a

B® AS| b

< AB> ® AB

< BB> ® BB

a¢ ® a •

f[kf dfxdtyjs^ hjv .jdtkb CF tybcfsdbc itb'kt,f dbgjdjs uhfvfnbrf^ hjvtkibw otct,bc vfh]dtyf v[fhtt,b bo.t,bfy nthvbyfkt,bs& fctsb uhfvfnbrbc fut,f lfae'yt,ekbf tuhts ojlt,ekb vfhw[tyf htrehcbbc fwbkt,fpt&

ufyvfhnt,f& G=(N,å ,P,S) CF uhfvfnbrbc A fhfnthvbyfkc tojlt,f htrehcbekb^ se AÞ ^+a Ab hjvtkbvt a lf b - csdbc& se a =e, vfiby A-c tojlt,f vfhw[ybd htrehcbekb& fyfkjubehfl^se b =e, vfiby A-c tojlt,f vfh]dybd htrehcbekb& uhfvfnbrfc^ hjvtkcfw uffxybf thsb vfbyw vfhw[ybd htrehcbekb fhfnthvbyfkb^ tojlt,f vfhw[ybd htrehcbekb&

pjubths ufhxtdbc fkujhbsvt,c^ hjvkt,ptw xdty itvlujvib ufydb[bkfds fh ite'kbfs bveifjy vfhw[ybd htrehcbek uhfvfnbrt,pt& dfxdtyjs^ hjv yt,bcvbthb CF tyf ufybcfpqdht,f thsb vfbyw fhf vfhw[ybd htrehcbekb uhfvfnbrbs& lfdbo.js CF uhfvfnbrblfy eiefkjl vfhw[ybd htrehcbekj,bc xfvjijht,bs&

2&15 ktvf& dsmdfs G=(N,å ,P,S)-CF uhfvfnbrff^ hjvtkibw

A® Aa _1| Aa _2| ...| Aa _{m| b 1| b 2|} ...| b _n

.dtkf A otct,bf P-lfy lf fhwthsb b _i (i=1,2,...n) ]fzdt,blfy fh bo.t,f A-sb& dsmdfs

G¢ =(NÈ { A¢ } ,å ,P¢ ,S),

cflfw A¢ -f[fkb fhfnthvbyfkbf^ [jkj P¢ vbbqt,f P-cfufy A otct,bc itwdkbs

A® b _{1| b 2|} ...| b _{n| b 1}A¢ | b ₂A¢ | ...| b _nA¢

A¢ ® a _{1| a 2|} ...| a _{m| a 1}A¢ | a ₂A¢ | ...| a _mA¢

otct,bs% vfiby L(G¢ )=L(G).

lfvnrbwt,f&]fzdt,b^hjvkt,bw itb'kt,f vbdbqjs G uhfvfnbrfib A fhfnthvbyfkbcfufy A otct,bc ufvj.tyt,bs .dtkfpt vfhw[tyf fhfnthvbyfkpt /mvybfy (b ₁+b ₂+...+b _n) (a ₁+a ₂+...+a _m)* htuekfhek cbvhfdktc& tc pecnfl bc ]fzdt,bf^ hjvkt,bw itb'kt,f vbdbqjs G¢ -ib A-cufy vfh]dtyf ufvj.dfyt,bs^ ufvjdb.tyt,s hf ths[tk A otcc lf hfvjltybvt]th A¢ otct,c& (itltufl vstkb ufvj.dfyf fh bmyt,f vfhw[tyf). ufvj.dfybc .dtkf yf,b]t,b G-ib^hjvkt,ibw fh ufvjb.tyt,f A otct,b itb'kt,f eiefkjl xfdfnfhjs G¢ -

ib^hflufyfw A otct,bc ufhlf G lf G¢ thsyfbhbf& fmtlfy itb'kt,f lfdfcrdyfs^ hjv L(G¢ )£ L(G).

it,heyt,ekb xfhsdf vnrbwlt,f fhct,bsfl bctdt&G¢ -ib bqt,f vfh]dtyf ufvj.dfyf lf ufyb[bkt,bfy yf,b]t,bc vbvltdhj,t,b^ hjvkt,bw itlut,bfy v[jkjl ths[tk A otct,bc ufvj.tyt,bcfufy lf hfvjltybvt]th A¢ otct,bc ufvj.tyt,t,bcfufy& fvudfhfl^ L(G)=L(G¢ ). –

A A

A α_i1 ß A^'

A α_i2 α_ik A^'

.

. α_ik-1 A^'

.

A &

&

A α_ik .

A^'

β

α_i2 A^'

α_i1

A

a b

yf[&2&13& [bc yfobkt,b%a-[bc yfobkb G-ib& b-itcf,fvbcb yfobkb G¢ -ib&

2&27 vfufkbsb& dsmdfs G₀ xdtyb xdtekt,hbdb uhfvfnbrff otct,bs&

E® E+T| T

T® T*F| F

F® (E)| a

se fv uhfvfnbrbc vbvfhs ufvjdb.tyt,s 2&15 ktvbc rjycnhemwbfc^ vfiby vbbqt,f tmdbdfktynehb G¢ uhfvfnbrf otct,bs

E® T| TE¢

E¢ ® +T| +TE¢

T® F| FT¢

T¢ ® · F| · FT¢

F® (E)| a. –

f[kf xdty vpfl dfhs fqdothjs fkujhbsvb^ hjvtkbw lf.dfybkb CF uhfvfnbrfc vjfijht,c vfhw[tyf htrehcbfc& sfdbcb bltbs tc fkujhbsvb /ufdc htuekfhek rjtabwbtynt,bfyb ufynjkt,bc fvj[cybc fkujhbsvc&

itcfcdktkb& lf.dfybkb CL uhfvfnbrf G=(N,å ,P,S).

ufvjcfcdktkb& tmdbdfktynehb CL uhfvfnbrf G¢ vfhw[tyf htrehcbbc ufhtit&

1& dsmdfs N={ A₁,...,A_n} . ufhlfdmvyfs G bct^ hjv A_{i® a} otcib a ]fzdb bo.t,jltc nthvbyfkbs fy bctsb A_j-sb^ hjv j> i. fv vbpybs dsmdfs i=1.

2& dsmdfs A_i otct,bc cbvhfdktf A_i® A_{ia 1|} ...| A_{ia m| b 1|} ...b _p, cflfw fhwthsb b _j ]fzdt,blfy fh bo.t,f A_k-sb^ se K£ i. (tc .jdtksdbc itcf'kt,tkbf). itdwdfkjs A_i otct,b

A_{i® b i|} ...| b _{p| b 1}A¢ _i| ...| b _pA¢ _i

A¢ _{i® a 1|} ...| a _{m| a 1}A¢ _i| ...| a _mA¢ _i

otct,bs cflfw A¢ _i f[fkb fhfnthvbyfkbf& .dtkf A_i otct,bc vfh]dtyf v[fhtt,b f[kf bo.t,bfy nthvbyfkbs fylf A_k-sb^ cflfw K> i.

3& se i=n, vfiby vbqt,ekb uhfvfnbrf xfdsdfkjs cf,jkjj itltufl lf ufdxthlts& obyffqvltu itvs[dtdfib vbdbqjs i+1 lf j=1.

4. itdwdfkjs .jdtkb A_i® Aja cf[bc otcb otct,bs A_{i® b 1a |} ...| b _ma , cflfw A_{j® b 1| b 2|} ...| b _m .dtkf A_j otct,bf& hflufyfw .jdtkb A_j otcbc vfh]dtyf v[fht bo.t,f erdt nthvbyfkbs fy A_k-sb K> j-csdbc^fvbnjv .jdtkb A_i otcbc vfh]dtyf v[fhtw ^f[kf tmyt,f tc sdbct,f&

5& se j=i-1 uflfdblts vt-(2) yf,b]pt& obyffqvltu itvs[dtdfib vbdbqjs j=j+1 lf uflfdblts vt-(4) yf,b]pt&—

stjhtvf 2&18& .jdtkb CF tyf ufybcfpqdht,f fhfvfhw[ybd htrehcbekb uhfvfnbrbs&

lfvnrbwt,f& dsmdfs G lf.dfybkb uhfvfnbrff^ hjvtkbw ofhvjij,c KL L tyfc& vfcpt 2&13 fkujhbsvbc ufvj.tyt,bcfc^ ufvjb.tyt,f v[jkjl bc ufhlfmvyt,b^ hjvkt,bw vj[ctyt,ekbf 2&14 lf 2&15 ktvt,ib& fvbnjv cf,jkjj G¢ uhfvfnbrf ofhvjmvybc L tyfc&

xfvjdf.fkb,js jhb lt,ekt,f^hjvkt,bw fhct,bsfl erdt itud[dlf 2&13 fkujhbsvbc vt-(2) lf vt-(4) yf,b]t,bc fqotht,bc ,jkjib%

2&4&4& i-csdbc vt-(2) yf,b]bc itchekt,bc itvltu .jdtkb A_i otcbc vfh]dtyf v[fht bo.t,f nthvbyfkbs fy bctsb A_k-sb^ hjv K> I.

Ddaprogramebis cnobili enebi ganisazRvrebian konteqstisagan Tavisufali gramatikebiT. Ees imas niSnavs, rom Tu Cven aviRebT raime daprogramebis enas magaliTad, FORTRAN-IV-s Cven SegviZlia SevadginoT konteqstisagan Tavisufali gramatika GF, romelic uSvebs mxolod FORTRAN-IV-ze sintaqsurad sworad Caweril programebs. e. i. nebismieri FORTRAN-IV-ze sworad Cawerili programisaTvis, romelic aris raime P teqsti, moiZebneba GF gramatikaSi gamoyvana SÞ *P da raime P₁ arasworad Cawerili programisaTvis ar arsebobs SÞ *P₁ GF gramatikaSi. Aqedan gamomdinareobs, rom Tu Cven gveqneba algoriTmi SÞ *P nebismieri P- s sapovnelad, maSin Cven SegviZlia am algoriTmis realizacia kompiuterze SA programis saxiT da misi saSualebiT SevamowmoT P programa aris Tu ara FORTRAN-IV- ze sworad Cawerili programa. AaseT SA programas ewodeba sintaqsuri analizatori. igive amocana SeiZleba gadawyvetil iqnes nebismieri konteqstisagan Tavisufali gramatikisaTvis specialuri mowyobilobiT, romelsac ewodeba avtomati maRaziuri mexsierebiT. AaseTi avtomatebi sasruli avtomatebisagan ZiriTadad gansxvavdebian imiT, rom maT SeuZliaT specialur mexsierebaSi daimaxsovron Tu ra mdgomareobebi gaiares mocemuli momentisaTvis da amiT aRadginoT winaistoria, romelic gaiara avtomatma sawyisi mdgomareobidan mocemul mdgomareobamde. AaseT specialur mexsierebas ewodeba maRaziuri mexsiereba an rasac programistebi meorenairad uwodeben steks. stekSi simbolos Cawera xdeba stekis TavSi da stekidan simbolos aReba xdeba igive stekis Tavidan. stekis Tavi yovelTvis uTiTebs bolos Caweril simbolos. roca vwerT simbolos stekSi, stekis Tavi erTi adgiliT gadaiwevs win da iq Caiwereba mocemuli simbolo e. i. winaT Cawerili simbolos win, xolo roca viRebT simbolos stekidan maSin xdeba piriqiT. stekis Tavi daiwevs erTi simboloTi ukan da stekis TavSi moxvdeba Semdegi simbolo. Amgvarad stekis Tavi moZraobs win da ukan masSi simbolos Cagdeba amogdebis mixedviT. Ees ki uzrunvelyofs stekSi bolos Cagdebuli simbolos pirvelad amoRebas. AaseT stekebs uwodeben LIFO(Last Input First Output) stekebs. imisaTvis, rom isini ganvasxvaoT FIFO(First Input First Output) stekebisagan, romelTa saSualebiT xdeba rigebis modelireba kompiuterSi. zogadad, avtomati maRaziuri mexsierebiT Sedgeba:

3. sasruli maRaziuri mexsierebisagan anu LIFO stekisagan (ix. Ddiagrama):

Ddiagrama

AM=(Q, å , d , Г, q_0, z_0,F) sadac

Q mdgomareobaTa simravlea,

Γ maRaziur simboloTa simravlea,

q_0Î Q sawyisi mdgomareobaa,

z₀ maRaziis ZirSi moTavsebuli simboloa, romelic miuTiTebs maRaziis dacarielebas. F Í Q saboloo mdgomareobaTa simravlea da d aris QX(å È e})XΓ simravlis gadasaxva iseT simravleSi romlis elementebia QXΓ* simravlis qvesimravleebi.

sasruli avtomatebis analogiurad ganisazRvreba AM avtomatis konfiguracia da taqti. (q,W,d) aris AM avtomatis mimdinare konfiguracia Tu avtomati imyofeba q mdgomareobaSi, Sesavali striqonia am momentSi W da a aris maRaziis SigTavsi. Aqedan gamomdinare (q,w,a ) sameuli aris QXå *XΓ* is elementi. roca a =e maRazia aris carieli. Ddamokidebulebas (q,aw,ya ) ├(q₁,W,g a ) ewodeba AM avtomatis taqti, roca AM avtomati (q,aw,ya ) konfiguraciidan gadadis (q,w,g a ) taqtSi da d (q,a,y) simravle Seicavs (q₁,g ) elements. Ees niSnavs rom AM avtomatis mimdinare mdgomareobaa q da Sesasvlelis mimdinare simboloa a , maRaziis TavSi gvaqvs y simbolo da Tu d (q,a,y) simravle Seicavs (q,g )-s, maSin AM avtomatis mimdinare mdgomareoba gaxdeba q₁, mimdinare Sesasvleli simbolo iqneba a-s momdevno simbolo marcxnidan marjvniv mimarTulebiT da maRaziaSi y striqoni Seicvleba g -Ti. Tu a=e aseT SemTxvevaSi taqts ewodeba carieli taqti. carieli taqti SesaZlebelia maSinac, roca Sesasvleli striqoni carielia, xolo Tu maRazia carielia e. i. maRaziaSi gvaqvs mxolod z₀ simbolo, Semdgomi taqti SeuZlebelia.├ⁱ aRiniSneba ├ damokidebulebis i xarisxi e.i. mimdevrobiT Sesrulebuli teqstebis i raodenoba, xolo ├* da ├* aRiniSnebian Sesabamisad ├damokidebulebis tranzitul- refleqsuri da tranzituli Caketvebi. (q₀,w,z₀) aris sawyisi konfiguracia, sadac WÎ å * , xolo saboloo konfiguraciaa (q,e,a ) Tu qÎ F da a Î Γ*. Tu (q₀,W,z₀)├(q,e,a ) raime qÎ F da a Î Γ* maSin vityviT, rom W striqons uSvebs AM avtomati an rac igivea WÎ L(AM) e. i. W ekuTvnis AM avtomatiT gansazRvrul enas da L(AM) aris AM avtomatiT daSvebuli yvela striqonis simravle.

GganvixiloT magaliTi. avagoT iseTi AM avtomati, romelic gansazRvravs L={aⁿb^nï n≥1} enas. imisaTvis, rom aseTi saxis nebismieri striqoni dauSvas Aavtomatma saWsiroa Sesasvleli striqonidan TiToTiTod CavagdoT a niSnebi sanam ar amovwuravT maT da Semdeg yoveli b-sTvis amovagdoT sityvidan a niSani da Tu Sesasvleli striqonis dacarielebis dros stekis TavSi aRmoCndeba z₀ simbolo amovagdoT isic da am dros AM avtomati unda iyos saboloo mdgomareobaSi. radgan steki dacarieldeba avtomats aRar SeeZleba axal mdgomareobaSi gadasvla da amave dros Sesasvleli striqonic dacarielebulia. rac imas niSnavs, rom aseT Sesasvlel striqons uSvebs AM avtomati. SevniSnoT, rom am enis daSveba ar SeuZlia sasrul avtomats, radgan mas ara aqvs a niSnebis damaxsovrebis saSualeba. Aamgvarad, AM avtomats SeiZleba hqondes aseTi saxe:

AM=({q₀,q₁,q₂,}, {a,b},{a,z₀},d ,q₀,z₀,{q₂}), sadac

d (q₀,a,z₀,)={(q₁, az₀)},

d simravlis pirveli elementi uzrunvelyofs avtomatis sawyis mdgomareobaSi pirveli Sesasvleli a niSnis Cagdebas stekis ZirSi da avtomati gadadis q₁ mdgomareobaSi. Mmeore elementi uzrunvelyofs q₁ mdgomareobaSi myofi avtomatisTvis Semdegi a niSnis Cagdebas stekSi. Mmesame elementi uzrunvelyofs q₁ mdgomareobaSi myofi avtomatisaTvis Sesasvleli b niSnis SemTxvevaSi stekidan a niSnis amogdebas, roca svetis TavSi gvaqvs a niSani da avtomati gadadis q₂ mdgomareobaSi. MmexuTe elementi uzrunvelyofs z₀ amogdebas stekis Tavidan, roca avtomati q₂ mdgomareobaSia Sesasvleli niSnis gamouyeneblad da amgvarad acarielebs steks. Tu am momentSi Sesasvleli striqoni carielia, maSin Sesasvlel striqons uSvebs AM avtomati. Yyvela SemTxvevaSi, garda bolo SemTxvevisa , Sesasvlel striqonSi mimdinare niSani xdeba Semdegi niSani. GganvixiloT raime Sesasvleli striqoni wÎ {a,b}*da vTqvaT AM avtomati (q₀,w_,z₀) sawyis mdgomareobaSia. AM avtomatma, rom gaagrZelos muSaoba e.i. gadavides Semdeg konfiguraciaSi, mas aqvs erTaderTi SesaZlebloba gamoiyenos d simravlis pirveli elementi. magram amisaTvis saWiroa w=aw₁. AaseT SemTxvevaSi avtomati gadadis axal konfiguraciaSi (q₁,w₁,az₀). Aam konfiguraciaSi MA avtomats SeuZlia gamoiyenos d - s meore an mesame elementi. Mmeore elementis gamoyenebis SemTxvevaSi unda gvqondes w₁=aw₂ da MA avtomati gadava konfiguraciaSi (q₁,w₂,aaz₀) da Cven varT igive situaciaSi, rac wina konfiguraciaSi. Ee.i. Cven kvlav SegviZlia gamoviyenoT d simravlis meore an mesame elementi. vTqvaT gamoviyeneT d simravlis meore an mesame elementi. vTqvaT gamoviyeneT d - s meore elementi k-jer, maSin gveqneba aseTi konfiguracia (q₁,w_k+2, a^k+2z₀). Aamis Semdeg MA rom moxvdes q₂ mdgomareobaSi

fv sfdib ofhvjlutybkbf byukbcehb tybc ahfuvtynb^ hjvtkbw fqothbkbf vjyntubec ihjvfib PTQ& dbo.t,s gfnfhf ahfuvtynbs lf vfc dfafhsjdt,s sfylfsfyj,bs& .jdtk yf,b]pt cbynfmcb lf ctvfynbrf uffyfkbpt,ekbf afhsjl& cgtwbfkehb .ehflqt,f tmwtdf vjnbdfwbfc lf fyfkbpbc lfpecnt,fc& cgtwbfkehb .ehflqt,f vbtmwtdf fuhtsdt lfveifdt,bc fkut,hek lf fkujhbsvek fcgtmnt,c& fkut,hekb ufy[bkdf bsdfkbcobyt,c bvbc f[cyfc^ se hfnjv pjubthsb ltnfkt,b fhbfy fct lf fhf c[dfyfbhfl& fkujhbsvekb fcgtmnt,b t[t,f bv vtsjlc^ hjvkbc cfiefkt,bsfw vfhnbdfl ofhvjblubyt,f vybidytkj,t,b& bvcfsdbc hjv vbdfqobjs fvfc pjubthsb otct,b vjwtvekb bmyt,f ajhvekt,bc ufcfvfhnbdt,kfl& ahfuvtynb vlblfhbf ctvfynbrehfl cfbynthtcj vjdktyt,bs& mdtvjs vt vbdesbst, pjubths vfsufyc rjvtynfht,bs&

~1` John runs.

(2) Every man runs.

(3) run (John)

(4) " C [ man (x)® run (x)] .

~5` Every man loves a woman.

tc obyflflt,f itb’kt,f b.jc ufut,ekb hjujhw rjyrhtnekb hjvtkbvt mfkb it.dfht,ekbf .jdtkb vfvfrfwbc vbth ~ vfufkbsfl Brigitte Bardot`^ fy hjwf .jdtkb vfvfrfwbcfsdbc itb’kt,f b.jc c[dflfc[df mfkb ~dsmdfs sfdbcb cfresfhb ltlf`& fvudfhfl ~5` fhbc jvjybvbehb& fv jhb itcf’kt,kj,bc ufvj& fctsb cf[bc jvjybvbfc tojlt,f "cfpqdht,bc jvjybvbf"mdfynbabrfnjht,bcfsdbc& jhb c[dflfc[dfyfbhb ofrbs[df fv obyflflt,bcf uhfvfnbrekfl vjwtvekbf ~6`-cf lf ~7`-ib&

~6` " C [ man(x)® $ y[ woman(y) Ù love(x,y)] ]

(7) $ y [ woman(y) Ù " x[ man(x)® love(x,y)] ] .

(8) John seeks a unicorn.

(9) John finds a unicorn.

fv jh obyflflt,fc fmdc thsyfbhb ajhvf lf v[jkjl vfsb pvyt,b ufyc[dfdlt,bfy thsbvtjhbcfufy& dbyvtv itb’kt,f babmhjc hjv vfs eylf /mjylts thsyfbhb fpht,b fuhtsdt& thsflthsb ufyc[dfdt,f fhbc bc^ hjv c[dflfc[df lfvjrblt,ekt,t,c ufvj[fnfdty ]jycf lf vfhnjhmfc ijhbc& vfuhfv tc fct fhff& vblujvf^ hjvtkbw fv,j,c^ hjv seek-lfvjrblt,ekt,f fhbc .jdtksdbc hfbvt lfvjrblt,ekt,f jh bylbdblc ijhbc fh eylf b.jc vbcfqt,b& xdty eylf ufdbsdfkbcobyjs ~8`-csdbc hfbvt fphb^ hjvkblfyfw fh ufvjvlbyfhtj,c hjv vfhnjhmt,b fhct,j,ty& vfuhfv ~8` itb’kt,f b.jc ufvj.tyt,ekb bv cbnefwbfibw hjwf vfhnjhmt,b fhct,j,ty& fvudfhfl udfmdc jvjybvbf fv jh itcf’kt,kj,fc ijhbc& vfc fmdc ofrbs[df^ hjvkblfyfw ufvjvlbyfhtj,c^ hjv .dtkfpt vwbht thsb vfhnjhmf vfbyw fhct,j,c ~htathtywbfkehb ofrbs[df` lf ofrbs[df^ hjvkblfyfw tc fh ufvjvlbyfhtj,c ~fhfhtathtywbfkehb ofrbs[df`& htathtywbfkehb lf fhfhtathtywbfkehb ofrbs[dbc c[df vfufkbst,bf ~10`^ ~11` lf ~12`&

(10) John talks about a unicorn. (]jyb cfe,hj,c vfhnjhmbc itcf[t,`

(11) John wishes to find a unicorn and eat it.~]jyc cehc bgjdjc vfhnjhmf lf itzfvjc bub `

(12) Mary believes that John finds a unicorn and that he eats it.(vthbc c]thf^ hjv ]jyb bgjdbc vfhnjhmfc lf itzfvc vfc`

~13` John tries to find a unicorn and wishes to eat it.(]jyb wlbkj,c bgjdjc vfhnjhmf lf itzfvjc bub`

jvjybvbf^ hjvtkcfw xdty dfc[dfdt,s ~8`^ ~9`^ ~11` lf ~12` obyflflt,t,ib kbnthfnehfib wyj,bkbf hjujhw "de-dicto/de-re" jvjybvbf fy """cgtwbabrehb / fhfcgtwbabrehb" jvjybvbf&

tc ahfuvtynb itlut,f ‘fkbfy vfhnbdb obyflflt,t,bcfufy& hjujhbwff John runs. udfmdc cfvb rfntujhbf ~cjhnb`% sthvt,bc rfntujhbf T^ ufhlfedfkb pvyehb ahfpt,bc rfntujhbf IV lf obyflflt,t,bc rfntujhbf S. fhct,j,ty ‘bhbsflb ,fpbcehb ufvjcf[ekt,t,b ~utythfnjht,b` T lf IV rfntujhbt,bcfsdbc& T rfntujhbbc BT utythfnjht,bc cbvhfdkt itbwfdc PTQ ahfuvtynbc cfresfh cf[tkt,c& itvlujvib vfs lftvfnt,f cgtwbfkehb cf[tkb cfbkecnhfwbjl Bigboss. cbvhfdktt,b BT lf BI _V ufybcfpqdht,bfy fct%

2&1& B_T={ John, Bill, Mary, Bigboss}
2. 2. B_IV={ run, walk, talk, rise, change} .
2. 3. End

kjubrfib B_T-c tktvtynt,c ittcf,fvt,f e nbgbc rjycnfynt,b, Bigboss-bc ufhlf. byntycbjyfkeh kjubrfib e nbgbc rjycnfynt,c ijhbc xdty ufydfc[dfdt,s cfv cgtwbfkeh vfsufyc%

2& 3& { John, bill, mary} Ì CON_e
2. 3. end
C^A,i,g=F(C) ( i ) (CÎ CON_e)

2.4. vybidytkj,bc 1gjcnekfnb%
$ u ð [ u = a ] cflfw a Î { John, bill, mary}
2.4. end

2.5. ufycfpqdht,f& [ a / Z ] Æ fqybiyfdc .dtkf
sfdbceafkb Z -bc xfyfwdkt,fc a -sb F -ib&

2&6& stjhtvf l U [ F ] a = [ a / ] F cflfw a Î { John, bill,
mary}

2.7. I L ajhvekfc tojlt,f vjlfkehfl xfrtnbkb
se bub fhbc itvltub I L mdtfkut,hbc tktvtynb%
< [ { John, mary, bill} ] , ( VARt ) t Î T U , RÈ { RÙ , Rð } >

2.8. ufvfhnbdt,bc otcb

1& dsmdfs ZÎ VARt ₁, a Î MEt ₂ lf b Î MEt 2

2` Z fhff lf,vekb b -ib Ù , H , W fy ÿ cfpqdht,ib fy

Bigross fh itb’kt,f bsfhuvyjc hjujhw e nbgbc [bcnb rjycnfynf& xdty itudb’kbf bub dsfhuvyjs < s,e> nbgbc rjycnfynfib fylf e nbgbc hfbvt rjycnfynfib dsfhuvyjs lf itvltu vfc ufdertsjs bynthghtnfwbf fhf[bcnfl& xdty fdbhxtds gbhdtk upfc&

2&9& bigboss Î CON< _{s, e>}

2.9. end.

bigboss rjycnfynbc bynthghtnfwbf fhbc aeymwbf byltmcblfy bylbdbleevib& fcts aeymwbfc tojlt,f bylbdblefkehb wyt,f ~rjywtgnb`& fvudfhfl Ù John fqybiyfdc bylbdblefkeh wyt,fc& Ù John-bs fqybiyekb bylbdblefkeh b wyt,f fhbc rjycnfynf aeymwbf^ vfiby hjwf bigboss fhff rjycnfynf aeymwbf&

dsmdfs ‘fksf ,fkfycb bwdkt,f lf ,ht;ytdb [lt,f bigboss htbufybc yfwdkfl& tc itb’kt,f ufvjbcf[jc obyflflt,bs ~14`&

~14` Bigboss changes&

~14` fphb fh bmyt,f cojhfl ofhvjlutybkb ajhvekbs^ hjvtkbw fv,j,c^ hjv change ghtlbrfnb ufvjb.tyt,f hfqfwf bylbdblevpt& itb’kt,f itbwdfkf f,cjkenehb ‘fkf htbufybcf ~itvwbhlf` fy itbwdfkf f,cjkenehb ‘fkf ,ht;ytdbcf ~ufbpfhlf`& fylf itb’kt,f jhbdtc ‘fkf itbwdfkf& obyflflt,f ~14` fv,j,c hjv wyt,f ¢ Bigboss¢ itbwdfkf bv fphbs hjv bub t[t,f c[df gbhjdyt,fc& fvudfhfl ~14`-bc fphb itb’kt,f b.jc ofhvjlutybkb - ajhvekbs^ hjvtkbw fv,j,c^ hjv ghtlbrfn changes-c flubkb fmdc bylbdblefkehb wyt,bcfsdbc^ hjvtkbw lfrfdibht,ekbf Bigboss-sfy& fctsb fyfkbpbcfsdbc change eylf b.jc < < s,e> , t > nbgbc& cbynfmccf lf ctvfynbrfc ijhbc /jvjvjhaekb lfvjrblt,ekt,bc ufvj tc ybiyfdc^ hjv .dtkf ufhlfedfkb pvyt,b < < s,e> , t> nbgbc eylf b.jc& fvudfhfl^

2&10& { run, walk, rise, change} Ì CON< < _{s,e> ,t>}
2.11. run ^¢ =run, walk¢ =walk, talk ¢ = talk, rise ^¢ =rise, change¢ =change

2.11. end

hjujhw wyj,bkbf ,eyt,hbdb tybc ‘bhbsflb cbynfmcehb fyfkbpb itb’kt,f fqbothjc rjyntmcnbcfufy sfdbceafkb uhfvfnbrbs ~CFG`& rjyntmcnbcfufy sfdbceafkb uhfvfnbrfsf itvlujv ufypjufljt,fc ofhvjflutyc ufycfpqdhek ahfpbfyb uhfvfnbrt,b& fcts uhfvfnbrfib fhfnthvbyfkeh cbv,jkjl itb’kt,f fdbqjs bctsb uhfvfnbrekb rfntujhია^ hjujhbwff obyflflt,f^ mdtvlt,fhbc ]ueab^ pvybc ]ueab^ lfvfnt,bc ]ueab lf c[df& itudb’kbf ufydvfhnjs^ hjv obyflflt,f itlut,f mdtvlt,fhbc ]ueabcfufy^ pvybc ]ueabcfufy lf thsb fy jhb lfvfnt,bc ]ueabcfufy& se xdty ufdfuh’tkt,s sdbstekb ]ueabc ufyvfhnt,fc lfdbyf[fds^ hjv mdtvlt,fhbc ]ueab lf lfvfnt,bc ]ueat,b sfdbfysb pjuflb fqyfuj,bs fh ufyc[dfdlt,bfy thsbvtjhtcfufy& fvbnjv vfssdbc itb’kt,f itvjdbqjs thsb cfthsj cf[tkb- cf[tkbc ]ueab lf bub ufydvfhnjs& vtjhtc v[hbd obyflflt,fib hfvltyb cf[tkbc ]ueabf lfvjrblt,ekbf pvybc ]ueapt& fvbnjv vbpfyitojybkbf obyflflt,bc ufyvfhnt,f lfderfdibhjs pvybc ]ueabc ufyvfhnt,fc lf pvybc ]ueabc vb[tldbs itvjdbnfyjs cf[tksf ]ueat,b obyflflt,fib lf tc ghjwtcb ufdfuh’tkjs vfyfv cfyfv fh lfdfks bcts rfntujhbt,fvlt hjujhbwff vtn.dtkt,bc yfobkt,b& vfufkbsfl fhct,bsb cf[tkt,b^ ptlcfhsfdt,b^ rfdibht,b^ pvybcptlt,b lf c[df& vfsb ufyvfhnt,f itb’kt,f vfsib itvfdfkb tktvtynt,bc ~cbn.dt,bc` xfvjsdkbs^ hjvkt,bw itvlujv ufyvfhnt,fc fh tmdtvlt,fht,bfy& vfs tojlt,fs nthvbyfkehb cbv,jkjt,b& .jdtkb ufycfvfhnfdb uhfvfnbrekb rfntujhbf fdqybiyjs hfbvt cbv,jkjsb& vfufkbsfl obyflflt,f - S-bs^ cf[tkbc ]ueab - P-sb lf pvybc ]ueab - VP-sb& vfiby otcb S® VP fqybiyfdc hjv obyflflt,f fhbc pvybc ]ueab^ [jkj otcb VP® np& vp1& nP ~1`

fqybiyfdc^ hjv pvybc ]ueab itlut,f ce,btmnbc ]ueabcfufy^ jhflubkbfyb ghtlbrfnbc lf gbhlfgbhb j,btmnbc ]ueabcfufy cbqhvbctek ljytpt^ [jkj ptlfgbhek ljytpt ufvjcf[ekbf cf[tkbc jhb ]ueabs lf pvybc ]ueabs^ hjvtksfw uffxybfs sfdbffysb lfvf[fcbfst,tkb ajhvfkehb ybiyt,b^ hjvkt,bw ufycfpqdhfdty uhfvfnbrekfl cojhfl itlutybk obyflflt,fc^ [jkj cbqhvbctek ljytpt ]ueat,b eylf b.dyty thsbvtjhtcsfy sfdct,flyb^ hjv vjudwtc fphj,hbdfl cojhb obyflflt,f& sfdct,flj,f ufybcfpqdht,f ]ueabc ctvfynbrehb ybiyt,bs lf ufvjbcf[t,f ctvfynbrehb otcbc cfiefkt,bs& fvudfhfl^ obyflflt,bc uhfvfnbrekfl cojhfl ufajhvt,f ufvjbcf[t,f cbynfmcehb otct,bs^ [jkj vbc fphj,hbd cbcojhtc ufycfpqdhfdc itcfn.dbcb ctvfynbrehb otcb& xdty fm fh itdt[t,bs ctvfynbreh otct,c lf lfdrvf.jabklt,bs v[jkjl cbynfmcehb otct,bc ufy[bkdbs& lfde,heylts ~1` obyflflt,fc& bvbcfsdbc^ hjv ufvjdcf[js cbynfmcehfl cojhb obyflflt,bc rth’j cf[tj,f^ lfdfpecnjs bub bv ybiyt,bs^ hjvkt,bw vjbs[jdt,f jhgbhbfyb ufhlfvfdfkb pvybc ajhvt,bcfsdbc& tc ybiyt,b rfhuflff wyj,bkb mfhsekb uhfvfnbrbc cf[tkv’qdfytkjt,ib& rjyrhtnekfl^ se pvybc ajhvf gbhdtkb cthbblfyff^ vfiby gbhdtkb cf[tkbc ]ueabc vsfdfhb cf[tkb eylf b.jc cf[tkj,bs ,heydfib ~ittcf,fvt,f ce,btmnbc ]ueac cbqhvbctek ljytpt`^ [jkj vtjht cf[tkbc ]ueabc vsfdfhb cf[tkb eylf b.jc vbwtvbs ,heydfib ~ittcf,fvt,f gbhlfgbhb j,btmnbc ]ueac cbqhvbctek ljytpt`& fyfkjubehfl xfvj.fkb,lt,f otct,b pvybc ajhvt,bcfsdbc vtjht lf vtcfvt cthbt,blfy& .dtkf itvs[dtdfib pvybc ajhvf eylf b.jc itsfy[vt,ekb hbw[dib ce,btmnbc ]ueasfy lf gbhib ce,btmnbcf lf j,btmnbc ]ueat,sfyfw& fvfdt lhjc eylf b.jc ufsdfkbcobyt,ekb^ hjv [ctyt,ekb ]ueat,b itb’kt,f b.dyty lfkfut,ekyb obyflflt,fib yt,bcvbthfl& f[kf dyf[js se hjujh itb’kt,f cbynfmcehb otct,b ufvjdcf[js DCG-ib lf itvltu hjujh uflfbotht,bfy bcbyb ghjkjupt&

S(X) ghtlbrfnbs fqdybiyjs bc afmnb^ hjv X fhbc cbf^ hjvkbc tktvtynt,bf hfbvt obyflflt,bc cbn.dt,b^ bubdt vbvltdhj,bs^ hjvkbsfw bcbyb ud[dlt,bfy obyflflt,fib^ t& b& P(X) fhbc thsfhuevtynbfyb ghtlbrfnb^ cflfw X fhbc cbf lf cbbc tktvtynt,b fhbfy cnhbmjyekb nbgbc rjycnfynt,b fy wdkflt,b`& fyfkjubehfl NP(X) ufvjcf[fdc cf[tkbc ]ueac lf VP(X) pvybc ]ueac& fvudfhfl^ ptvjs vjwtvekb otct,b itb’kt,f ufvjdcf[js /jhybc obyflflt,t,bs itvltuyfbhfl%

S(X)¬ VP(X).

VP(X)¬ append(X1,X4,X)& append (X2,X3,X4,)& (2)

np| (X1)& VP1(X2)& np2(X3)&

fm append (X1,X2,X3) fqybiyfdc X3 cbbc uf[ktxfc X1 lf X2 cbt,fl^ cflfw X1 lf X2 cbt,bc tktvtynsf rjyrfntyfwbf bubdtf hfw X3-bc tktvtynsf rjyrfntyfwbf& ptvjs vjwtvekb ~2` obyflflt,t,b xdty itudb’kbf uflfdothjs eahj vj[th[t,ekb cf[bs& fvbcfsdbc^ hfbvt X cbf xdty itudb’kbf ofhvjdblubyjs jh cbfl Y lf Z, cflfw X fhbc Y lf Z-bc rjyrfntyfwbf& rth’jl^ Z itb’kt,f b.jc wfhbtkb cbf^ hjvtkbw fqdybiyjs nil-bs& fvudfhfl^ S(X) ghtlbrfnb itb’kt,f itdwdfkjs f[fkb ghtlbrfnbs S(Y,Z), ptvjs vbqt,ekb itsfy[vt,bc ufsdfkbcobyt,bs& fvbc itvltu^ ~2` obyflflt,t,b uflfbotht,bfy fct%

S(X,Z)¬ VP(X,Z).

VP(X,V)¬ nP1(X,Y)& VP1(Y,Z)& nP2(Z,V). (3)

¬ S~gtnht^ fityt,c^ f[fk^ cf[kc^ nil, nil)

S- - > VP.

VP- - > nP1 : VP1 :nP2. (4)

~4`-ib S, np, np1 lf np2 fhbfy fhfnthvbyfkehb cbv,jkjt,b lf ofhvjflutyty ~3`-ib vjwtvekb ghtlbrfnt,bc itvjrkt,ek xfothfc& f[kfl itvjnfybkb jgthfnjht,bcfsdbc eylf lflubyltc vfsb ghbjhbntnt,b& w[flbf %-c eylf /mjyltc eahj vfqfkb ghbjhbntnb dblht - - > -c& IBM ghjkjuib jgthfnjhbc ghbjhbntnb vjbwtvf xfityt,ekb ghtlbrfnbs OP. vfu& OP("- - > ² , rl, 20), cflfw rl fqybiyfdc jh jgthfylbfy vfh]dybd fcjwbfnbeh jgthfnjhc& fhfnthvbyfkt,b ufycfpqdhfdty cbn.dt,bc cbfsf rkfct,c^ [jkj nthvbyfkt,b ufycfpqdhfdty wfkrtek cbn.dt,c& nthvbyfkt,b ufvjbcf[t,bfy + T ajhvbs^ cflfw + fhbc ghtabmcekb jgthfnjhb lf eylf /mjyltc c[df jgthfnjht,pt eahj vfqfkb ghbjhbntnb& ptvjs vbqt,ekb itsfy[vt,t,bs f[kf itdflubyjs vfhnbdb uhfvfnbrf^ hjvtkbw ufvjlut,f ² gtnht fityt,c f[fk cf[kc² -bc vcufdcb obyflflt,t,bc ufvjwyj,bcfsdbc%

s - - > p

VP - - > np1:vp1:np2.

vp1- - > v

np1- - > gtnht

v - - > + fityt,c&

N - - > +cf[kc&

ad - - > + f[fk&

tc uhfvfnbrf xdty itudb’kbf bjkfl uflfdb.dfyjs /jhybc obyflflt,t,ib se ufdb[ctyt,s^ hjv .jdtkb fhfnthvbyfkb nt uflfb.dfyt,f jhflubkbfy ghtlbrfnib nt(x,y) lf % jgthfnjhc itdwdkbs & -bs& + t, cflfw t fhbc nthvbyfkehb cbv,jkj^ eylf uflfdb.dfyjs gbhj,fib X=t, y otcib vbcb gjpbwbbc ufsdfkbcobyt,bs& vfufkbsfl& otcb

vp- - > np : vp1 : + f[fk % n, uflfb.dfyt,f obyflflt,fib

vp(x,v)¬ np(x,y)& vp1(y,z)& z= f[fk&u& n(u,v)

itcf’kt,tkbf fv otcbc itvlujvb ufvfhnbdt,f se z-c itdwdkbs vbcb vybidytkj,bs%

vp(x,v)¬ np(x,y)& vp1(y,f[fk&u)& n (u,v).

fctdt otcb n- - > + cf[kc uflfb.dfyt,f obyflflt,fib

n(x,y)¬ x= cf[kc& y.

[jkj X-bc ufvjhbw[dbs vbbqt,f

n(cf[kc&y,y).

s(x,y)¬ vp(x,y).

np1(gtnht&x,x).

v(fityt,c&x,x).

n(cf[kc&x,x).

ad(f[fk&x,x).

vbqt,ekb ghjkju ghjuhfvf itb’kt,f ufvj.tyt,ek bmytc hjujhw ~5` uhfvfnbrbs ufycfpqdhekb obyflflt,t,bc ufvjcfwyj,fl^ fctdt ~5`-bs ufycf[qdhekb obyflflt,t,bc utythbht,bcfsdbc& se ~6` ghjuhfvfc vbdwtvs vbpfyc¬ s(x, nil)& write (x) & fail. gfce[fl vbdbqt,s .dtkf obyflflt,fc ufycfpqdhekc ~5` uhfvfnbrbs^ [jkj se vbdwtvs vbpfyc

¬ S( gtnht& fityt,c& f[fk& cf[kc^ nil).

vjudwtvc lflt,bs gfce[c^ hfw ybiyfdc hjv ² gtnht fityt,c f[fk cf[kc² obyflflt,f tresdybc ~5` uhfvfnbrbs ufycfpqdhek tyfc& hjujhw fldbkb itcfvxytdbf fctsb uhfvfnbrf ghfmnbrekfl edfhubcbf vbcb itvlujvb ufafhsjt,bc ufhtit& gbhdtk hbuib ‘fkpt vje[th[t,tkbf ghfmnbrekb htfkbpfwbbc sdfkcfphbcbs mfhsekb tybc cbn.dbc ajhvt,bc nthvbyfkeh cbv,jkjt,fl ufvjw[flt,f^ hfw bvfc ybiyfdc hjv cbn.dfsf .dtkf ajhvt,b eylf itdbnfyjs rjvgbenthek ktmcbrjyib& fvbnjv^ fv tnfgpt itb’kt,f dbuekbc[vjs^ hjv .jdtkb cbn.df itb’kt,f lf[fcbfst,ek bmytc vbcb ewdktkb yfobkbs ~ktmcbrehb vybidytkj,bs` lf bv vjhajkjubehb rfntujhbt,bs^ hjvkt,bw fqothty chekfl fv cbn.dfc& xdty dbuekbc[vt,s hjv cbn.dbc ajhvf itwdkbkbf vbcb ewdktkb yfobkbs lf vjhajkjubehb rfntujhbt,bs^ hjvkt,bw fv cbn.dfc fqothty& fvbcfsdbc itvjdbnfys fm xdty cfsfyflj ghtlbrfnt,c^ hjvkt,cfw fhuevtynt,fl tmyt,fs cfzbhj vjhajkjubehb rfntujhbt,b lf fctdt c[df byajhvfwbfw& vfufkbsfl^ fhct,bsb cf[tkt,bcfsdbc itb’kt,f itvjdbnfyjs ghtlbrfnb fhc-cf[^ vfiby bvbcfsdbc^ hjv vbdesbsjs cbn.dbc ajhvf cf[kc cfzbhjf fhc-cf[ ghtlbrfnc /mjyltc fhuevtynt,b^ hjvkt,bw udbxdtyt,ty ,heydfc^ hbw[dc lf cbn.dbc ewdktk yfobkc& rth’jl se lfdoths fhc-cf[ ~cf[k^ vbw^ v[ `^ cflfw gbhdtkb fhuevtynb vbesbst,c cbn.dbc ewdktk yfobkc^ vtjht fhuevtynb ,heydfc lf vtcfvt fhuevtynb hbw[dc lf xfyfotht,b% cf[k^ vbw lf v[ fhbfy fhuevtynt,bc vybidytkj,t,b& cf[k ofhvjflutyc cbn.dbc ² cf[kc² ewdktk yfobkc^ [jkj vbw lf v[ ofhvjfutyty vbwtvbsb ,heydbcf lf v[jkj,bsb hbw[dc fqybidyt,c itcf,fvbcfl& hjujhw vfufkbsblfy xfyc^ ghtlbrfnbc lfcf[fcbfst,kfl fhff cfrvfhbcb vbcb cf[tkbcf lf fhuevtynt,bc hfjltyj,bcf lf hbubc wjlyf^ fctdt cfzbhjf sdbstekb fhuevtynbc nbgbc wjlyf fye lfdf[fcbfsjs sdbstekb fhuevtynbcfsdbc vbcb vybidytkj,fsf cbvhfdkt& vj.dfybk vfufkbsib ghtlbrfnc fhc-cf[ fmdc cfvb fhuevtynb^ hjvtkbw cfrvfhbcb b.j vjwtvekb sthvbc ² cf[kc² lfcf[fcbfst,kfl^ vfuhfv tc bvfc fh ybiyfdc^ hjv cfpjufljl fhct,bs cf[tksf lfcf[fcbfst,kfl cfrvfhbcb bmyt,f cfvb fhuevtynb& fhuevtynsf hfjltyj,f lfvjrblt,ekbf bvfpt^ se hfc dbcf[fds vbpyfl fv ghtlbrfnbc itvjnfybs& se xdty dbcf[fds vbpyfl lfdf[fcbfsjs .dtkf fhct,bsb cf[tkt,b vjhajkjubeh ljytpt^ vfiby fhuevtynt,bc hfjltyj,f bmyt,f dsmdfs m&^ [jkj se fctdt dbuekbc[vt,s^ hjv tc ghtlbrfnb itbwfdltc byajhvfwbfc fhct,bs cf[tksf lfcf[fcbfst,kfl ctvfynbreh ljytptw^ vfiby fhuevtynt,bc hfjltyj,f bmyt,f eahj vtnb& se tc ghtlbrfnb udzbhlt,f hjujhw cfo.bcb byajhvfwbf fhct,bsb cf[tkbc vjhajkjubehb rfntujhbt,bc lfcflutyfl^ vfiby vfc eylf /mjyltc fhuevtynt,b^ cbn.dbc ae’bcfsdbc^ ,heyt,bc nbgbcfsdbc lf c[df bcts- byajhvfwbbcfsdbc^ hjvtkbw xdtekt,hbd vjbwtvf vfymfyehb sfhuvybc rjvgbenthek ktmcbrjyt,ib fhct,bsb cf[tkbc ae’tt,bcfsdbc& fvudfhfl^ nthvbyfkehb cbv,jkjt,b itbwdkt,f ghtlbrfnt,bs^ hjvkt,bw bqt,ty vybidytkj,t,c sfdbfysb fhuevtynt,bcfsdbc wjlybc ,fpblfy& t&b& fctsb ghtlbrfnt,b eylf b.jc ufycfpqdhekb wjlybc ,fpfib& fctsb ghtlbrfnt,bc wjlybc ,fpfib itnfyf [lt,f eahj lf,fkb ljybc fyfkbpbc lhjc& vfufkbsfl^ cbynfmcehb fyfkbpbcfsdbc eahj lf,fkb ljybc fyfkbpb bmyt,f vjhajkjubehb fyfkbpb& ufhlf fvbcf^ bvbcfsdbc^ hjv otct,ib vbdesbsjs ]ueat,c ijhbc fhct,ekb vjs[jdyt,bc lfwdf^ fhfnthvbyfkehb cbv,jkjt,bc itcf,fvbcb ghtlbrfnt,bcfsdbc eylf itvjdbnfyjs rbltd lfvfnt,bsb fhuevtynt,b& vfufkbsfl^ fhct,bsb cf[tkbc ]ueacf lf pvybc ]ueac ijhbc hbw[dib itsfy[vt,bcfsdbc lf c[df& fctsyfbhfl ufafhsjt,ekb uhfvfnbrf erdt ufvjlut,f bvbcfsdbc^ hjv lfdflubyjs hfbvt obyflflt,f fhbc se fhf cbynfmcehfl cojhfl itlutybkb& bvbcfsdbc^ hjv fctsvf uhfvfnbrfv vjudwtc fuhtsdt vjwtvekb obyflflt,bc cbynfmcehb cnhemnehf^ cfzbhjf .jdtk fhfnthvbyfkeh cbv,jkjc itcf,fvbc ghtlbrfnc lfdevfnjs f[fkb fhuevtynb^ hjvtkbw bmyt,f cbf lf lfcfidt,bf^ hjv fv cbbc tktvtynt,b b.jc rdkfd cbf lf f& i&

2& thstekt,b^ hjvkt,bw ufvjb.tyt,bfy fyfkbpbcfc fhbfy lfkfut,ekyb itcfcdktk cnhbmjyib vfsb it[dtlhbc hbubc vb[tldbs^ vfiby hjwf utythfwbbc lhjc thstekt,b itbwfdty byajhvfwbfc bvbc itcf[t,^ se hjvtk cnhbmjyt,ib itb’kt,f itud[dlyty bcbyb& fmtlfy ufvjvlbyfht itb’kt,f lfdfcrdyfs^ hjv fyfkbpb fhbc utythfwbbc eahj itpqelekb cf[tj,f^ hflufy fyfkbpbc lhjc wyj,bkbf hjvtkbf fcfut,b cnhbmjyb ~b[& Kay, Martin. Algorithm Schemata and Data Structures in Sintactic Processing. Report CSL-8012, Palo Alto, CA: XEROX PARC). fvbnjv^ fut,ekbf thsbfyb fkujhbsvb^ hjujhw utythfwbbcfsdbc fctdt fyfkbpbcfsdbc^ cflfw ufyc[dfdt,f sfdc bxtyc v[jkjl fkujhbsvbc bybwbfkbpfwbbc afpfib& fkujhbsvb ufyfc[dfdt,c fmnbeh lf gfcbeh thstekt,c& hfbvt otcb fhbc ufvj.tyt,ekb hfbvt thstekpt^ se thstekbc rfntujhbf erfdibhlt,f otcbc vfh]dtyf v[fhbc gbhdtk rfntujhbfc vfiby f[fkb thstekb^ hjvkbc lf,jkjt,f fhbc otcbc vfh]dtyf v[fhbc lfhxtybkb yfobkb& se lfhxtybkb yfobkb fhff wfhbtkb^ vfiby thstekc tojlt,f fmnbehb thstekb lf vfc ite’kbf vbethsltc hfbvt gfcbeh thstekc^ hjvkbc rfntujhbf erfdibhlt,f lfhxtybkb yfobkbc .dtkfpt vfhw[tyf tktvtynbc rfntujhbfc& hfbvt thstekb fhbc < Span, String, Category, Remainder> .

Span fhbc o.dbkb < lfcfo.bcb ‘bhb^ ,jkj ‘bhb> &

String fhbc cbn.dt,bc cbf&

Category fhbc uhfvfnbrbc hfbvt fhfnthvbyfkehb cbv,jkj&

Remander fhbc rfntujhbt,bc cbf& se cbf wfhbtkbf vfiby thstekc tojlt,f gfcbehb ~lfchekt,ekb`^ obyffqvltu itvs[dtdfib bub fhbc fmnbehb ~lfechekt,tkb`&thstekt,b fhbfy fmnbeht,b fy lfrblt,ekt,b& fmnbeh thsteksf cbvhfdktc tojlt,f w[hbkb^ [jkj lfrblt,ek thsteksf cbvhfdktc-ybveib& lfrblt,ek thstekt,c fmds ghbjhbntnt,b lf bcbyb tvfnt,bfy w[hbkc vfsb ghbjhbntnt,bc rkt,bc vb[tldbs& hjwf lfrblt,ekb thstekb tvfnt,f w[hbkc bub [lt,f fmnbehb lf f[fkb lfrblt,ekb thstekt,b bmvyt,bfy hfbvt otcbc ufvj.tyt,bs thstekpt fy thsteksf rjv,bybht,bs^ hjwf thsthsb fmnbehbf lf vtjht gfcbehb& fctsb fkujhbsvb cfiefkt,fc b’ktdf ufvjdb.tyjs c[dflfc[df ufhxtdbc cnhfntubt,b&

[tsf itthst,bc uhfvfnbrf (Tree-Adjoining Grammar) ufvbpyekbf cnhbmjysf utythfwbbc cbcntvbcfsdbc^ eahj pecnfl^ bv cnhemneht,bc utythfwbbcfsdbc^ hjvkt,bw ofhvjlutybkb fhbfy [tt,bc cfiefkt,bs& bvbcfsdbc^ hjv fdqothjs [tt,bc ufvj.dfyf j,btmneh tyfpt^ cfzbhjf tc [tt,b ufvjdb.dfyjs j,btmnehb tybc [tt,bcfufy& fctsb ufvj.dfyt,b cfbynthtcjf^ hjujhw cbynfmcehb - fctdt ctvfynbrehb sdfkcfphbcbs& TAG itvjnfybkbf E. Joshi-bc vbth 1975 otkc ~[ Joshi 1975] ) lf cf,jkjj chekb dfhbfynb fqothbkbf Joshi-bc vbth 1991 o& ~[ Joshi 1991] ). [tsf itthst,bc tyf ~TAG) tresdybc rjyntmcnpt lfvjrblt,ek tyt,c^ eahj pecnfl^ iefktleh rjyntmcnbc vuh’yj,bfht tyfsf rkfcc&

[tsf itthst,bc uhfvfnbrf tojlt,f [estekc ~å , N , I , A , S), cflfw%

~2` N fhbc fhfnthvbyfkehb cbv,jkjt,bc cfchekb cbvhfdkt*

~3` S fhbc ufvj.jabkb fhfnthvbyfkehb cbv,jkj^ SÎ N;

(4 ) I fhbc cfchekb [tt,bc cbvhfdkt^ hjvtkcfw tojlt,f cfo.bcb [tt,bc cbvhfdkt&

~5` A fhbc cfchekb [tt,bc cfchekb cbvhfdkt ^ hjvtkcfw tojlt,f lfv[vfht [tsf cbvhfdkt&

[bc ibuf rdfy’t,b vjybiyekbf fhfnthvbyfkehb cbv,jkjt,bs^ hjvtksfw fqdybiyfds lblb kfsbyehb fcjt,bs& [jkj [bc ajskt,b vjybiyekbf nthvbyfkehb cbv,jkjt,bs fy fhfnthvbyfkehb cbv,jkjt,bs& nthvbyfkeh cbv,jkjt,c fqdybiyfds gfnfhf kfsbyehb fcjt,bs& [bc ajsjkb^ hjvtkbw voybiyekbf fhfnthvbyfkehb cbv,jkjsb vbothbkb fmdc cbv,jkj ¯ ^ hjvtkbw fqybiyfdc^ hjv tc rdfy’b ufyresdybkbf xfcvbcfsdbc& fhct,j,c v[jkjl thsb rdfy’b^ hjvtkbw vjybiyekbf bubdt cbv,jkjsb^ hfw [bc ‘bhb lf fv rdfy’c tojlt,f rdfkb lf bub lfvfnt,bs vjybiyekbf cbv,jkjsb * & ktmcbrfkbpt,ek TAG-ib .dtkfpt vwbht thsb vfbyw nthvbyfkehb cbv,jkj ~rdfkb` eylf b.jc cfo.bc fy lfv[vfht [tib& [tc fqt,ekc { I È A } -lfy tojlt,f tktvtynfhekb [t& fcts [tc deojlt,s C nbgbc tktvtynfkeh [tc se vbcb ‘bhb vjybiyekbf C -bs&

[t^ hjvtkbw itlutybkbf jhb [bc rjvgjpbwbbs tojlt,f ufvj.dfybkb [t& TAG b.tyt,c itthst,bcf lf xfcvbc rjvgjpbwbeh jgthfwbt,c& itthst,bc jgthfwbf

b lfv[vfht [bcf lf yt,bcvbthb a [bcfufy fut,c f[fk g [tc& dsmdfs n fhbc a -c fhf xfcvbsb rdfy’b vjybiyekb C -bsf lf b -c ‘bhb vjybiyekbf C -bs& g ^ hjvtkbw vbbqt,f b -c a -c n-eh rdfy’sfy itthst,bs lf ufybcfpqdht,f itvltuyfbhfl%

1& n-bs ufycfpqdhekb mdt[t^ deojljs vfc d ^ xfvjtzht,f a -c&

2& b -lfv[vfht [t vbethslt,f n rdfy’ib a -c lf b -c ‘bhb ufbubdlt,f n rdfy’sfy&

xfcvbc jgthfwbf vjmvtlt,c v[jkjl [bc ajskt,pt^ hjvkt,bw vjybiyekb fhbfy fhfnthvbyfkehb cbv,jkjt,bs lf ¯ -bs& rdfy’b^ cflfw [lt,f xfcvf itbwdkt,f xfcfcvtkb [bs& itcf’kt,tkbf itvjdbnfyjs itpqeldt,b itthst,bc jgthfwbfpt& vfufkbsfl^ itcf’kt,tkbf vjwtvek rdfy’ib ufydcfpqdhjs T lfv[vfht [tt,bc cbvhfdkt T Í A , hjvkbc tktvtnb itb’kt,f itdfthsjs vjwtvek rdfy’ib& fctsb itpqeldf fqdybiyjs SA(T) –sb& fcts itvs[dtdfib itthst,f fhff cfdfklt,ekj& NA-sb fqdybiyjs SA(T), cflfw T wfhbtkb cbvhfdktf& t& b& vjwtvek rdfy’ib itthst,f frh’fkekbf& OA(T)-sb fqdybiyjs fewbkt,tkb itthst,f^ hjwf vjwtvek rdfy’ib fewbkt,kfl eylf vj[ltc itthst,f hjvtkbvt tÎ T-sb& se fhfdbsfhb itpqeldt,b fhff itthst,fpt lf fhf udfmdc xfcvbc rdfy’t,b tktvtynfhek [tt,ib fcts TAG-c tojlt,f [tsf itthst,bc vrfwhb uhfvfnbrf& ufvj.dfyf uhfvfnbrfib ufycfpqdhekbf bctsb [bc cfiefkt,bs^ hjvtkbw udbxdtyt,c se hjujh vbbqt,f cf,jkjj [t cfo.bcb [bcfufy itthst,bcf lf xfcvbc jgthfwbt,bc ufvj.tyt,bs* uhfvfnbrfc tojlt,f ktmcbrfkbpt,ekb se bub itlut,f%

2& hfbvt jgthfwbbcfufy fy jgthfwbt,bcfufy cnhemnehfsf rjvgjpbwbbcfsdbc vjbs[jdt,f^ hjv rdfkb fh eylf b.jc wfhbtkb ktmcbrehb thstekb& ktmcbrjyb itlut,f cnhemnehfsf cfchekb cbvhfdkbcfufy^ cflfw .jdtkb cnhemnehf lfrfdibht,ekbf hfbvt rdfksfy& ktmcbrjybs ufycfpqdhek cnhemneht,c tojlt,fs tktvtynfhekb cnhemneht,b^ [jkj cnhemneht,b hjvkt,bw vbbqt,bfy cnhemnehfsf rjv,bybht,bs tojlt,fs ufvj.dfybkb cnhemneht,b& vjbs[jdt,f^ hjv cnhemnehf b.jc cfchekb pjvbc lf jgthfwbfc uflf/.fdltc cnhemnehfsf cfchekb cbvhfdkt cfchekb hfjltyj,bc vmjyt cnhemneht,ib& cnhemnehf fhbc ktmcbrfkbpt,ekb se fhct,j,c thsb vfbyw ktmcbrehb thstekb ~fhfwfhbtkb`^ hjvtkbw ud[dlt,f vfcib& uhfvfnbrf^ hjvtkbw itlut,f ktmcbrfkbpt,ekb cnhemneht,bcfufy fhbc ktmcbrfkbpt,ekb& itcf’kt,tkbf rjyntmcnbcfufy sfdbceafkb uhfvfnbrt,bc ktmcbrfkbpfwbf TAG-t,bs& uhfvfnbrekb ajhvfkbpvt,bc ktmcbrfkbpfwbf cfbynthtcjf hjujhw kbyudbcnehb^ fctdt ajhvfkehb sdfkcfphbcbs& se vbdbqt,s sdfkcfphbcc^ hjv fh b.jc chekfl ufywfkrtdt,ekb sfdbfysb ktmcbrehb htfkbpfwbbcfufy^ vfiby .jdtkb tktvtynfhekb cnhemnehf cbcntvehfl lfrfdibht,ekbf sfdbc ktmcbreh rdfksfy ktmcbrfkbpt,ekb vblujvbc lhjc& tc cnhemneht,b fpecnt,ty ufafhsjt,ek fhtt,c^ hjvkt,ptlfw itb’kt,f lfdfljs itpqeldt,b& rjyntmcnbcfufy sfdbceafkb otct,bc ktmcbrfkbpfwbbc ghjwtcb udfb’ekt,c xdty ufvjdb.tyjs xfcvbcf lf itthst,bc jgthfwbt,b cnhemnehfsf rjv,bybht,bcfsdbc^ tc rb [lbc ajhvfkbpvc bctsc^ hjvtkbw [dlt,f rjyntmcnbc vuh’yj,bfht tyfsf rkfcib& xfcvbcf lf itthst,bc jgthfwbt,b fbjkt,ty rjyntmcnbcfufy sfdbceafkb tyt,bc ktmcbrfkbpfwbfc& fctsb ajhvfkbpvb rb udf’ktdc ktmcbrfkbpt,ek [tsf itthst,bc tyfc& TAG^ sfdbc v[hbd^ xfrtnbkbf ktmcbrfkbpfwbbc vbvfhs&

a& uflfflubkjc cntrbc vbvsbst,tkb thsb cbv,jkjsb cntrblfy ofrbs[ekb cbv,jkjc vfh]dybd fy vfhw[ybd&

b. se bub rbs[ekj,c cntrbc sfdib vjsfdct,ek cbv,jkjc^ vfiby vfc ite’kbf xfothjc cntrbc sfdib cbv,jkjt,b lf ofifkjc cntrbc sfdblfy ofrbs[ekb cbv,jkj& ajhvfkehfl A = ( K , å , Ë ^$,G , d , q₀,Z_0, F)

cntrbfyb fdnjvfnb itlut,f itvltub tktvtynt,bcfufy%

1& K fhbc vlujvfhtj,bc cfchekb fhfwfhbtkb cbvhfdkt*

3& Ï lf $ fhbfy cbv,jkjt,b^ hjvkt,bw fh tresdybfy å -c lf ud[dlt,bfy itcfcdktkb ]fzdbc sfdcf lf ,jkjib itcf,fvbcfl ^ hjvkt,bw ufvjb.tyt,bfy itcfcdktkb ]fzdbc sfdcf lf ,jkjc lfcfabmcbht,kfl*

5& Z₀ Î G lf ud[dlt,f cntrbc ,jkjib v[jkjl& bub ufvjb.tyt,f bvbc fqcfybiyfdfl^ hjv vbdfqobts cntrbc ‘bhc*

fhtf K C ( å È { Ë ^$} ` C G lf vybidytkj,fsf fhtf

{ - 1 , 0 , 1 } C K C { - 1 , 0 , 1 } C G * bctsb hjv .jdtkb q, a, lf Z-bcfsdbc%

a. se d ( q, a, z)=(d,q¢ , e,w) lf w¹ z, vfiby e = 0;

b. se d ( q,a,z₀)=(d, q¢ , e,y), vfiby y=z_ow,

wÎ G _* ;

7. q_{0Î K} lf tojlt,f cfo.bcb vlujvfhtj,f*

8& FÎ K lf tojlt,f cf,jkjj vlujvfhtj,fsf cbvhfdkt& cntrbfyb fdnjvfnbc itcfcdktk ]fzdb fhbc å * $-bc tktvtynb& cf,jkjj vlujvfhtj,t,b ufvjb.tyt,f bvbcfsdbc^ hjv ufvjdbnfyjs bc ]fzdt,b^ hjvkt,bw fv uhfvfnbrbs ufycfpqdhek tyfc tresdybfy& xfyfothb d (a, q,z,)=(d,q¢ ,e,z) ybiyfdc& hjv se cntrbfyb fdnjvfnb ~SA) bv.jat,f q vlujvfhtj,fib^ cntrbc sfdib fhbc Z lf itcfcdktk cnhbmjyblfy rbs[ekj,c a cbv,jkjc vfiby%

1& bub uflflbc q¢ vlujvfhtj,fib*

2& bub vj’hfj,c vfhw[ybd ~itcfcdktkb cnhbmjybc vbvfhs`^ se d= -1 fy vfh]dybd se d= 1 fy fh vj’hfj,c se d=0;

3. bub vj’hfj,c ~cntrbc vbvfhs` vfhw[ybd se e= -1 fy vfh]dybd se e=1 fy fh vj’hfj,c se e=0.

xfyfothb d ~q,a,z)=(d,q¢ , o,w) lf Z¹ W ybiyfd hjv se SA fhbc ~q,a,z) rjyabuehfwbfib^ vfiby

1& bub vj’hfj,c itcfcdktk cnhbmjypt d- vb[tldbs*

2& uflflbc q¢ vlujvfhtj,fib*

3& cntrib othc W-c Z-bc yfwdkfl&

6a gbhj,f rh’fkfdc cntrpt vjmvtlt,t,c^ hjwf e=0 lf 6b gbhj,f rh’fkfdc vfqfpbbc lfwfhbtkt,fc^ t&b& Z₀-bc ofikfc& cntrbfyb fdnjvfnbc vbvlbyfht vlujvfhtj,f ufybcfpqdht,f ofcfrbs[fdb cnhbmjybs^ vbvlbyfht q vlujvfhtj,bsf lf cntrbc ibusfdcbs^ t&b& SA fdnjvfnbc vlujvfhtj,f ~M` fhbc

K C Q(å È { e,$,a} ) * C ( G È { b} ) * cbvhfdkbc tktvtynb^ cflfw a fhbc itcfdfkb cnhbmjybc vbvlbyfht cbv,jkjc vbvsbst,tkb^ [jkj b fhbc cntrbc sfdbc vbvsbst,tkb& f[kf ufydcfpqdhjs | ¾ lfvjrblt,ekt,f SA fdnjvfnbcfsdbc& dsmdfs SA= ( K , å , Ï $, G ,d , q₀, Z_0,F), | ¾ lfvjrblt,ekt,f SA –c vlujvfhtj,t,c ijhbc ufybcfpqdht,f itvltuyfbhfl% se k,l³ 1, a₁,a₂ , ..., a_k tresdybc å È { Ï $} ; a_{k+1| ¾ ,} Z_1,...,Z_e tresdybc G , U tresdybc G * tresdybcG -c^ vfiby

1& se d ~q, a_i,Z_j)=(d,q¢ ,e,z_j), cflfw 1£ i £ k lf 1£ j£ l frvf.jabkt,c gbhj,t,c% i. d³ 0 se i=1; ii. e³ 0 se j=1lf iii. e£ 0 se j=l, vfiby ~ q,a₁...āa_i...a_k, z₁...Z_jb...Z_l)| ¾ (q¢ ,a₁...āa_i+d a_k+1, z₁ ...z_j+eb...z_l);

2& se d ~q, a_i, Z)= ( d,q¢ ,0,w) lf 1£ i£ k frvf.jabkt,c i gbhj,fc^ vfiby ~q,a₁...āa_i...a_k, yzb)| ¾ (q^’, a₁...ba_i+d...a_k, ywb).

fv lfvjrblt,ekt,bs xdty itudb’kbf fqdothjs SA fdnjvfnbc thsb yf,b]b& f[kf ufydb[bkjs fv lfvjrblt,ekt,bc nhfypbnekb lf htaktmcehb xfrtndf * %

~ q, xāy, w₁bw₂) | ¾ * ( q ¢ ,x¢ āy¢ ,w¢ ,bw ₂),¢ cflfw X,Y,X ^¢ lf y¢ ]fzdt,bf ~å È { Ï $} ) *-lfy lf W_1,W_2,W_1¢ ^,W_2¢ ]fzdt,bf G *-lfy& se K ³ 0 ^ f_i, g_i lf h_i, cflfw 0 £ i£ k bctsb^ hjv f₀=q, f_k=q¢ , g₀=xāy; g_k=x¢ by¢ , h₀=w₁bw₂,h_k=w¢ ₁bw¢ ₂, vfiby

~f_i,g_i,h_i) | ¾ (f_i+1, g_i+1,h_i+1), cflfw 0 £ i £ k.

dbn.dbs^ hjv SA fdnjvfnb eidt,c XÎ å * ]fzdc se

~q₀, āÎ x$,z₀b) | ¾ *(q,Ï x$ā,w,bw_2),

cflfw qÎ F lf W_1,W_{2Î G} *. SA fdnjvfnbc vbth lfidt,ekb .dtkf ]fzdsf cbvhfdkt fqdybiyjs L(SA)-sb lf bub fhbc tyf ufycfpqdhekb SA fdnjvfnbs& vfqfpbehb fdnjvfnbc fyfkjubehfl^ fmfw xdty itudb’kbf itvjdbnfyjs fhfltnthvbybcnekb SA fdnjvfnbc ufyvfhnt,f ~b[& Ginsburg...). SA fdnjvfnpt ufhrdtekb itpqeldt,bc lflt,bs vbbqt,f .dtkf fmfvlt ufy[bkekb fdnjvfnt,b& lfvjrblt,ekt,f c[dflfc[df fdnjvfnt,cf lf wyj,bk cbvhfdktt,c ijhbc vjrktl itb’kt,f ofhvjdflubyjs itvltub lbfuhfvbs

fv lbfuhfvfpt ufvj.tyt,ekbf itvltub fqybidyt,b% 1 → thsvbvfhsekt,bfyb^ 2 → jhvbvfhsekt,bfyb^ D   → ltnthvbybcnekb^ FA → cfchekb^ ltnthvbybcnekb fdnjvfnbc^ N → fhfltnthvbybcnekb^ NE → fhfofikflb^ RS → htrehcbekb cbvhfdktt,b^ P →  vfqfpbehb fdnjvfnb^ LBA → ohabdfllfrfdibht,ekb fdnjvfnb^ S  → cntrehb fdnjvfnb^ RF → htrehcbekfl uflfsdkflb cbvhfdktt,b& jhvfub [fpt,b udbxdtyt,ty cfreshbd yfobkc^ thsvfub [fpb udbxdtyt,c hjv bub ofhvjflutyc yfobkc lf cfreshbd yfobkc ofhvjflutyc se fhf fhff wyj,bkb& vfufkbsfl^ a═b ybiyfdc hjv bÌ a^ a ¾ b ybiyfdc bÍ a. wyj,bkbf ^hjv SA fdnjvfnbc vbth lfidt,ekb cbvhfdktt,b fhbfy htrehcbekb cbvhfdktt,b&

itvjdbnfyjs cntrbfyb cbvhfdktt,bc ufyvfhnt,f% hfbvt cntrbfyb cbcntvf fhbc cfvtekb G=(K,G , P), cflfw K lf G fhbfy cfchekb fhfwfhbtkb cbvhfdktt,b K Ç G = = Æ lf P fhbc itvltub cf[bc otct,bc cfchekb cbvhfdktt,b ~cflfw S lf S¢ tresdybc K-c lf A lf B tresdybc G -c`%

1& xfothf% QAs® QABs¢

2& itwdkf% QAs ® QBs¢

3& ofikf% QAs ® Qs¢

4& lfnjdt,f% Q₁AsQ_2® Q₁AsQ₂

5& vfhw[ybd uflfotdf% Q₁AsQ_2® Q₁s¢ AQ₂

6& vfh]dybd uflfotdf% Q₁AsBQ_2® Q₁ABs¢ Q₂

f[kf ufydcfpqdhjs se hjujh eylf ufvjdb.tyjs ptvjsf otct,b& Q,Q₁,Q_{2 Î ( K È G ) * .} dsmdfs G=(K,G , R ) fhbc cntrbfyb cbcntvf& se W,Y,Y¢ tresdybc ( K È G ) * lf Q₁YQ_2® Q₁Y¢ Q₂, vfiby doths WYÞ WY¢ . fyfkjubehfl^ se W,W¢ ,Y,Y¢ tresdybc ~ K È G ) * lf Q₁YQ_2® Q₁Y¢ Q₂, vfiby doths WYW¢ Þ WY¢ W¢ . se C lf Y tresdybc ( K È G ) * , vfiby C Þ * U ybiyfdc^ hjv fhct,j,c Z₀,...Zr [fzdt,b ( K È G ) * -lfy bctsb hjv Z₀

=X, Zr=Y, ZiÞ Zi+1 lf 0 £ i£ r. lfvjrblt,ekt,f Þ fhbc htaktmcehb lf nhfypbnekb& fctsb cbcntvbc ufvj.tyt,bs vnrbwlt,f obyf lbfuhfvfpt yfxdtyt,b vstkb hbub lt,ekt,t,bcf ~ b[& `& SA fdnjvfnbs lfidt,ekb cbvhfdktt,b fhbfy xfrtnbkb sfyfrdtsbc jgthfwbbc vbvfhs&

CAT 2 fhbc ufvbpyekb ,eyt,hbdb tybc rjvgbenthekb lfveifdt,bcfsdbc& bub itbwfdc bcts cfiefkt,t,c hjvtksf lf[vfht,bs uffldbkt,ekbf ,eyt,hbdb tybc cnhemneht,bc rjvgbenthpt ofhvjlutyf& gbhdtk hbuib bub ufvbpyekbf vfymfyehb sfhuvfybcfsdbc^ sevwf vbcb cfiefkt,bs itcf’kt,tkbf ,eyt,hbdb-tybc fyfkbpb^ wjlybc lfuhjdt,f lf vbcb ufvj.tyt,f c[dflfc[df vbpybcfsdbc& CAT2-c cfae’dkfl fmdc vblujvf^ hjvtkbw itveifdt,ekb b.j EUROTRA ghjtmnib rth’jl < C,A > , T-c cf[tkbs wyj,bkb vblujvf vfymfyehb sfhuvfybcflvb ~Arnold lf c[dt,b 1985^ 1986^ Arnold lf Tombe 1987). bub lfae’yt,ekbf rjycnhemnjht,bcf^ fnjvt,bcf lf nhfyckbfnjht,bc wyt,t,pt& rjycnhemnjht,b lf fnjvt,b mvybfy ofhvjlutybc hfbvt ljytc^ [jkj nhfyckbfnjht,b frfdibht,ty thsbvtjhtcsfy hfbvt jh ljytc& tyj,hbdb cnhemneht,b ofhvjblubyt,bfy [tt,bc cfiefkt,bs& vfc fmdc ufvfhnbdt,ekb cbynfmcb lf ctvfynbrf& rfhufl ufycfpqdhekbf^ hjvtkbw tv.fht,f sdbct,fsf kjubrfcf ~Johnson 1988) lf sdbct,fsf eybabrfwbbc ajhvfkbpvc ~Kasper 1987). CAT2-‘bhbsflb ufyc[dfdt,f c[df vcufdc ajhvfkbpvt,bcfufy fhbc bc ^ hjv bub b.tyt,c kbyudbcneh-cnhemneht,bc ofhvjcflutyflfw [tt,c^ vfiby hjltcfw sdbct,fsf cnhemneht,b ufvjb.tyt,f vfufkbsfl% LFG-ib ~Kaplan lf Bresnan 1982), FUG-ib ~Kay 1984) lf HPSG-ib (Pollard and Sag 1987). CAT2-bc c[df lfvf[fcbfst,tkb ybifybf ljytsf hjkt,b^ hjvkt,bw f[fcbfst,ty ofhvjlutybc ljytt,c& fvudfhfl^ KAT2-ib xdty udfmdc c[dflfc[df ofhvjlutybc ljytt,b^ hjvkt,bw lfrfdibht,ekb fhbfy thsbvtjhtcsfy nhfyckbfnjht,bs& ofhvjlutybc ljyt ufycfpqdhekbf utythfnjhbs&

hfbvt ,eyt,hbdb tybc uhfvfnbrf CAT2-ib ofhvjblubyt,f hjujhw otct,bc cbvhfdkt^ hjvtkbw lf]ueat,ekbf utythfnjht,fl lf nhfyckbfnjhfl& hfbvt utythfnjhb fhbc otct,bc cbvhfdkt^ hjvtkbw ufycfpqdhfdc ofhvjlutybc ljytc lf hfbvt nhfyckbfnjhb-fhbc otct,bc cbvhfdkt^ hjvtkbw frfdibht,c thsbvtjhtcsfy ofhvjlutybc jh ljytc& thsb utythfnjhb ufycfpqdhfdc cbynfmceh cnhemneht,c^ hjvtkcfw tojlt,f cbynfmcehb utythfnjhb lf vtjht utythfnjhb ufycfpqdhfdc htfkeh cnhemneht,c^ hjvtkcfw tojlt,f htfkehb utythfnjhb& fctdt fhct,j,ty vjhajkjubehb utythfnjhb lf ntmcnbc utythfnjhb& vjhajkjubehb utythfnjhb ufycfpqdhfdc vjhajkjubeh cnhemneht,c lf ntmcnbc utythfnjhb ufsdfkbcobyt,ekbf vhfdfk-obyflflt,bfyb cnhemneht,bcfsdbc& fvudfhfl fdfut,s hf cbynfmceh utythfnjhc lf thsc fy vtn htfkeh utythfnjht,c^ hjvtksfw lffrfdibht,ty nhfyckbfnjht,b^ itcf’kt,tkbf vjwtvekb tybcfsdbc itbmvyfc kbyudbcnehb cnhemneht,b rjvgbenthbc cfiefkt,bs& fctdt vtjht tybcfsdbc se ufdfrtst,s bubdtc lf vfs utythfnjht,c lfdfrfdibht,s nhfyckbfnjht,bs fvbs itcheklt,f thsb tybc kbyudbcnehb cnhemneht,bc uflf.dfyf vtjht tybc itcf,fvbc kbyudbcneh cnhemneht,ib& vfufkbsfl^ ufydcfpqdhjs byukbcehb tybc uhfvfnbrf^ hjvtkbw itlut,f CSEN cbynfmcehb utythfnjhbcfufy lf ISEN bynthatbcekb utythfnjhbcfufy lf bcbyb lfdfrfdibhjs nhfyckbfnjht,bs% CSEN® ISEN, hjvtkcfw uflf/.fdc cbynfmcehb cnhemneht,b CSEN-blfy htfkeh cnhemneht,ib ISEN-ib lf ISEN® CSEN, hjvtkbw fchekt,c it,heyt,ek vjmvtlt,fc& fctdt ufydcfpqdhjs mfhsekb tybc uhfvfnbrf CSKR lf ISKAR utythfnjht,bs lf nhfyckbfnjht,bs CSKAR® ISKAR lf ISKAR® CSKAR. lfdevfnjs vfs nhfyckbfnjht,b% ISEN® ISKAR lf ISKAR® ISEN, vfiby itudb’kbf xdty mfhsekb IS (bynthatbcekb cnhemneht,b` uflfdb.dfyjs byukbceh IS cnhemneht,ib lf gbhbmbs& kbyudbcneh cnhemneht,c^ hjvtkcfw utythfnjhb /mvybc tojlt,fs j,btmnt,b& rjyrhtnek j,btmnc fmdc [bc ajhvf^ hjvtkibw rdfy’t,b itbwfdty sdbct,t,bc cbvhfdktc& .jdtkb sdbct,f fhbc o.dbkb fnhb,enb lf vybidytkj,f& .jdtkb fnhb,enb fhbc eybrfkehb [bc rdfy’ib lf .jdtk fnhb,enc fmdc vybidytkj,f¾ fnjvehb rjycnfynf fy wdkflb fy sdbct,fsf cbvhfdkt& j,btmnt,bc utythbht,bcfsdbc CAT2 b.tyt,c eybabrfwbbc jgthfwbfc^ hjujhw [tt,bc fcfut,fl^ fctdt sdbct,fsf itcflutyfl& eybabrfwbf hfbvt j,btmnbcf [lt,f vfhw[yblfy vfh]dybd mdt[tt,bc ufsdfkbcobyt,bs& eybabrfwbfcsfy lfrfdibht,ekb vybidytkjdfyb wyt,ff itpqeldbc lfrvf.jabkt,f& itpqeldt,b^ hjvkt,bw fh rvf.jabklt,f vjwtvek vjvtynib^ [lt,f vbcb uflflt,f vfyfvlt^ cfyfv f[fkb byajhvfwbbc vbqt,f fhbc itcf’kt,tkb& itpqeldfsf nbgt,bf% lflt,bsb^ efh.jabsb^ lbpbeymwbehb^ fhct,j,bc lf gbhj,bsb itpqeldt,b&

{ cat=fhc^ lex=cf[kt,b^ lu=cf[kb^ arg={ per=3, num=vh} ^ wh=¢ - ¢ }

sdbct,bc vybidytkj,f itb’kt,f b.jc rjycnfynf^ wdkflb fy sdbct,fsf cbvhfdkt& sdbct,f itb’kt,f b.jc hsekb ~vfu& arg ) fy fnjvehb ~vfu&cat, lu lf c[df`& CAT2-bc rjycnfynt,bf PROLOG-bc rjycnfynt,b^ v[jkjl fh ufvjb.tyt,f yfvldbkb hbw[dt,b& sdbct,bc vybidytkj,f itb’kt,f b.jc wdkflb& wdkflb itb’kt,f lferfdibhltc rjycnfynfc fy sdbct,fsf cbvhfdktc eybabrfwbbs lf itvltu [lt,f bybwbfkbpt,ekb wdkflb& fctdt wdkflb itb’kt,f lferfdibhltc c[df wdkflc fcts itvs[dtdfib udfmdc lfrfdibht,ekb wdkflb& sdbct,fsf cbvhfdkbc fqothf ufvjcf[fdc itpqeldt,c j,btmnbc sdbct,t,pt&

lflt,bsb itpqeldt,b bctsb itpqeldt,bf^ hjvkt,bw vjbwtvf rjycnfynt,bs fy wdkflt,bs fy itlutybkb sdbct,bs^ hjvtkbw rdkfd itlut,f lflt,bsb itpqeldt,bs& efh.jabsb itpqeldt,b itbwfdty efh.jat,c& vfu & { perØ =3} . lbpbeymnehb itpqeldt,b fw[flt,ty^ hjv j,btmnbc sdbct,t,bc vybidytkj,f itb’kt,f b.jc ths-thsb hfvjltybvt fknthyfnbdt,blfy& fhct,j,bc itpqeldt,b vjbs[jdty^ hjv vjwtvekb itpqeldf eylf fhct,j,ltc j,btmnib obyffqvltu itvs[dtdfib bub ufybwlbc vfhw[c& fhct,j,bc itpqeldf fqbybiyt,f = = ybiybs& gbhj,bs itpqeldt,b fhbfy itpqeldt,b hfbvt sdbct,fsf cbvhfdktpt lf fhf hfbvt sdbct,bc vybidytkj,fpt& gbhj,bs itpqeldfc fmdc cf[t

fhct,j,c jhb sdbct,bc fqothbc vybidytkj,t,b CAT2-ib^ hjvtksfw fmds cgtwbfkehb lfybiyekt,f& thsb fhbc INDEX-eybrfkehb vstkb hbw[dt,bc utythbht,bcfsdbc lf vtjht fhbc NUM-bcfsdbc^ hjv vybidytkj,f b.jc hbw[dbsb& bcbyb itb’kt,f itud[dltc hjujhw vybidytkj,t,b yt,bcvbthb sdbct,bc fqothfib& jhbdtyb ofhvjflutyty itpqeldt,c vybidytkj,t,pt& $INDEX vybidytkj,f ufvjb.tyt,f fyfajhek vbsbst,fib byltmct,bc utythbht,bcfsdbc&

hfbvt utythfnjhb ufycfpqdhfdc j,btmnt,bc cbvhfdktc ofhvjlutybc hfbvt ljytpt& utythfnjht,b itbwfdty jhb nbgbc otct,c% b-otct,cf lf f-otct,c& b-otct,b ~fut,bc otct,b` fhbfy rjycnhemnjhsf cbvhfdkt^ hjvtkbw ufycfpqdhfdc cnhemnehek [tt,c lf f-otct,b ~sdbct,fsf otct,b` vjmvtlt,ty sdbct,t,pt [bc ibuybs^ fy fvfnt,ty f[fk sdbct,t,c fy fvjovt,ty erdt fhct,ek sdbct,t,c& hjwf xdty dmvybs hfbvt afbkc^ hjvtkbw itbwfdc hfbvt utythfnjhbc ufycfpqdhfc^ xdty dbo.t,s ufycfpqdht,fc rjvgbkfnjhbc lbhtmnbdbs @ level:

@ level (NAME /TYPE / ATTRIBUTE ).

tc lbhtmnbdf f’ktdc utythfnjhc cf[tkc^ ~NAME) ufycfpqdhfdc vbc nbgc ~TYPE) lf ghbdbkbubht,ek fnhb,ent,c vbcsdbc& ~ATTRIBUTE) cf[tkb itb’kt,f b.jc^ fnjvehb rjycnfynf& nbgb fhbc cbynfmcehb ~Syntactic) fy htkfwbehb (relational) lf fnhb,enb fhbc hfbvt fnjvehb rjycnfynf& vfufkbsfl

@ level (CSKAR / syntactic / cat ).

vjvltdyj bycnhemwbt,b f[fk @ level bycnhemwbfvlt tresdybfy fv utythfnjhc&

B-otct,b ufycfpqdhfdty rjycnhemnjht,cf lf fnjvt,c^ hjvkt,bw fqothty wfkrtek [tt,c& .jdtk b-otcc fmdc ajhvf%

NAME=ROOT.BODY.

cflfw cf[tkb ~NAME) fhbc fnjvehb rjycnfynf^ hjvtkbw fqybiyfdc otcc^ ‘bhb ( ROOT) fhbc hfbvt sdbct,fsf cbvhfdkbc fqothf^ hjvtkbw fqothc [bc ‘bhc lf nfyb ~BODY) fhbc eiefkj isfvjvfdkt,bc sdbct,fsf cbvhfdktt,bc fqotht,b& fnjvehbrjycnhemnjhbc itvs[dtdfib nfyb fhbc wfhbtkb cbf& b-otct,b bo.t,f lbhtmnbdbs

@ rule (b), fv lbhtmnbdbc vjvltdyj bycnhemwbt,b itvltu @ rule fy @ level lbhtmnbdt,fvlt ufyb[bkt,bfy hjujhw b-otct,b&

cfe,hbc ofhvjlutybc stjhbf (DRT) lfrfdibht,ekbf ,eyt,hbdb tybc ntmcnbc ctvfynbrehb cnhemnehbc ofhvjlutyfcsfy& eahj pecnfl^ bub wlbkj,c ntmcnbc itvflutytkb vbvltdhj,bsb obyflflt,t,bcfsdbc ofhvjudblubyjc vfsb cbynfmcehb^ ctvfynbrehb lf kjubrehb cnhemnehf lf bc rfdibht,b^ hjvkt,bsfw bcbyb lfrfdibht,ekb fhbfy thsbvtjhtcsfy& fvfcsfyfdt tc ofhvjlutyf eylf b.jc ufypjuflt,ekb t& b& bctsb^ hjvtkbw ufvjlut,jlf fhf vfhnj vjwtvekb ntmcnbc obyflflt,t,bcfsdbc fhfvtl fuhtsdt ,tdhb c[df ufhrdtekb sdfkcfphbcbs vcufdcb obyflflt,t,bcfsdbc& DRT fhbc ,eyt,hbdb tybc ctvfynbrbc vtsjlb lf ofhvjbidf sfdcfnt[b obyflflt,t,bc ~vfsb ctvfynbrbc sdfkcfphbcbs` ctvfynbrbc lfcflutyfl lf fuhtsdt lhjbc lf fcgtmnbc ufhxtdbcfsdbc hjvfyek tyt,ib& fv vblujvfc cfae’dkfl eltdc vjlfkehb stjhbekb c tvfynbrf^ hjvtkbw itvjnfybkbf vjyntubec [ ] vbth lf ofhvfnt,bs b.j ufvj.tyt,ekb vbc vbth byukbcehb tybc ahfuvtynbcfsdbc& lqtbcfsdbc bub wyj,bkbf vjyntubec uhfvfnbrbc cf[tkojlt,bs& vjyntubec uhfvfnbrfv ufydbsfht,f /gjdf gfhnbtc ( Partee [ ] ), sjvfcjybc ~Thomasson [ ] ) , ajljhbc ~ Fodor [ ] ), rttyfybc ~ Keenan [ ] ) lf bfyctybc ( Iansen [ ] ) ihjvt,ib& DRT fh fhbc ovbylf vjltkeh stjhbekb ctvfynbrbc vtsjlb& DRT wlbkj,c uffcojhjc vjltkeh stjhbekb gfhflbuvt,bc wfkv[hbdj,f htathtywbfkehb gthcgtmnbdbc bynthghtnfwbfpt jhbtynbht,ek sdfkcfphbcsfy rjv,bybht,bs& bub fhbc kbyudbcnehb vybidytkj,bc eahj hsekb vtsjlb^ hflufyfw bub thsbc v[hbd cfufypt jhbtynbht,ekbf lf vtjhtc v[hbd bub lfrfdibht,ekbf tybc bynthghtnfwbfcsfy& tc stjhbf ufydbsfht,ekbf rfvabc (Kamp [ ] ) lf /tbvbc ~ Heim [ ] ) vbth& xdty itdtwlt,bs fqdothjs tc stjhbf lf cfsfyflj cfe,hbc ofhvjlutybc cnhemneht,b (DRS) lf vfsb fut,bc otct,b mfhsekb tybc ahfuvtynbc vfufkbspt& cfyfv fv stjhbbc fqothfc itdelut,jlts ufdtwyjs pjubths ‘bhbsfl wyt,t,c^ hjvkt,bw xdty lfudzbhlt,f DRT-c fqothbcfc& hjltcfw^ xdty drbs[ekj,s ntmcnc lf dbut,s vbc ibyffhcc tc ghjwtcb itb’kt,f ufut,ek bmytc hjujhw kbyudbcnehb ajhvblfy ibyffhcbc fqt,bc ghjwtcb lf fv ibyffhcbc xflt,f f[fk fphjdyt,bs ajhvfib& gbhbmbs^ hjwf xdty uflvjdwtvs ibyffhcc ntmcnbc utythbht,bcfc^ vfiby [lt,f ibyffhcbc fphjdyt,bsb ajhvblfy uflfnfyf ~xflt,f` kbyudbcneh ajhvfib&

fvudfhfl^ tc ghjwtct,b xdty itudb’kbf ufydb[bkjs hjujhw sfhuvfyb thsb tyblfy vtjhtpt ~ ,eyt,hbdb tyblfy fphjdyt,bc tyfpt sfhuvfyb fy gbhbmbs`& vtjhtc v[hbd^ bcvbc cfrbs[b ibyffhcbc ztivfhbnt,bc itcf[t, t&b& ,eyt,hbdb tybc ufvjcf[ekt,bc ~fy itcfn.dbcb fphjdyt,bc tybc ufvjcf[ekt,bc`^ hjvtkcfw ibyffhcb uffxybf^ ztivfhbnt,bc itcf[t,& cfyfv ufydvfhnfdlts se hfc ybiyfdc tc vjdb.dfyjs ajljhbc ( Fodor [ ] ) fhuevtynt,b&

wfkcf[f tybc vfufkbsbf obyflflt,fsf fqhbw[dbc tyf U⁰, cflfw bylbdblefkehb rjycnfynt,bf `a`, `b` lf `c`. thsflubkbfyb ghtlbrfnt,bf ~fye thsflubkbfyb pvyt,b fye ufhlfedfkb pvyt,b` `p` lf `q` thsflubkbfyb lfvfrfdibht,tkbf `┐` lf jhflubkbfyb lfvfrfdibht,kt,b `Ù ` lf `Ú `& ajhvekt,bc cbvhfdkt ufycfpqdhekbf htrehcbekfl^ hjujhw ctvfynbrehb cbvhfdkt K bctsb^ hjv

~0` se fhbc thsflubkbfyb pvyf lf a fhbc hfbvt bylbdblefkehb rjycnfynf^ vfiby <sup>┌</sup>~a `^┐ Î K

~1` se ζ thsflubkbfyb lfvfrfdibht,tkbf j Î K ^ vfiby ^┌ζj ^┐Î K lf

~2` se V jhflubkbfyb lfvfrfdibht,tkbf lf j , Y Î K , vfiby <sup>┌ j</sup> ζ Y <sup>┐Î</sup> K . `p(a)`, `┌ ┐ p(a) ` , ` p(a) Ú Q(a) lf ` ┐┐ p(a) Ù ┐ Q(b) ajhvekt,bf& fv ajhvekbht,fib vjyfobktj,c [esb cbynfmcehb rfntujhbf% bylbdblefkehb rjncnfynt,b^ thsflubkbfyb pvyt,b^ thsflubkbfyb lfvfrfdibht,kt,b^ jhflubkbfyb lfvfrfdibht,kt,b lf ajhvekt,b& ufhlf erfyfcrytkbcf^ .dtkf rfntujhbf ufycfpqdhekbf vfsb tktvtynt,bc xfvjsdkbs& ahx[bkt,bc cfvb o.dbkb fhwths rfntujhbfc fh tresdybfy& bcbyb itvjnfybkb fhbfy cbyrfntujhbvfnbrekfl ajhvekfsf cbvhfdkbc htrehcbekfl ufycfpqdhbcfc& hfw bvfc ybiyfdc^ hjv fv tybc cnfylfhnekb ctvfynbrehb bynthghtnfwbbc lhjc vfs fhfdbsfhb lfvjerblt,tkb vybidytkj,f fhf fmds& ahx[bkt,bc ctvfynbrehb ufvj.tyt,ff fhf vybidytkj,fsf itmvyf^ fhfvtl ajhvekfsf cbynfmcehb wfkcf[j,bc epheydtk.jaf^ ehjvkbcjlfw tyf bmyt,jlf jvjybvehb& fvbc cfbkecnhfwbjl ufydb[bkjs L tyf^ cflfw ~2` itwdkbkbf itvltub otcbs% ~2₁` se ζ fhbc jhflubkbfyb lfvfrfdibht,tkb lf j , Y Î K vfiby j ζY Î K . L tyf fhbc jvjybvbehb^ hflufy ajhvekfc

`p(a)Ú Q(a)Ù Q(b)`fmdc jhb ufhxtdf lf itcf,fvbcfl jhb ufyc[dfdt,ekb cbynfmcehb cnhemnehf%

(S1)

(S2)

cflfw S-bs fqybiyekbf ufycf[bkdtkb ajhvekf& se a fhbc gtnht^ b fhbc sfvfhb^ P fhbc lflbc lf Q fhbc pbc^ vfiby (S1) ybiyfdc ^hjv ~ gtnht lflbc` fy ~gtnht pbc lf sfvfhb pbc`^ [jkj (S2) ybiyfdc^ hjv ~gtnht lflbc fy gtnht pbc` lf ~sfvfhb pbc`& vhudfkb ahx[bkt,b fqybiyfdty `fy`-bcf lf `lf`-c cfpqdht,c& (S1) lf (S2) fhbfy fyfkbpbc [tt,b^ hjvkt,bw udbxdtyt,ty se hjujh ofhvjbmvyt,f otct,bc ufvj.tyt,bs S ajhvekf& fyfkbpbc [tt,b udbxdtyt,ty ajhvekfsf cbynfmceh cnhemneht,c^ hjvkt,bw sfdbc v[hbd vbbqt,bfy htrehcbekb ufycfpqdht,t,bs& cbynfmcehb rfntujhbt,b^ hjvkt,bw abuehbht,ty fv htrehcbt,ib ths-ths vybidytkjdfy sdbct,t,pt vbesbst,ty& se hfbvt ajhvekt,b tresdybfy thslfbvfdt cbynfmceh rfntujhbfc^ vfiby bcbyb thsyfbhfl itb’kt,f lferfdibhlyty c[df ufvjcf[ekt,t,c thsblfbubdt cjhnbc lfrfdibht,bs& tc fhbc ufvj.tyt,ekb tybc ajhvekt,bc htrehcbekb ufycfpqdhbcfc& lfrfdibht,bc cjhnt,b fhbfy aeymwbt,b^ hjvkt,bw bqt,ty ufvjcf[ekt,fsf vbvltdhj,fc lf udf’ktdty ufvjcf[ekt,t,c& vfufkbsbc cf[bs ufydcfpqdhjs fctsb aeymwbt,b U⁰-bcsdbc& dsmdfs F₀⁰ b.jc cjhnb^ hjvtkbw frfdibht,c thsflubkbfy pvyfc bylbdblefkeh rjycnfynfcsfy lf qt,ekj,c ajhvekfc^ F₁⁰ b.jc cjhnb^ hjvtkbw bqt,c thsflubkbfy lfvfrfdibht,tkc lf frfdibht,c vfc hfbvt ajhvekfcsfy^ hjv vbbqjc f[fkb ajhvekf& F₂⁰ b.jc cjhnb^ hjvtkbw frfdibht,c jhflubkbfy lfvfrfdibht,tkc jh-flubkbfy ajhvekfsf vbvltdhj,fcsfy lf qt,ekj,c f[fk ajhvekfc& fvudfhfl^ udfmdc ufynjkt,t,b^ hjvkt,bw ufycfpqdhfdty fv aeymwbt,c%

F₀^{0( d , a ) = ┌d ( a ) ┐}

F₁⁰(ζ‚φ) = ^┌ζ( j ) ^┐

tc aeymwbt,b afmnbehfl fhbfy jgthfwbt,b^ hjvkt,bw ufycfpqdhekbf tybc ufvjcf[ekt,t,pt& F₁^{0 (} ┐( QV`,`)b`)=^┌┐(QV( )b )^┐ fv aeymwbt,c tojlt,fs U⁰-bc cnhemnehekb jgthfwbt,b lf ufvjb.tyt,bfy cbynfmcehb otct,bc ufvjcfw[flt,kfl^ vfuhfv bcbyb sdbs fh fhbfy cbynfmcehb otct,b& fct vfufkbsfl^ fct,j,c bctsb otcb^ hjvtkbw udte,yt,f^ hjv F₀⁰ fhbc cbynfmcehb jgthfwbf lf ufvj.tyt,ekbf thsflubkbfyb pvybcf lf bylbdblefkehb rjycnfynbcfufy ajhvekbc vbcfqt,fl& bvbcfsdbc^ hjv fctsb otcb xfvjdf.fkb,js^ xdty gbhdtk hbuib eylf xfvjdsdfkjs U⁰-bc cbynfmcehb rfntujhbt,b% ICST, IV,1C, 2C lf FOR. dsmdfs Ñ b.jc cbvhfdkt { ICST,IV,1C,2C,FOR} . vjyntubec vb[tldbs^ tc cbvhfdkt fhbc wfkcf[f tybc ufycfpqdht,bc ths-thsb rjvgjytynsfufyb& cbynfmcehb otcb eylf itbwfdltc cfvb cf[bc byajhvfwbfc% cnhemnehek F jgthfwbfc^ ufvjcf[ekt,fsf cbynfmceh rfntujhbt,c^ hjvkt,bw fhbfy F-bc fhuevtynt,b lf F-bc vybidytkj,bc cbynfmceh rfntujhbfc& vfufkbsfl U⁰-bc gbhdtkb otcb fv,j,c^ hjv se e fhbc IV lf a fhbc ICST vfiby e ( a ) fhbc FOR. fvudfhfl^ vjyntubec cbynfmcehb otct,b fhbfy lfkfut,ekb cfvtekt,b^ hjvkbc gbhdtkb rjvgjytynb fhbc cnhemnehekb jgthfwbf^ vtjht rjvgjytynbf rfntujhbekb byltmct,bc vbvltdhj,f lf vtcfvt tktvtynbf rfntujhbekb byltmcb& fvudfhfl S⁰ cbvhfdkbc itvltub cfvb cfvtekb itflutyc U⁰-bc cbynfmcehb otct,bc cbvhfdktc%

< F₀^{0, <} IV,ICST> , FOR>

< F₁⁰,< 1C, FOR> , FOR>

< F₂⁰,< 2C, FOR, FOR > ,FOR>

ctvfynbrehb vjcfpht,bs vbpfyitojybkbf lfdfabmcbhjs bc rfntujhbf^ hjvtkbw itflutyc tybc obyflflt,t,c^ hflufy obyflflt,t,c eylf /mjyltc ztivfhbnekb vybidytkj,t,b& U⁰-bc itvs[dtdfib tc fhbc FOR. cbvhfdktt,b D ⁰ lf S⁰ bsdfkbcobyt,ty U⁰-bc cnhemnehek lf[fcbfst,fc& lf vstk hbu rfntujhbt,bc ufvjcf[ekt,t,c fmdc sfdbcb cnhemnehf^ ufhlf bv ufvjcf[ekt,t,bcf^ hjvkt,bw itflutyty htrehcbbc ,fpbcc& fctsb ufvjcf[ekt,t,b fhbfy d rfntujhbbc ufvjcf[ekt,t,b lf bcbyb tresdybfy ktmcbrjyc^ cflfw d Î D & ktmcbrjyb itbwfdc cbvhfdktc C d ^ cflfw d Î D & U⁰-csdbc fctsb cbvhfdktt,bf%

X⁰_ICST={ `a`,`b`,`c`}

X_IV={ `p`,`a`}

X⁰_IC={ ` Ø `}

X⁰_2C={ `V`,`Ù `}