(ÍêÕû°æ)±àÒëÔ­Àí[ÕÅËØÇÙ]µÚ2°æ-´ð°¸-Ç廪´óѧ³ö°æÉç ÏÂÔØ±¾ÎÄ

ÄÚÈÝ·¢²¼¸üÐÂʱ¼ä : 2025/7/19 7:05:28ÐÇÆÚÒ» ÏÂÃæÊÇÎÄÕµÄÈ«²¿ÄÚÈÝÇëÈÏÕæÔĶÁ¡£

T¡úT+S£üS

£¨£±£© ¹¹ÔìG£ÛS£ÝµÄËã·ûÓÅÏȹØÏµ±í£¬²¢ÅжÏG£ÛS£ÝÊÇ·ñΪËã·ûÓÅÏÈÎÄ·¨¡£ £¨£²£© ¸ø³ö¾äÐÍa(T+S);H;(S)µÄ¶ÌÓï¡¢¾ä±ú¡¢ËضÌÓïºÍ×î×óËØ¶ÌÓï¡£

£¨£³£© ¸ø³öa;(a+a)ºÍ(a+a)µÄ·ÖÎö¹ý³Ì£¬ËµÃ÷ËüÃÇÊÇ·ñΪG£ÛS£ÝµÄ¾ä×Ó¡£

£¨£´£© ¸ø³ö£¨£³£©ÖÐÊäÈë´®µÄ×îÓÒÍÆµ¼£¬·Ö±ð˵Ã÷Á½ÊäÈë´®ÊÇ·ñΪG[S]µÄ¾ä×Ó¡£ £¨£µ£© ÓÉ£¨£³£©ºÍ£¨£´£©ËµÃ÷ÁËËã·ûÓÅÏÈ·ÖÎöµÄÄÄЩȱµã¡£

£¨£¶£© Ëã·ûÓÅÏÈ·ÖÎö¹ý³ÌºÍ¹æ·¶¹éÔ¼¹ý³Ì¶¼ÊÇ×îÓÒÍÆµ¼µÄÄæ¹ý³ÌÂ𣿠´ð°¸£º£¨1£©¹¹ÔìÎÄ·¨G£ÛS£ÝµÄËã·ûÓÅÏȹØÏµ¾ØÕó£º

ÔÚÉϱíÖпɿ´³öÖÕ½á·ûÖ®¼äµÄÓÅÏȹØÏµÊÇΨһµÄ£¬»ò³ÆG£ÛS£ÝµÄËã·ûÓÅÏȹØÏµ¾ØÕ󲻺¬¶àÖØÈë¿Ú£¬Òò´Ë£¬G£ÛS£ÝÊÇÒ»¸öËã·ûÓÅÏÈÎÄ·¨¡£

£¨£²£©

£¨3£©¶ÔÊäÈë´®(a+a)££µÄ·ÖÎö¹ý³ÌÈçÏ£º

˵Ã÷ÊÇËüµÄ¾ä×Ó¡£

£¨£´£©ÊÔÓÃ¹æ·¶ÍÆµ¼£º

S? G?H?£¨S£©ÓÉ´ËÍùÏÂS ²»¿ÉÄÜÍÆµ¼³öa+a£¬ËùÒÔ (a+a)²»ÊÇG£ÛS£ÝµÄ¾ä×Ó¡£

£¨5£©½á¹û˵Ã÷£ºÓÉÓÚËã·ûÓÅÏÈ·ÖÎö·¨È¥µôÁ˵¥·ÇÖÕ½á·ûÖ®¼äµÄ¹éÔ¼£¬¾¡¹ÜÔÚ·ÖÎö¹ý³ÌÖУ¬ µ±¾ö¶¨ÊÇ·ñΪ¾ä±úʱ²ÉȡһЩ¼ì²é´ëÊ©£¬µ«ÈÔÄÑÍêÈ«±ÜÃâ°Ñ´íÎóµÄ¾ä×ӵõ½ÕýÈ·µÄ¹éÔ¼¡£ £¨£¶£©Ëã·ûÓÅÏÈ·ÖÎö¹ý³Ì²»ÊÇ×îÓÒÍÆµ¼µÄÄæ¹ý³Ì¡£¹æ·¶¹éÔ¼¹ý³ÌÊÇ×îÓÒÍÆµ¼µÄÄæ¹ý³Ì¡£

µÚ7 ÕÂ LR ·ÖÎö

µÚ1 ÌâÒÑÖªÎÄ·¨A¡úaAd|aAb|¦Å

ÅжϸÃÎÄ·¨ÊÇ·ñÊÇSLR(1)ÎÄ·¨£¬ÈôÊǹ¹ÔìÏàÓ¦·ÖÎö±í£¬²¢¶ÔÊäÈë´®ab#¸ø³ö·ÖÎö¹ý³Ì¡£ ´ð°¸£ºÎÄ·¨£ºA¡úaAd|aAb|¦Å

ÍØ¹ãÎÄ·¨ÎªG¡ä£¬Ôö¼Ó²úÉúʽS¡ä¡úA Èô²úÉúʽÅÅÐòΪ£º 0 S' ¡úA 1 A ¡úaAd 2 A ¡úaAb 3 A ¡ú¦Å

ÓɲúÉúʽ֪£º

