1.6 »³öʶ±ðÏÂÊöÓïÑÔµÄDFAµÄ״̬ͼ¡£
a){w | w´Ó1¿ªÊ¼ÒÔ0½áÊø}
b){w | wÖÁÉÙÓÐ3¸ö1}
c) {w | wº¬ÓÐ×Ó´®0101}
1 1 0 0 1 0 0 1 0,1 0 1 0 1 0 1 0,1 0 1 0,1 1 1 0
0 d) {w | wµÄ³¤¶È²»Ð¡ÓÚ3£¬ÇÒµÚÈý¸ö·ûºÅΪ0}
0,1 0,1 1 0,1 0 1 0 0,1 e) {w | w´Ó0¿ªÊ¼ÇÒΪÆ泤¶È£¬»ò´Ó1¿ªÊ¼ÇÒΪż³¤¶È}
0 1 0,1 0,1 0,1 0,1 0 »ò
1 0,1 0,1
f) {w | w²»º¬×Ó´®110}
0
1
0 1 1 0 0,1 g) {w | wµÄ³¤¶È²»³¬¹ý5}
h){w | wÊdzý11ºÍ111ÒÔÍâµÄÈκÎ×Ö·û} 1 1 1
i){w | wµÄÆæλÖþùΪ1}
1
0,1 0
j) {w | wÖÁÉÙº¬ÓÐ2¸ö0£¬ÇÒÖÁ¶àº¬ÓÐ1¸ö1}
0 k) {¦Å,0}
0 1
0,1 0,1 0 1 0 0 1 0 1 1 0 1 1 0,1
0,1 0 0 0 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 l) {w | wº¬ÓÐżÊý¸ö0£¬»òÇ¡ºÃÁ½¸ö1}
m) ¿Õ¼¯ n) ³ý¿Õ´®ÍâµÄËùÓÐ×Ö·û´®
1.29ÀûÓñÃÒýÀíÖ¤Ã÷ÏÂÊöÓïÑÔ²»ÊÇÕýÔòµÄ¡£ a. A1={012 | n?0}¡£
Ö¤Ã÷£º¼ÙÉèA1ÊÇÕýÔòµÄ¡£ÉèpÊDZÃÒýÀí¸ø³öµÄ¹ØÓÚA1µÄ±Ã³¤¶È¡£
ÁîS=012,
¡ßSÊÇA1µÄÒ»¸ö³ÉÔ±ÇÒSµÄ³¤¶È´óÓÚp£¬ËùÒÔ±ÃÒýÀí±£Ö¤S¿É±»·Ö³É3¶ÎS=xyzÇÒÂú×ã±ÃÒýÀíµÄ3¸öÌõ¼þ¡£¸ù¾ÝÌõ¼þ3£¬yÖÐÖ»º¬0£¬xyyzÖУ¬0±È1¡¢2¶à£¬xyyz²»ÊÇA1µÄ³ÉÔ±¡£Î¥·´±ÃÒýÀíµÄÌõ¼þ1£¬Ã¬¶Ü¡£ ¡àA1²»ÊÇÕýÔòµÄ¡£
b. A2={www | w?{a,b}*}.
Ö¤Ã÷£º¼ÙÉèA2ÊÇÕýÔòµÄ¡£ÉèpÊDZÃÒýÀí¸ø³öµÄ¹ØÓÚA2µÄ±Ã³¤¶È¡£
ÁîS=ababab,
¡ßSÊÇA2µÄÒ»¸ö³ÉÔ±ÇÒSµÄ³¤¶È´óÓÚp£¬ËùÒÔ±ÃÒýÀí±£Ö¤S¿É±»·Ö³É3¶ÎS=xyzÇÒÂú×ã±ÃÒýÀíµÄ3¸öÌõ¼þ¡£¸ù¾ÝÌõ¼þ3£¬yÖÐÖ»º¬a£¬ËùÒÔxyyzÖеÚÒ»¸öaµÄ¸öÊý½«±ÈºóÁ½¸öaµÄ¸öÊý¶à£¬¹Êxyyz²»ÊÇA2µÄ³ÉÔ±¡£Î¥·´±ÃÒýÀíµÄÌõ¼þ1£¬Ã¬¶Ü¡£ ¡àA2²»ÊÇÕýÔòµÄ¡£
p
p
p
pp
p
nn
n
1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0,1 0,1 0,1 c. A3={a | n?0}.(ÔÚÕâÀa±íʾһ´®2¸öa .)
Ö¤Ã÷£º¼ÙÉèA3ÊÇÕýÔòµÄ¡£ÉèpÊDZÃÒýÀí¸ø³öµÄ¹ØÓÚA3µÄ±Ã³¤¶È¡£
ÁîS= a2£¬
¡ßSÊÇA2µÄÒ»¸ö³ÉÔ±ÇÒSµÄ³¤¶È´óÓÚp£¬ËùÒÔ±ÃÒýÀí±£Ö¤S¿É±»·Ö³É3¶ÎS=xyzÇÒÂú×ã±ÃÒýÀíµÄ3¸öÌõ¼þ¡£¼´¶ÔÈÎÒâµÄi?0£¬xyiz¶¼Ó¦ÔÚA3ÖУ¬ÇÒxyizÓëxyi+1zµÄ³¤¶È¶¼Ó¦ÊÇ2µÄÃÝ. ¶øÇÒxyi+1zµÄ³¤¶ÈÓ¦ÊÇxyizµÄ³¤¶ÈµÄ2±¶(n?1)¡£ÓÚÊÇ¿ÉÒÔÑ¡Ôñ×ã¹»´óµÄi£¬Ê¹µÃ|xyiz|=2>p. µ«ÊÇ|xyi+1z|-|xyiz|=|y|?p. ¼´|xyi+1z|<2, ì¶Ü¡£ ¡àA3²»ÊÇÕýÔòµÄ¡£
1.46 Ö¤Ã÷£º
a) ¼ÙÉè{010|m,n¡Ý0}ÊÇÕýÔòµÄ£¬pÊÇÓɱÃÒýÀí¸ø³öµÄ±Ã³¤¶È¡£È¡s£½010£¬q>0¡£
ÓɱÃÒýÀíÌõ¼þ3Öª£¬|xy|¡Üp£¬¹ÊyÒ»¶¨ÓÉ0×é³É£¬´Ó¶ø×Ö·û´®xyyzÖÐ1Ç°ºó0µÄÊýÄ¿²»Í¬£¬¼´xyyz²»ÊôÓÚ¸ÃÓïÑÔ£¬ÕâÓë±ÃÒýÀíì¶Ü¡£ËùÒÔ¸ÃÓïÑÔ²»ÊÇÕýÔòµÄ¡£
b) ¼ÙÉè{0n1n|n¡Ý0}µÄ²¹¼¯ÊÇÕýÔòµÄ£¬Ôò¸ù¾ÝÕýÔòÓïÑÔÔÚ²¹ÔËËãÏ·â±Õ¿ÉµÃ{0n1n|n¡Ý0}ÊÇÕýÔòµÄ£¬ÕâÓëÒÑ֪ì¶Ü£¬¹Ê¼ÙÉè²»³ÉÁ¢¡£ËùÒÔ¸ÃÓïÑÔ²»ÊÇÕýÔòµÄ¡£
c) ¼Çc={0m1n|m¡Ùn}£¬©´cΪcµÄ²¹¼¯£¬©´c¡É0*1*={0n1n|n¡Ý0}£¬ÒÑÖª{0n1n|n¡Ý0}²»ÊÇÕýÔòµÄ¡£Èô ©´cÊÇÕýÔòµÄ£¬ÓÉÓÚ0*1*ÊÇÕýÔòµÄ£¬ÄÇô©´c¡É0*1*ҲӦΪÕýÔòµÄ¡£ÕâÓëÒÑ֪ì¶Ü£¬ËùÒÔ ©´c²»ÊÇÕýÔòµÄ¡£ÓÉÕýÔòÓïÑÔÔÚ²¹ÔËËãϵķâ±ÕÐÔ¿ÉÖªcÒ²²»ÊÇÕýÔòµÄ¡£
d) {w | w?{0,1}*²»ÊÇÒ»¸ö»ØÎÄ}µÄ²¹¼¯ÊÇ{w | w?{0,1}*ÊÇÒ»¸ö»ØÎÄ}£¬ÉèÆäÊÇÕýÔòµÄ£¬ÁîpÊÇÓɱÃÒýÀí¸ø³öµÄ±Ã³¤¶È¡£È¡×Ö·û´®s=010£¬ÏÔÈ»sÊÇÒ»¸ö»ØÎÄÇÒ³¤¶È´óÓÚp¡£ÓɱÃÒýÀíÌõ¼þ3Öª|xy|¡Üp£¬¹ÊyÖ»ÄÜÓÉ0×é³É¡£¶øxyyz²»ÔÙÊÇÒ»¸ö»ØÎÄ£¬ÕâÓë±ÃÒýÀíì¶Ü¡£ËùÒÔ{w | w?{0,1}ÊÇÒ»¸ö»ØÎÄ}²»ÊÇÕýÔòµÄ¡£ÓÉÕýÔòÓïÑÔÔÚ²¹ÔËËãϵķâ±ÕÐÔ¿ÉÖª{w | w?{0,1}²»ÊÇÒ»¸ö»ØÎÄ}Ò²²»ÊÇÕýÔòµÄ¡£
**
pq
p
n
mn
pq
p
n+1
n
n
p
2n2n
n