LL1 (1131543)
Текст из файла
ƒ« ¢ 3. ‘¨â ªá¨ç¥áª¨© «¨§
3.1. Žá®¢ë¥ ¯®ïâ¨ï ¨ ®¯à¥¤¥«¥¨ï
�ãáâì G=<N,T,P,S> - ª®â¥ªáâ®-᢮¡®¤ ï £à ¬¬ ⨪ , £¤¥ N - ¬®¦¥á⢮ ¥â¥à¬¨ «ìëå ᨬ¢®«®¢, T - ¬®¦¥á⢮ â¥à¬¨ «ìëå ᨬ¢®«®¢, P - ¬®¦¥á⢮ ¯à ¢¨« ¢ë¢®¤ ¨ S - ªá¨®¬ . �㤥¬ £®¢®à¨âì, çâ® uxv ¢ë¢®¤¨âáï § ®¤¨ è £ ¨§ uAv (¨ § ¯¨áë¢ âì íâ® ª ª uAv=>uxv), ¥á«¨ A->x - ¯à ¢¨«® ¢ë¢®¤ ¨ u ¨ v - ¯à®¨§¢®«ìë¥ áâப¨ ¨§ (N U T)*. …᫨ u1=>u2=>...=>un, ¡ã¤¥¬ £®¢®à¨âì, çâ® ¨§ u1 ¢ë¢®¤¨âáï un, ¨ § ¯¨áë¢ âì íâ® ª ª u1=>*un. ’.¥.:
1) u=>*u ¤«ï «î¡®© áâப¨ u,
2) ¥á«¨ u=>*v ¨ v=>*w, â® u=>*w.
€ «®£¨ç®, "=>+" ®§ ç ¥â ¢ë¢®¤¨âáï § ®¤¨ ¨«¨ ¡®«¥¥ è £®¢.
…᫨ ¤ £à ¬¬ ⨪ G á ç «ìë¬ á¨¬¢®«®¬ S, ®â®è¥¨¥ =>+ ¬®¦® ¨á¯®«ì§®¢ âì ¤«ï ®¯à¥¤¥«¥¨ï L(G) - ï§ëª , ¯®à®¦¤¥®£® G. ‘âப¨ L(G) ¬®£ãâ ᮤ¥à¦ âì ⮫쪮 â¥à¬¨ «ìë¥ á¨¬¢®«ë G. ‘âப â¥à¬¨ «®¢ w ¯à¨ ¤«¥¦¨â L(G) ⮣¤ ¨ ⮫쪮 ⮣¤ , ª®£¤ S=>+w. ‘âப w §ë¢ ¥âáï ¯à¥¤«®¦¥¨¥¬ ¢ G.
…᫨ S=>*u, £¤¥ u ¬®¦¥â ᮤ¥à¦ âì ¥â¥à¬¨ «ë, â® u §ë¢ ¥âáï á¥â¥æ¨ «ì®© ä®à¬®© ¢ G. �।«®¦¥¨¥ - íâ® á¥â¥æ¨ «ì ï ä®à¬ , ¥ ᮤ¥à¦ é ï ¥â¥à¬¨ «®¢.
� áᬮâਬ ¢ë¢®¤ë, ¢ ª®â®àëå ¢ «î¡®© á¥â¥æ¨ «ì®© ä®à¬¥ ª ¦¤®¬ è £¥ ¤¥« ¥âáï ¯®¤áâ ®¢ª á ¬®£® «¥¢®£® ¥â¥à¬¨ « . ’ ª®© ¢ë¢®¤ §ë¢ ¥âáï «¥¢®áâ®à®¨¬. …᫨ S=>*u ¢ ¯à®æ¥áᥠ«¥¢®áâ®à®¥£® ¢ë¢®¤ , â® u - «¥¢ ï á¥â¥æ¨ «ì ï ä®à¬ . € «®£¨ç® ®¯à¥¤¥«ï¥âáï ¯à ¢®áâ®à®¨© ¢ë¢®¤.
“¯®à冷ç¥ë¬ £à 䮬 §ë¢ ¥âáï ¯ à (V,E), £¤¥ V ®¡®§ ç ¥â ¬®¦¥á⢮ ¢¥àè¨, E - ¬®¦¥á⢮ «¨¥©® 㯮à冷ç¥ëå ᯨ᪮¢ ¤ã£, ª ¦¤ë© í«¥¬¥â ª®â®à®£® ¨¬¥¥â ¢¨¤ ((v,e1),(v,e2),...,(v,en)). �â®â í«¥¬¥â 㪠§ë¢ ¥â, çâ® ¨§ ¢¥àè¨ë a ¢ë室ïâ n ¤ã£, ¯à¨ç¥¬ ¯¥à¢®© ¨§ ¨å áç¨â ¥âáï ¤ã£ , ¢å®¤ïé ï ¢ ¢¥àè¨ã e1, ¢â®à®© - ¤ã£ , ¢å®¤ïé ï ¢ ¢¥àè¨ã e2, ¨ â.¤.
„¥à¥¢® ¢ë¢®¤ ¢ £à ¬¬ ⨪¥ G=(N,T,P,S) - íâ® ¯®¬¥ç¥®¥ 㯮à冷祮¥ ¤¥à¥¢®, ª ¦¤ ï ¢¥àè¨ ª®â®à®£® ¯®¬¥ç¥ ᨬ¢®«®¬ ¨§ ¬®¦¥á⢠N U T U {e}. …᫨ ¢ãâà¥ïï ¢¥àè¨ ¯®¬¥ç¥ ᨬ¢®«®¬ A, ¥¥ ¯àï¬ë¥ ¯®â®¬ª¨ - ᨬ¢®« ¬¨ X1,..., Xn, â® A->X1X2...Xn - ¯à ¢¨«® í⮩ £à ¬¬ ⨪¨.
“¯®à冷祮¥ ¯®¬¥ç¥®¥ ¤¥à¥¢® D §ë¢ ¥âáï ¤¥à¥¢®¬ ¢ë¢®¤ (¨«¨ ¤¥à¥¢®¬ à §¡®à ) ¢ Š‘-£à ¬¬ ⨪¥ G(S)=(N,T,P,S), ¥á«¨ ¢ë¯®«¥ë á«¥¤ãî騥 ãá«®¢¨ï:
(1) ª®à¥ì ¤¥à¥¢ D ¯®¬¥ç¥ S;
(2) ª ¦¤ë© «¨áâ ¯®¬¥ç¥ «¨¡® a<-T, «¨¡® e;
(3) ª ¦¤ ï ¢ãâà¥ïï ¢¥àè¨ ¯®¬¥ç¥ ¥â¥à¬¨ «®¬;
(4) ¥á«¨ N - ¥â¥à¬¨ «, ª®â®àë¬ ¯®¬¥ç¥ ¢ãâà¥ïï ¢¥àè¨ ¨ X1,...,Xn - ¬¥âª¨ ¥¥ ¯àï¬ëå ¯®â®¬ª®¢ ¢ 㪠§ ®¬ ¯®à浪¥, â® N->X1...Xk - ¯à ¢¨«® ¨§ ¬®¦¥á⢠P.
€¢â®¬ â á ¬ £ §¨®© ¯ ¬ïâìî (᮪à 饮 Œ�- ¢â®¬ â) - í⮠ᥬ¥àª P=(Q,T,ƒ,d,q0,Z0,F), £¤¥
(1) Q - ª®¥ç®¥ ¬®¦¥á⢮ ᨬ¢®«®¢ á®áâ®ï¨©, ¯à¥¤áâ ¢«ïîé¨å ¢á¥¢®§¬®¦ë¥ á®áâ®ï¨ï ã¯à ¢«ïî饣® ãáâனá⢠;
(2) T - ª®¥çë© ¢å®¤®© «ä ¢¨â;
(3) ƒ - ª®¥çë© «ä ¢¨â ¬ £ §¨ëå ᨬ¢®«®¢;
(4) d - äãªæ¨ï ¯¥à¥å®¤®¢ - ®â®¡à ¦¥¨¥ ¬®¦¥á⢠Qx(T U {e})xƒ ¢ ¬®¦¥á⢮ ª®¥çëå ¯®¤¬®¦¥á⢠Qxƒ*, â.¥. d:Qx(T U {e})xƒ -> {Qxƒ*};
(5) q0<-Q - ç «ì®¥ á®áâ®ï¨¥ ã¯à ¢«ïî饣® ãáâனá⢠;
(6) Z0<-ƒ - ᨬ¢®«, 室ï騩áï ¢ ¬ £ §¨¥ ¢ ç «ìë© ¬®¬¥â ( ç «ìë© á¨¬¢®«);
(7) F<=Q - ¬®¦¥á⢮ § ª«îç¨â¥«ìëå á®áâ®ï¨©
Ю䍣ãà æ¨¥© Œ�- ¢â®¬ â §ë¢ ¥âáï âனª (q,w,u)<-QxT*xƒ*, £¤¥
(1) q - ⥪ã饥 á®áâ®ï¨¥ ã¯à ¢«ïî饣® ãáâனá⢠;
(2) w - ¥¨á¯®«ì§®¢ ï ç áâì ¢å®¤®© 楯®çª¨; ¯¥à¢ë© ᨬ¢®« 楯®çª¨ w 室¨âáï ¯®¤ ¢å®¤®© £®«®¢ª®©; ¥á«¨ w e, â® áç¨â ¥âáï, çâ® ¢áï ¢å®¤ ï «¥â ¯à®ç¨â ;
(3) u - ᮤ¥à¦¨¬®¥ ¬ £ §¨ ; á ¬ë© «¥¢ë© ᨬ¢®« 楯®çª¨ u áç¨â ¥âáï ¢¥à娬 ᨬ¢®«®¬ ¬ £ §¨ ; ¥á«¨ u=e, â® ¬ £ §¨ áç¨â ¥âáï ¯ãáâë¬.
’ ªâ à ¡®âë Œ�- ¢â®¬ â P ¡ã¤¥¬ ¯à¥¤áâ ¢«ïâì ¢ ¢¨¤¥ ¡¨ ண® ®â®è¥¨ï |-, ®¯à¥¤¥«¥®£® ª®ä¨£ãà æ¨ïå. �㤥¬ ¯¨á âì
(q,aw,Zu)|-(q',w,vu)
¥á«¨ ¬®¦¥á⢮ d(q,a,Z) ᮤ¥à¦¨â (q',v), £¤¥ q, q'<-Q, a<-T U {e}, w<-T*, Z<-ƒ, u,v<-ƒ*.
� ç «ì®© ª®ä¨£ãà æ¨¥© Œ�- ¢â®¬ â P §ë¢ ¥âáï ª®ä¨£ãà æ¨ï ¢¨¤ (q0,w,Z0), £¤¥ w<-T*, â.¥. ã¯à ¢«ïî饥 ãáâனá⢮ 室¨âáï ¢ ç «ì®¬ á®áâ®ï¨¨, ¢å®¤ ï «¥â ᮤ¥à¦¨â 楯®çªã, ª®â®àãî 㦮 à ᯮ§ âì, ¢ ¬ £ §¨¥ ¥áâì ⮫쪮 ç «ìë© á¨¬¢®« Z0. ‡ ª«îç¨â¥«ì ï ª®ä¨£ãà æ¨ï - íâ® ª®ä¨£ãà æ¨ï ¢¨¤ (q,e,u), £¤¥ q<-F, u<-ƒ*.
ƒ®¢®àïâ, ç⮠楯®çª w ¤®¯ã᪠¥âáï Œ�- ¢â®¬ ⮬ P, ¥á«¨ (q0,w,Z0)|-*(q,e,u) ¤«ï ¥ª®â®àëå q<-F ¨ u<-ƒ*. Ÿ§ëª®¬, ®¯à¥¤¥«ï¥¬ë¬ (¨«¨ ¤®¯ã᪠¥¬ë¬) ¢â®¬ ⮬ P (®¡®§ ç ¥âáï L(P)), §ë¢ îâ ¬®¦¥á⢮ 楯®ç¥ª, ¤®¯ã᪠¥¬ëå ¢â®¬ ⮬ P.
ˆ®£¤ ¤®¯ãá⨬®áâì ®¯à¥¤¥«ïî⠥᪮«ìª® ¨ ç¥: 楯®çª w ¤®¯ã᪠¥âáï Œ�- ¢â®¬ ⮬ P, ¥á«¨ (q0,w,Z0)|-*(q,e,e). �⨠®¯à¥¤¥«¥¨ï íª¢¨¢ «¥âë.
3.2. ’ ¡«¨ç®-ã¯à ¢«ï¥¬ë© ¯à¥¤áª §ë¢ î騩 à §¡®à
3.2.1. €«£®à¨â¬ à §¡®à ᢥàåã-¢¨§
Žá®¢ ï ¯à®¡«¥¬ ¯à¥¤áª §ë¢ î饣® à §¡®à - ®¯à¥¤¥«¥¨¥ ¯à ¢¨« ¢ë¢®¤ , ª®â®à®¥ 㦮 ¯à¨¬¥¨âì ª ¥â¥à¬¨ «ã. �à®æ¥áá ¯à¥¤áª §ë¢ î饣® à §¡®à (ᢥàåã-¢¨§) á â®çª¨ §à¥¨ï ¯®áâ஥¨ï ¤¥à¥¢ à §¡®à ¬®¦® ¯à®¨««îáâà¨à®¢ âì à¨á. 3.1. ”à £¬¥âë ¥¤®áâ஥®£® ¤¥à¥¢ ᮮ⢥âáâ¢ãîâ á¥â¥æ¨ «ìë¬ ä®à¬ ¬ ¢ë¢®¤ . ‚ ç «¥ ¤¥à¥¢® á®á⮨â ⮫쪮 ¨§ ®¤®© ¢¥àè¨ë, ᮮ⢥âáâ¢ãî饩 ªá¨®¬¥ S. ‚ íâ®â ¬®¬¥â ¯® ¯¥à¢®¬ã ᨬ¢®«ã ¢å®¤®£® ¯®â®ª ¯à¥¤áª §ë¢ î騩 «¨§ â®à ¤®«¦¥ ®¯à¥¤¥«¨âì ¯à ¢¨«® S->X1 X2 ..., ª®â®à®¥ ¤®«¦® ¡ëâì ¯à¨¬¥¥® ª S. ‡ ⥬ ¥®¡å®¤¨¬® ®¯à¥¤¥«¨âì ¯à ¢¨«®, ª®â®à®¥ ¤®«¦® ¡ëâì ¯à¨¬¥¥® ª X1, ¨ â.¤., ¤® â¥å ¯®à, ¯®ª ¢ ¯à®æ¥áᥠ⠪®£® ¯®áâ஥¨ï á¥â¥æ¨ «ì®© ä®à¬ë, ᮮ⢥âáâ¢ãî饩 «¥¢®¬ã ¢ë¢®¤ã, ¥ ¡ã¤¥â ¯à¨¬¥¥® ¯à ¢¨«® Y->a .... �â®â ¯à®æ¥áá § ⥬ ¯à¨¬¥ï¥âáï ¤«ï á«¥¤ãî饣® á ¬®£® «¥¢®£® ¥â¥à¬¨ «ì®£® ᨬ¢®« á¥â¥æ¨ «ì®© ä®à¬ë.
S S S
/ | \ / | \
X1 X2... X1 X2...
/ / |
........... .............
/ / |
Y Y |
/|\ /|\ Z
/ ... / ... /|\
a..........$ a...........$ a........b.......$
) ¡) ¢)
�¨á. 3.1
� à¨á. 3.2 ¯à¨¢¥¤¥ áâàãªâãà ¯à¥¤áª §ë¢ î饣® «¨§ â®à , ª®â®àë© ®¯à¥¤¥«ï¥â ®ç¥à¥¤®¥ ¯à ¢¨«® ¨§ â ¡«¨æë. ’ ªãî â ¡«¨æã ¬®¦® ¯®áâநâì ¥¯®á।á⢥® ¨§ £à ¬¬ ⨪¨.
ÚÄÄÄÂÄÄÄÂÄÄÄÂÄÄÄ¿
‚室 ³ a ³ + ³ b ³ $ ³
ÀÄÄÄÁÄÄÄÁÄÄÄÁÄÄÄÙ
^
³
ÚÄ¿ ÚÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄ¿
³X³ ³ �à®£à ¬¬ ¯à¥¤áª §ë- ³ ‚ë室
Œ £ §¨ ÃÄ´<ÄÄÄ´ ¢ î饣® «¨§ â®à ÃÄÄÄ>
³Y³ ÀÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÙ
³Z³ ³
³-³ v
³$³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÀÄÙ ³ ’ ¡«¨æ «¨§ â®à ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
�¨á. 3.2
’ ¡«¨ç®-ã¯à ¢«ï¥¬ë© ¯à¥¤áª §ë¢ î騩 «¨§ â®à ¨¬¥¥â ¢å®¤®© ¡ãä¥à, â ¡«¨æã «¨§ ¨ ¢ë室. ‚室®© ¡ãä¥à ᮤ¥à¦¨â à ᯮ§ ¢ ¥¬ãî áâபã, § ª®â®à®© á«¥¤ã¥â $ - ¯à ¢ë© ª®æ¥¢®© ¬ થà, ¯à¨§ ª ª®æ áâப¨. Œ £ §¨ ᮤ¥à¦¨â ¯®á«¥¤®¢ ⥫ì®áâì ᨬ¢®«®¢ £à ¬¬ ⨪¨ á $ ¤¥. ‚ ç «¥ ¬ £ §¨ ᮤ¥à¦¨â ç «ìë© á¨¬¢®« £à ¬¬ ⨪¨ ¢¥àåã誥 ¨ $ ¤¥. ’ ¡«¨æ «¨§ - íâ® ¤¢ã¬¥àë© ¬ áᨢ M[A,a], £¤¥ A - ¥â¥à¬¨ «, ¨ a - â¥à¬¨ « ¨«¨ ᨬ¢®« $.
€ «¨§ â®à ã¯à ¢«ï¥âáï ¯à®£à ¬¬®©, ª®â®à ï à ¡®â ¥â á«¥¤ãî騬 ®¡à §®¬. Ž à áᬠâਢ ¥â X - ᨬ¢®« ¢¥àåã誥 ¬ £ §¨ ¨ a - ⥪ã騩 ¢å®¤®© ᨬ¢®«. �⨠¤¢ ᨬ¢®« ®¯à¥¤¥«ïîâ ¤¥©á⢨¥ «¨§ â®à . ˆ¬¥îâáï âਠ¢®§¬®¦®áâ¨.
1. …᫨ X=a=$, «¨§ â®à ®áâ ¢«¨¢ ¥âáï ¨ á®®¡é ¥â ®¡ ãᯥ讬 ®ª®ç ¨¨ à §¡®à .
2. …᫨ X=a#$, «¨§ â®à 㤠«ï¥â X ¨§ ¬ £ §¨ ¨ ¯à®¤¢¨£ ¥â 㪠§ â¥«ì ¢å®¤ á«¥¤ãî騩 ¢å®¤®© ᨬ¢®«.
3. …᫨ X - ¥â¥à¬¨ «, ¯à®£à ¬¬ § £«ï¤ë¢ ¥â ¢ â ¡«¨æã M[X,a]. �® í⮬㠢室ã åà ¨âáï «¨¡® ¯à ¢¨«® ¤«ï X, «¨¡® ®è¨¡ª . …᫨, ¯à¨¬¥à, M[X,a]={X->UVW}, «¨§ â®à § ¬¥ï¥â X ¢¥àåã誥 ¬ £ §¨ WVU { ¢¥àåã誥 U}. �㤥¬ áç¨â âì, çâ® «¨§ â®à ¢ ª ç¥á⢥ ¢ë室 ¯à®áâ® ¯¥ç ⠥⠨ᯮ«ì§®¢ ë¥ ¯à ¢¨« ¢ë¢®¤ . …᫨ M[X,a]=error, «¨§ â®à ®¡à é ¥âáï ª ¯®¤¯à®£à ¬¬¥ «¨§ ®è¨¡®ª.
�®¢¥¤¥¨¥ «¨§ â®à ¬®¦¥â ¡ëâì ®¯¨á ® ¢ â¥à¬¨ å ª®ä¨£ãà æ¨© ¢â®¬ â à §¡®à .
€«£®à¨â¬ 3.1. �¥à¥ªãàá¨¢ë© ¯à¥¤áª §ë¢ î騩 «¨§.
repeat X:=¢¥à娩 ᨬ¢®« ¬ £ §¨ ;
if X - â¥à¬¨ « ¨«¨ $
then if X=InSym
then 㤠«¨âì X ¨§ ¬ £ §¨ ;
InSym:=®ç¥à¥¤®© ᨬ¢®«;
else error()
end
else /*X = ¥â¥à¬¨ «*/
if M[X,InSym]=X->Y1Y2...Yk
then 㤠«¨âì X ¨§ ¬ £ §¨ ;
¯®¬¥áâ¨âì Yk,Yk-1,...Y1 ¢ ¬ £ §¨
(Y1 ¢¥àåãèªã);
¢ë¢¥á⨠¯à ¢¨«® X->Y1Y2...Yk
else error() /*¢å®¤ â ¡«¨æë M ¯ãáâ*/
end end
until X=$ /*¬ £ §¨ ¯ãáâ*/
�¨á. 3.3
‚ ç «¥ «¨§ â®à 室¨âáï ¢ ª®ä¨£ãà æ¨¨, ¢ ª®â®à®© ¬ £ §¨ ᮤ¥à¦¨â S$, (S - ç «ìë© á¨¬¢®« £à ¬¬ ⨪¨), ¢® ¢å®¤®¬ ¡ãä¥à¥ w$ (w - ¢å®¤ ï æ¥¯®çª ), ¯¥à¥¬¥ ï InSym ᮤ¥à¦¨â ¯¥à¢ë© ᨬ¢®« ¢å®¤®© áâப¨. �à®£à ¬¬ , ¨á¯®«ì§ãîé ï â ¡«¨æã «¨§ â®à M ¤«ï ®áãé¥á⢫¥¨ï à §¡®à , ¨§®¡à ¦¥ à¨á. 3.3.
�ਬ¥à 3.1. � áᬮâਬ £à ¬¬ ⨪ã à¨ä¬¥â¨ç¥áª¨å ¢ëà ¦¥¨©:
E -> T E'
E' -> + T E' | e
T -> F T' (*)
T' -> * F T' | e
F -> ( E ) | id
’ ¡«¨æ ¯à¥¤áª §ë¢ î饣® «¨§ â®à ¤«ï ¥¥ ¨§®¡à ¦¥ à¨á. 3.4. ‡¤¥áì ¯ãáâë¥ ª«¥âª¨ - ¢å®¤ë ®è¨¡®ª. �¥¯ãáâë¥ ¤ îâ ¯à ¢¨« , ¯® ª®â®àë¬ ¤¥« ¥âáï à §¢¥à⪠¥â¥à¬¨ « .
ÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
�¥â¥à-³ ‚室®© ᨬ¢®«
ÃÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄÄ
¬¨ « ³ id ³ + ³ * ³ ( ³ ) ³ $
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.