First (S' ) = {¦Å,a} First (A ) = {¦Å,a} Follow(S' ) = {#} Follow(A ) = {d,b,#}

G¡äµÄLR(0)ÏîÄ¿¼¯×弰ʶ±ð»îǰ׺µÄDFA ÈçÏÂͼËùʾ£º

ÔÚI0 ÖУºA ¡ú.aAd ºÍA ¡ú.aAb ÎªÒÆ½øÏîÄ¿£¬A ¡ú.Ϊ¹éÔ¼ÏîÄ¿£¬´æÔÚÒÆ½ø-¹éÔ¼³åÍ»£¬Òò´ËËù¸øÎÄ·¨²»ÊÇLR(0)ÎÄ·¨¡£

ÔÚI0¡¢I2 ÖУºFollow(A) ¡É{a}= {d£¬b£¬#} ¡É{a}=

ËùÒÔÔÚI0¡¢I2 ÖеÄÒÆ½ø-¹éÔ¼³åÍ»¿ÉÒÔÓÉFollow ¼¯½â¾ö£¬ËùÒÔG ÊÇSLR(1)ÎÄ·¨¡£ ¹¹ÔìµÄSLR(1)·ÖÎö±íÈçÏ£ºÌâÄ¿1 µÄSLR(1)·ÖÎö±í

ÌâÄ¿1 ¶ÔÊäÈë´®ab#µÄ·ÖÎö¹ý³Ì

·ÖÎö³É¹¦£¬ËµÃ÷ÊäÈë´®ab ÊÇÎÄ·¨µÄ¾ä×Ó¡£

µÚ2 ÌâÈôÓж¨Òå¶þ½øÖÆÊýµÄÎÄ·¨ÈçÏ£º S¡úL¡¤L|L L¡úLB|B B¡ú0|1

(1) ÊÔΪ¸ÃÎÄ·¨¹¹ÔìLR ·ÖÎö±í£¬²¢ËµÃ÷ÊôÄÄÀàLR ·ÖÎö±í¡£ (2) ¸ø³öÊäÈë´®101.110 µÄ·ÖÎö¹ý³Ì¡£ ´ð°¸£ºÎÄ·¨£º S¡úL.L|L L¡úLB|B B¡ú0|1

ÍØ¹ãÎÄ·¨ÎªG¡ä£¬Ôö¼Ó²úÉúʽS¡ä¡úS Èô²úÉúʽÅÅÐòΪ£º 0 S' ¡úS 1 S ¡úL.L 2 S ¡úL 3 L ¡úLB 4 L ¡úB 5 B ¡ú0 6 B ¡ú1

ÓɲúÉúʽ֪£º

First (S' ) = {0,1} First (S ) = {0,1} First (L ) = {0,1} First (B ) = {0,1} Follow(S' ) = {#} Follow(S ) = {#}

Follow(L ) = {.,0,1,#} Follow(B ) = {.,0,1,#}

G¡äµÄLR(0)ÏîÄ¿¼¯×弰ʶ±ð»îǰ׺µÄDFA ÈçÏÂͼËùʾ£º

ÔÚI2 ÖУºB ¡ú.0 ºÍ B ¡ú.1 ÎªÒÆ½øÏîÄ¿£¬S ¡úL.Ϊ¹éÔ¼ÏîÄ¿£¬´æÔÚÒÆ½ø-¹éÔ¼³åÍ»£¬Òò´ËËù¸øÎÄ·¨²»ÊÇLR(0)ÎÄ·¨¡£

ÔÚI2¡¢I8 ÖУºFollow(s) ¡É{0£¬1}= { #} ¡É{0£¬1}=

ËùÒÔÔÚI2 ¡¢I8 ÖеÄÒÆ½ø-¹éÔ¼³åÍ»¿ÉÒÔÓÉFollow ¼¯½â¾ö£¬ËùÒÔG ÊÇSLR(1)ÎÄ·¨¡£ ¹¹ÔìµÄSLR(1)·ÖÎö±íÈçÏ£ºÌâÄ¿2 µÄSLR(1)·ÖÎö±í

ÌâÄ¿2 ¶ÔÊäÈë´®101.110#µÄ·ÖÎö¹ý³Ì

·ÖÎö³É¹¦£¬ËµÃ÷ÊäÈë´®101.110 ÊÇÌâÄ¿2 ÎÄ·¨µÄ¾ä×Ó¡£ ÌâÄ¿3¿¼ÂÇÎÄ·¨S-> A S | b

A -> S A | a

£¨1£©ÁгöÕâ¸öÎÄ·¨µÄËùÓÐLR(0)ÏîÄ¿

£¨2£©°´£¨1£©ÁгöµÄÏîÄ¿¹¹Ôìʶ±ðÕâ¸öÎÄ·¨»îǰ׺µÄNFA£¬°ÑÕâ¸öNFA È·¶¨»¯ÎªDFA£¬ËµÃ÷

Õâ¸öDFA µÄËùÓÐ״̬ȫÌå¹¹³ÉÕâ¸öÎÄ·¨µÄLR(0)¹æ·¶×å £¨3£©Õâ¸öÎÄ·¨ÊÇSLR µÄÂð£¿ÈôÊÇ£¬¹¹Ôì³öËüµÄSLR ·ÖÎö±í £¨4£©Õâ¸öÎÄ·¨ÊÇLALR »òLR(1)µÄÂ𣿠´ð£º

£¨1£©ÁîÍØ¹ãÎÄ·¨G¡¯Îª (0) S¡¯ -> S (1)S-> A S (2)S-> b (3)A -> S A (4)A -> a

ÆäLR(0)ÏîÄ¿£º

(2) ʶ±ðÕâ¸öÎÄ·¨»îǰ׺µÄNFA ÈçÉÏͼËùʾ£º È·¶¨»¯ÎªDFA ÈçÏÂͼËùʾ£º