close

Se connecter

Se connecter avec OpenID

( : G1 @ L1 L1 L(G)= . : L1 > : > > > . @ : (b > G1 . : @ a > > > @ > G1

IntégréTéléchargement
‫‪ (1‬ﻓﺮض ﻛﻨﻴﺪ ‪:‬‬
‫ﻳﻚ ﮔﺮاﻣﺮ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻣﺜﻞ ‪ G1‬ﺑﺮاي زﺑﺎن ‪ L1‬ﻃﺮاﺣﻲ ﻛﻨﻴﺪ ﻛﻪ‪. L(G)= L1‬‬
‫ﺣﻞ ‪ :‬ﻣﺎ ﻓﺮض ﻣﻲ ﻛﻨﻴﻢ ﻛﻪ ‪ L1‬از دو ﺑﺨﺶ ‪ L11‬و‪ L12‬ﺗﺸﻜﻴﻞ ﺷﺪه اﺳﺖ ‪:‬‬
‫‪ L11‬ﺧﻮدش ﺑﻪ دو ﺑﺨﺶ ‪ La<bc‬و‪ La>bc‬ﺗﻘﺴﻴﻢ ﻣﻲ ﺷﻮد ‪.‬‬
‫ﻣﺮاﺣﻞ ﻛﺎر روي رﺷﺘﻪ ﻳﻪ ﺷﻜﻞ زﻳﺮ اﺳﺖ ‪:‬‬
‫‪ (b‬ﻧﺸﺎن دﻫﻴﺪ‪ G1‬ﻣﺒﻬﻢ اﺳﺖ ‪.‬‬
‫ﺣﻞ‪:‬‬
‫رﺷﺘﻪ اي ﻣﺜﻞ ‪ a‬داراي دو درﺧﺖ ﺗﺠﺰﻳﻪ در ‪ G1‬اﺳﺖ‪ .‬ﺑﻨﺎﺑﺮ اﻳﻦ‪ G1‬ﻣﺒﻬﻢ اﺳﺖ ‪.‬‬
‫‪(2‬‬
‫‪ ( a‬ﻣﻲ داﻧﻴﻢ ﻛﻪ زﺑﺎن زﻳﺮ‪:‬‬
‫ﻳﻚ زﺑﺎن ﻣـﺴﺘﻘﻞ از ﻣـﺘﻦ اﺳـﺖ وﻟـﻲ زﺑـﺎن ﻣﻌـﻴﻦ ﻣـﺴﺘﻘﻞ از ﻣـﺘﻦ ﻣﻌـﻴﻦ ﻧﻴـﺴﺖ ‪ .‬آﻳـﺎ زﺑـﺎن زﻳـﺮ‬
‫ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ ؟‬
‫ﺣﻞ ‪:‬‬
‫ﺑﻠﻪ ‪ .‬ﻣﺎ ﻣﻲ ﺗﻮاﻧﻴﻢ اﻳﻦ زﺑﺎن را ﺑﺎ ﻳﻚ ‪ PDA‬آﺗﻮﻣﺎﺗﺎي ﭘﺸﺘﻪ اي ﻳﺎ ﻳـﻚ ﮔﺮاﻣـﺮ ﻣـﺴﺘﻘﻞ از ﻣـﺘﻦ ﻧـﺸﺎن‬
‫دﻫﻴﻢ ‪.‬‬
‫ﮔﺰﻳﻨﻪ ﮔﺮاﻣﺮ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ در اﻳﻨﺠﺎ ﻗﺎﺑﻞ ﻓﻬﻢ ﺗﺮ اﺳﺖ ‪ .‬ﮔﺮاﻣﺮ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻃﺮاﺣـﻲ ﺷـﺪه ﺑـﺎ اﻳـﻦ‬
‫واﻗﻌﻴﺖ ﻧﺸﺎن داده ﻣﻲ ﺷﻮد ﻛﻪ ﻳﻚ رﺷﺘﻪ ﻣﺘﻘﺎرن ﻧﻴﺴﺖ ‪ ،‬ﺑﻨﺎﺑﺮاﻳﻦ ﺑﺎﻳﺪ ﻳﻚ ﻧﻘﻄﻪ اي ﺑﺎﺷﺪ ﻛﻪ ﺧﺎﺻﻴﺖ‬
‫ﻣﺘﻘﺎرن ﺑﻮدن در آن وﺟﻮد ﻧﺪاﺷﺘﻪ ﺑﺎﺷﺪ =< ﺑﺎﻳﺪ ﻳﻚ ﺳﻤﺒﻞ ﺑﺎﺷﺪ ﻛﻪ ﺑﺎﻋﺚ ﺷـﻮد ﻛـﻪ رﺷـﺘﻪ ﻧﺎﻣﺘﻘـﺎرن‬
‫ﺷﻮد ‪.‬‬
‫و ‪ M‬ﻣﺘﻨﺎﺳﺐ ﻧﺒﻮدن را اﻳﺠﺎد ﻣﻲ ﻛﻨﺪ ‪:‬‬
‫اﮔﺮ ﻳﻜﻲ از ﺣﺮوف ﺑﺎﻫﻢ ﻧﺎﻣﺘﻘﺎرن ﺑﺎﺷﺪ ﻣﺎ دﻳﮕﺮ ﺑﻪ ﻣﺮﻛﺰ رﺷﺘﻪ ﺗﻮﺟﻬﻲ ﻧﻤﻲ ﻛﻨﻴﻢ ‪:‬‬
‫ﭘﺲ ‪ N‬در *∑ ﺗﻮﻟﻴﺪ ﻣﻲ ﺷﻮد ‪.‬‬
‫‪ (b‬زﺑﺎن زﻳﺮ ﻣﻔﺮوض اﺳﺖ ‪:‬‬
‫آﻳﺎ ‪ L23‬ﻳﻚ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ ؟‬
‫‪L23= ∑*- L22‬‬
‫ﺣﻞ ‪:‬‬
‫ﺧﻴﺮ – دارﻳﻢ ﻛﻪ ‪:‬‬
‫اﮔﺮ ‪ L23‬ﻳﻚ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﺑﺎﺷﺪ ‪ .‬اﻳﻦ ﺑﻪ اﻳﻦ ﻣﻌﻨﻲ اﺳﺖ ﻛﻪ }‪ {anbncn : n≥0‬ﻫﻢ ﻣـﺴﺘﻘﻞ از‬
‫ﻣﺘﻦ اﺳﺖ از آﻧﺠﺎ ﻛﻪ زﺑﺎﻧﻬﺎي ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻧﺴﺒﺖ ﺑﻪ اﺷﺘﺮاك ﺑﺎ زﺑﺎﻧﻬﺎي ﻣـﻨﻈﻢ ﺑـﺴﺘﻪ اﻧـﺪ ‪ .‬اﻣـﺎ ﻣـﻲ‬
‫داﻧﻴﻢ ﻛﻪ }‪ {anbncn : n≥0‬ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻧﻴﺴﺖ ‪ .‬ﺑﻨﺎﺑﺮاﻳﻦ ‪ L23‬ﻧﻴﺰ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻧﻴﺴﺖ ‪.‬‬
‫‪ (C‬ﺣﺪس زﻳﺮ را در ﻧﻈﺮ ﺑﮕﻴﺮﻳﺪ ‪:‬‬
‫اﮔﺮ ‪ L‬ﻋﻀﻮي از*∑ ﺑﺎﺷﺪ و ‪ L‬ﻳﻚ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﺑﺎﺷﺪ و‪ L‬ﻳﻚ زﺑﺎن ﻣـﺴﺘﻘﻞ از ﻣـﺘﻦ ﻣﻌـﻴﻦ‬
‫ﻧﺒﺎﺷﺪ ﺑﻨﺎﺑﺮاﻳﻦ ‪ L‬ﻳﻚ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻧﻴﺴﺖ ‪) .‬ﺑﺮاي ﻫـﺮ زﺑـﺎن ﻣـﺴﺘﻘﻞ از ﻣـﺘﻦ و ‪ L‬ﻳـﻚ زﺑـﺎن‬
‫ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻣﻌﻴﻦ ﻧﺒﺎﺷﺪ ﭘﺲ ‪ L‬ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻧﻴﺴﺖ‪( .‬‬
‫آﻳﺎ ﺣﺪس درﺳﺖ اﺳﺖ ؟‬
‫ﺣﻞ‪:‬‬
‫ﺧﻴﺮ – اﻳﻦ ﺣﺪس ﻏﻠﻂ اﺳﺖ ‪ .‬اﻳﻦ ﺣﻘﻴﻘﺖ ﺗﻮﺳﻂ ‪ L21‬ﺗﺤﺮﻳﻒ ﺷﺪه اﺳﺖ ‪.‬در ﺳﺌﻮال ‪ 2‬ﺑﺨﺶ ‪ a‬اﺛﺒﺎت‬
‫ﻛﺮدﻳﻢ ﻛﻪ ‪ L21‬ﻳﻚ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ وﻟﻲ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻣﻌﻴﻦ ﻧﻴﺴﺖ و دﻳﺪﻳﻢ ﻛـﻪ ‪L21‬‬
‫ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﺑﻮد ‪.‬‬
‫‪ (٣‬ﻓﺮض ﻛﻨﻴﺪ ‪ G3‬ﻳﻚ ﮔﺮاﻣﺮ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ و‬
‫ﺣﺎل ﺑﺮاي رﺷﺘﻪ اي ﻣﺜﻞ ‪ aabbab‬اﻳﻦ ﺑﺨﺶ ﻫﺎ راﺑﻴﺎﺑﻴﺪ ‪:‬‬
‫‪ ( a‬ﻳﻚ اﺷﺘﻘﺎق ﭼﭗ ﺑﻴﺎﺑﻴﺪ ‪.‬‬
‫‪ ( b‬ﻳﻚ اﺷﺘﻘﺎق راﺳﺖ ﺑﻴﺎﺑﻴﺪ ‪.‬‬
‫‪ ( c‬ﻳﻚ درﺧﺖ ﺗﺠﺰﻳﻪ ‪:‬‬
‫(‬
‫آﺗﻮﻣﺎﺗﺎي ﭘﺸﺘﻪ اي زﻳﺮ را در ﻧﻈﺮ ﺑﮕﻴﺮﻳﺪ ‪:‬‬
‫‪ (a‬زﺑﺎن )‪ L(M4‬ﭼﻴﺴﺖ ؟‬
‫ﺣﻞ‪:‬‬
‫‪ (b‬ﺑﺮاي آﺗﻮﻣﺎﺗﺎي ﭘﺸﺘﻪ اي ‪ LFS(M) : M‬ﻳﻚ زﺑﺎن اﺳﺖ ﻛﻪ ﺗﻮﺳﻂ ﺣﺎﻟﺖ ﭘﺎﻳﺎﻧﻲ ﭘﺬﻳﺮﻓﺘـﻪ ﻣـﻲ ﺷـﻮد‪.‬‬
‫آن زﺑﺎن ﭼﻴﺴﺖ ؟‬
‫ﺣﻞ ‪:‬‬
‫‪ (c‬ﺑﺮاي آﺗﻮﻣﺎﺗﺎي ﭘﺸﺘﻪ اي ‪ LES(M) : M‬ﻳﻚ زﺑﺎن اﺳﺖ ﻛﻪ ﺗﻮﺳﻂ ﺣﺎﻟﺖ ﭘﺸﺘﻪ ﺧـﺎﻟﻲ ﭘﺬﻳﺮﻓﺘـﻪ ﻣـﻲ‬
‫ﺷﻮد‪ .‬آن زﺑﺎن ﭼﻴﺴﺖ ؟‬
‫ﺣﻞ ‪:‬‬
‫‪ (d‬ﻳــﻚ ‪ PDA‬ﺑﻨــﺎم ‪ MES‬ﺑﻴﺎﺑﻴــﺪ ﻛــﻪ ) ‪ LES( MES ) = LFS( M4‬در ﻧﺘﻴﺠــﻪ‪ MES‬ﺑﺎﻳــﺪ‬
‫)‪LFS(M4‬را ﺑﺎ ﭘﺸﺘﻪ ﺧﺎﻟﻲ ﺑﭙﺬﻳﺮد ‪.‬‬
‫ﺣﻞ ‪:‬‬
‫ﺑﺮاي ﺳﺎﺧﺘﻦ ‪ MES‬ﺑﺎ ﻳﻚ ﺣﺎﻟﺖ ﺷﺮوع ﺟﺪﻳﺪ ﺑﻨﺎم ‪ qstart‬ﻳﻚ ﺣﺎﻟﺖ ﺟﺪﻳﺪ ﻛﻪ ﺑﻌﻨـﻮان ﺣﺎﻟـﺖ ﭘـﺸﺘﻪ‬
‫ﺧﺎﻟﻲ ‪ qempty‬اﺳﺘﻔﺎده ﻣﻴﺸﻮد اﺿﺎﻓﻪ ﺷﻮد ‪.‬‬
‫وﻗﺘﻲ ﺑﻪ ﺣﺎﻟﺖ ﺷﺮوع ‪ M4‬ﻣﻲ روﻳﻢ ﻣﺎ ﻳﻚ ﻧﻤﺎد ﺟﺪﻳﺪ ﺑﻪ ﻋﻨﻮان ﺗﻪ ﭘﺸﺘﻪ ‪ Z0‬در ﭘﺸﺘﻪ ﻗﺮار ﻣﻲ دﻫـﻴﻢ ‪،‬‬
‫ﺑﺎﻻﺧﺮه ‪ ε‬را ﻛﻪ ﻳﻚ اﻧﺘﻘﺎل از ‪ ) q2‬ﺣﺎﻟﺖ ﭘﺎﻳﺎﻧﻲ‪ M4‬اﺳﺖ ( ﺑﻪ‪ qempty‬وﺻﻞ ﻣﻲ ﻛﻨﻴﻢ ) ﺑﺎ ﻳﻚ ‪ ε‬ﻣﺎ ‪q1‬‬
‫را ﺑﻪ ‪ qempty‬وﺻﻞ ﻣﻲ ﻛﻨﻴﻢ ( ‪.‬‬
‫ﭘﺲ ﻣﺎ اﻧﺘﻘﺎل ﻫﺎﻳﻲ را ﻫﻢ ﻛﻪ ﻣﻨﺠﺮ ﺑﻪ اﻳﺠﺎد ﭘﺸﺘﻪ ﺧﺎﻟﻲ ﻣﻲ ﺷﻮد دارﻳﻢ‪.‬‬
‫ﺣﺎﻻ ﻧﺸﺎﻧﻪ ﻫﺎﻳﻲ از ﭘﺸﺘﻪ ﻗﺒﻠﻲ را در ﭘﺸﺘﻪ ﺣﺎﺻﻞ از زﺑﺎن‪ MES‬ﻗﺮار ﻣﻲ دﻫﻴﻢ ‪.‬‬
‫ﻣﻲ ﺗﻮان ﻫﺮ وﻗﺖ در ‪ q2‬ﺑﺎﺷﻴﻢ ﺑﻪ‪ qempty‬ﺑﺮوﻳﻢ ‪.‬‬
‫ﺑﻪ ﻣﺤﺾ اﻳﻨﻜﻪ در ﺣﺎﻟﺖ ‪ qempty‬ﭘﺸﺘﻪ ﺧﺎﻟﻲ ﺷﻮد رﺷﺘﻪ ﺗﻮﺳﻂ زﺑﺎن ﭘﺬﻳﺮﻓﺘﻪ ﻣﻲ ﺷﻮد ‪.‬‬
‫‪ (5‬ﻋﺒﺎرت ﻣﻨﻈﻢ )‪ l(a(a U b)* a U a‬را در ﻧﻈﺮ ﺑﮕﻴﺮﻳﺪ ﻳﻚ ﮔﺮاﻣﺮ ﻣﻨﻈﻢ ﺑﺮاي اﻳﻦ ﻋﺒﺎرت ارﺋﻪ دﻫﻴﺪ ‪.‬‬
‫ﺣﻞ‪:‬‬
‫‪(6‬ﻧﺸﺎن دﻫﻴﺪ زﺑﺎن ﻫﺎي زﻳﺮ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻣﻌﻴﻦ ﻫﺴﺘﻨﺪ ‪:‬‬
‫ﺣﻞ ‪:‬‬
‫وﻗﺘﻲ ‪ a‬در ورودي ﻇﺎﻫﺮ ﻣﻲ ﺷﻮد آﻧﻬﺎ را در ﭘﺸﺘﻪ ﻗﺮار ﻣﻲ دﻫﻴﻢ و ﺗﻌﺪاد ‪ b‬ﻫﺎ را در ﻧﻈﺮ ﻧﻤﻲ ﮔﻴـﺮﻳﻢ ‪.‬‬
‫ﺗﺎاﻳﻨﻜﻪ دوﺑﺎره در ورودي ‪ a‬ﺑﺒﻴﻨﻴﻢ ﻛﻪ در اﻳﻦ ﺻﻮرت ﺗﻤﺎﻣﻲ ‪ a‬ﻫﺎ را ﻳﻜﻲ ﻳﻜﻲ از ﭘﺸﺘﻪ ﺧﺎرج ﻣﻲ ﻛﻨﻴﻢ‪.‬‬
‫ﻓﺮض ﻛﻨﻴﺪ ‪:‬‬
‫ﻣﻲ ﺗﻮان در اﻳﻨﺠﺎ ﻳﻚ آﺗﻮﻣﺎﺗﺎي ﭘﺸﺘﻪ اي ﻣﻌﻴﻦ ﺳﺎﺧﺖ اﻣﺎ ﻳﻚ روش ﺳﺎده ﺗﺮ اﻳﻦ اﺳﺖ ﻛـﻪ ‪ L6b‬را ﺑـﻪ‬
‫اﻳﻦ ﺷﻜﻞ در ﻧﻈﺮ ﺑﮕﻴﺮﻳﻢ ‪:‬‬
‫دﻳﺪﻳﻢ ﻛﻪ ‪ L6a‬ﻳﻚ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻣﻌﻴﻦ اﺳﺖ و ﻣﻲ داﻧﻴﻢ ﻛﻪ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻣﻌﻴﻦ ﻧـﺴﺒﺖ‬
‫ﺑﻪ ﻋﻤﻞ اﺟﺘﻤﺎع ﺑﺎ زﺑﺎن ﻣﻨﻈﻢ ﺑﺴﺘﻪ اﺳﺖ ﺑﻨﺎﺑﺮاﻳﻦ ‪ L6b‬زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻣﻌﻴﻦ ﺧﻮاﻫﺪ ﺑﻮد ‪.‬‬
‫)‪ K1‬و‪ K2‬اﺧﺘﻴﺎري ﻫﺴﺘﻨﺪ و ﻧﺸﺎﻧﻪ زﻳﺮ ﺑﺮاﺑﺮ ﺗﻌﺪاد ‪ a‬ﻫﺎ در رﺷﺘﻪ ‪ w‬اﺳﺖ ‪.‬‬
‫ﺣﺎﻟﺖ ﺷﺮوع = ‪ s‬و ﺣﺎﻟﺖ ﭘﺎﻳﺎﻧﻲ =} ‪{ f‬‬
‫ﺷﺮوع ‪ :‬ﺑﺎ ﮔﺬاﺷﺘﻦ ﻧﺸﺎﻧﻪ ﻛﻒ ﭘﺸﺘﻪ در ﺑﺎﻻي ﭘﺸﺘﻪ ‪.‬‬
‫ﺑﻪ ﺗﻌﺪاد ‪ K1‬ﺗﺎ ‪ a‬روي ﭘﺸﺘﻪ ﺑﻪ ازاي ﻫﺮ ورودي ‪ a‬ﻗﺮار ﻣﻲ دﻫﻴﻢ ‪.‬‬
‫ﺑﻪ ﺗﻌﺪاد ‪K2‬ﺗﺎ ‪b‬روي ﭘﺸﺘﻪ ﺑﻪ ازاي ﻫﺮ ورودي ‪ b‬ﻗﺮار ﻣﻲ دﻫﻴﻢ ‪.‬‬
‫اﻧﺘﻘﺎل ﺧﺮوﺟﻲ ‪:‬‬
‫ﺑﺮاي ﻫﺮ ورودي ‪ a‬ﺑﻪ اﻧﺪازه ‪ K1‬ﺗﺎ ‪ b‬از ﭘﺸﺘﻪ ﺧﺎرج ﻛﻨﻴﺪ ‪ .‬اﻳﻦ زﻣﺎﻧﻲ اﻧﺠـﺎم ﻣـﻲ ﺷـﻮد ﻛـﻪ ‪ K1‬ﺗـﺎ ﻳـﺎ‬
‫ﺑﻴﺸﺘﺮ ‪ b‬در ﭘﺸﺘﻪ وﺟﻮد داﺷﺘﻪ ﺑﺎﺷﺪ ‪.‬‬
‫ﻧﻜﺘﻪ ‪ :‬ﻫﻴﭻ ﻳﻚ از اﻧﺘﻘﺎل ﻫﺎي ﺑﺎﻻ ﺳﺎزﮔﺎر ﻧﻴﺴﺘﻨﺪ ‪.‬‬
‫اﻧﺘﻘﺎل ﺧﺮوﺟﻲ ‪:‬‬
‫ﺑﺮاي ﻫﺮ ورودي ‪ b‬ﺑﻪ اﻧﺪازه ‪ K2‬ﺗﺎ ‪ a‬از ﭘﺸﺘﻪ ﺧﺎرج ﻛﻨﻴﺪ ‪ .‬اﻳﻦ زﻣﺎﻧﻲ اﻧﺠـﺎم ﻣـﻲ ﺷـﻮد ﻛـﻪ ‪ K2‬ﺗـﺎ ﻳـﺎ‬
‫ﺑﻴﺸﺘﺮ ‪ a‬در ﭘﺸﺘﻪ وﺟﻮد داﺷﺘﻪ ﺑﺎﺷﺪ ‪.‬‬
‫ﻧﻜﺘﻪ ‪ :‬ﻫﻴﭻ ﻳﻚ از اﻧﺘﻘﺎل ﻫﺎي ﺑﺎﻻ ﺳﺎزﮔﺎر ﻧﻴﺴﺘﻨﺪ ‪.‬‬
‫ﺑﺎﺑﺮداﺷﺘﻦ ﻧﻤﺎد ﺗﻪ ﭘﺸﺘﻪ ﻋﻤﻠﻴﺎت ﺗﻤﺎم ﻣﻲ ﺷﻮد ‪.‬‬
‫‪ (7‬ﻛﺪاﻣﻴﻚ از زﺑﺎن ﻫﺎي زﻳﺮ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻫﺴﺘﻨﺪ ؟‬
‫‪ La‬ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ ‪ .‬ﻣﺎ ﻧﻴﺎز ﻧﺪارﻳﻢ ﻛﻪ ‪ v‬و ‪ w‬را ﺗﺸﺨﻴﺺ دﻫﻴﻢ ‪.‬ﻫﻤﻪ زﺑﺎن ﻫﺎ ﺑﻪ ﻣـﺎ ﻣـﻲ ﮔﻮﻳﻨـﺪ‬
‫ﻛﻪ ﺗﻌﺪاد ﻧﺸﺎﻧﻪ ﻫﺎي ﺳﻤﺖ راﺳﺖ ‪ c‬ﺑﺎﺳﺪ دو ﺑﺮاﺑﺮ ﺗﻌﺪاد ﻧﺸﺎﻧﻪ ﻫﺎ در ﺳﻤﺖ ﭼﭗ ‪ c‬ﺑﺎﺷﺪ ‪.‬‬
‫ﻣﻲ ﺗﻮان ﻧﺸﺎن داد ﻛﻪ ‪ La‬ﻳﻚ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ ‪ .‬اﺳﻦ ﻛﺎر را ﺑﺎ ﺳﺎﺧﺘﻦ ﻳﻚ ﮔﺮاﻣﺮ ﻣـﺴﺘﻘﻞ از‬
‫ﻣﺘﻦ ﺑﺮاي آن اﻧﺠﺎم ﻣﻲ دﻫﻴﻢ ‪.‬‬
‫‪ Lb‬زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻧﻴـﺴﺖ ‪ .‬ﺑـﺮاي ﻧـﺸﺎن دادن اﻳـﻦ ﻣﻮﺿـﻮع اﺑﺘـﺪا اﻳـﻦ زﺑـﺎن را ﺑـﺎ *‪a*ca*ca‬‬
‫اﺷﺘﺮاك ﻣﻲ ﮔﻴﺮﻳﻢ و ﺑﻪ ﻋﻨﻮان زﺑﺎن ‪ Lb1‬ﻣﻲ ﺷﻨﺎﺳﻴﻢ ﻛﻪ ‪:‬‬
‫ﺑﺎ ﻳﻚ ﺑﺮرﺳﻲ ﻟﻢ ﺗﺰرﻳﻖ ﺑﺮاي }‪ {anbncn : n≥0‬ﻛﺎﻓﻲ اﺳﺖ ﺗـﺎ ﻧـﺸﺎن دﻫـﺪ ‪ Lb1‬ﻧﻤـﻲ ﺗﻮاﻧـﺪ زﺑـﺎن‬
‫ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﺑﺎﺷﺪ ‪ .‬از آﻧﺠﺎ ﻛﻪ زﺑﺎﻧﻬﺎي ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﺗﺤﺖ اﺷﺘﺮاك ﺑﺎ زﺑﺎﻧﻬﺎي ﻣﻨﻈﻢ ﺑﺴﺘﻪ ﻫـﺴﺘﻨﺪ‬
‫ﭘﺲ ‪ Lb1‬ﻧﻤﻲ ﺗﻮاﻧﺪ زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﺑﺎﺷﺪ ‪.‬‬
‫‪ Lc‬زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ ‪ .‬ﻣﻲ ﺗﻮان اﻳﻦ ﻣﻮﺿﻮع را ﺑﺎ اﻳﺠﺎد ﻳﻚ ﮔﺮاﻣﺮ ﻣﺸﺘﻘﻞ از ﻣـﺘﻦ ﻳـﺎ ﺳـﺎﺧﺖ‬
‫ﻳﻚ آﺗﻮﻣﺎﺗﺎي ﭘﺸﺘﻪ اي رﺑﺎي زﺑﺎن ﻧﺸﺎن داد ‪ .‬ﻣﺎ از اﻳﻦ ﺣﻘﻴﻘﺖ اﺳﺘﻔﺎده ﻣﻲ ﻛﻨـﻴﻢ ﻛـﻪ ‪ Lc‬اﺟﺘﻤـﺎع دو‬
‫زﺑﺎن ﻣﺴﺘﻘﻞ از ﻣﺘﻦ اﺳﺖ ‪.‬‬
‫اﻳﻦ زﺑﺎن ﺗﻬﻲ اﺳﺖ ﭘﺲ ﻧﻴﺎز ﺑﻪ ﺑﺮرﺳﻲ ﻧﺪارد وﻟﻲ دوﺳﺖ ﻗﺪﻳﻤﻲ ﻣﺎ}‪{anbncn : n≥0‬ﻛﻪ ﺑـﺪون ﻋﻤـﻞ‬
‫اﺷﺘﺮاك ﺟﺰﺋﻲ از زﺑﺎن اﺳﺖ در واﻗﻊ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ ﻧﻴﺴﺖ ‪.‬‬
‫اﻳﻦ زﺑﺎن ﺣﺘﻲ دوﺳﺘﻲ ﻗﺪﻳﻤﻲ ﺗﺮ از زﺑﺎن ﻗﺒﻞ اﺳﺖ )*∑( ﻛﻪ ﺑﻄﻮ واﺿﺢ ﻣﺴﺘﻘﻞ از ﻣﺘﻦ و ﻣﻨﻈﻢ اﺳﺖ ‪.‬‬
‫‪ (8‬ﻳﻚ آﺗﻮﻣﺎﺗﺎي ﻣﺘﻨﺎﻫﻲ ﺑﺮاي ﭘﺬﻳﺮش زﺑﺎن زﻳﺮ ﻃﺮاﺣﻲ ﻛﻨﻴﺪ ‪.‬‬
‫ﺑﺮاي داﻧﻠﻮد ﻛﺘﺎب ﻫﺎي ﺑﻴﺸﺘﺮ ﺑﻪ آدرس ‪ wwww.Arsanjan.blogfa.com‬ﻣﺮاﺟﻌﻪ ﻛﻨﻴﺪ‪.‬‬
Auteur
Document
Catégorie
Uncategorized
Affichages
5
Taille du fichier
290 KB
Étiquettes
1/--Pages
signaler