نظریه زبان ها و ماشین ها

نظریه زبانها و ماشینها تهيه کننده :سیده فاطمه نورانی گروه :کامپيوتر شناسنامه منبع عنوان منبع :نظریه زبانها و ماشینها مترجم :مهندس سید حجت اهلل جلیلی انتشارات :پژوهشهای فرهنگی()1380 منبع اصلي: ‏Languages & machines ‏Written By: Thomas A.Sudkamp گروه کامپيوتر نظریه زبانها و ماشینها صفحه2 : جايگاه درس در رشته کامپيوتر ‏ ‏ ‏ ‏ ‏ ضرورت اين درس: ضرورت نياز به زبانهای سطح باال ضرورت ترجمه برنامه های نوشته شده با زبان سطح باال به برنامه به زبان ماشين تنوع زبانهای برنامه نويسی سطح باال دروس پيش نياز: نوع درس: تعدادکل ساعات تدريس: تعداد جلسات تدريس: گروه کامپيوتر نظریه زبانها و ماشینها صفحه3 : فصل اول :ریاضیات مقدماتی اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: مفاهیم نمادگذاری و مفهوم تابع نظریه مجموعه ها مفهوم استقراء ریاضی گراف و انواع آن گروه کامپيوتر نظریه زبانها و ماشینها صفحه4 :  x 1-1نمادگذاری نماد ┌ :┐xاشاره به کوچکترین عدد صحیح بزرگتر یا مساوی عدد حقیقی xدارد3-=┐3.7-┌ . ┌5 =┐4.5 نماد ┌ ┐xرا جزء صحیح باالی xمی نامیم. نماد └ :┘xاشاره به بزرگترین عدد صحیح کوچکتر یا مساوی عدد حقیقی xدارد4-=┘3.7-└ . └4 =┘4.5 نماد └ ┘xرا جزء صحیح پایین xمی نامیم. گروه کامپيوتر نظریه زبانها و ماشینها صفحه5 :  1-2توابع تاب\ع :fتشکی\ل شده از ی\ک متغی\ر ب\ا قاعده و قانون م\ی باش\د ک\ه به ازاء ی\ک مقدار ، xمقدار منحص\ر ب\ه فردی را ب\ه ) f(xنس\بت می دهد. نمودار ی\ک تاب\ع :مجموع\ه ای اس\ت از کلی\ه زوجهای مرت\ب که بوسیله تابع تعیین می شوند. دامن\ه ی\ک تابع :مجموع\ه مقادیری اس\ت ک\ه تابع به ازاء آنه\ا تعریف می شود گروه کامپيوتر نظریه زبانها و ماشینها صفحه6 :  1-2توابع تابع جامع :تابعی که از Xبه Yیک رابطه دودویی روی X*Yرا داراست. تابع جزئی :رابطه بین X*Yاست وقتی که ]єf [x,y2و ]єf [x,y1 تابع یک به یک :تابعی که در آن هر عنصر xبه یک عنصر مجزا در برد تصویر شود. تابع f:X Yپوشاست اگر که برد fکل مجموعهYباشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه7 :  1-3نظریه مجموعه ها نمادهای مجموعه : نماد єبه معنای عضویت است .بطوریکه x є Xمشخص می کند که xیک عضو یا عنصر مجموعه Xاست. از دو براکت{ } برای تعریف یک مجموعه استفاده می شود. } X= { 1,2,3 مجموعه هایی که تعداد زیاد یا تعداد نامتناهی عضو دارند بایستی به صورت ضمنی تعریف شوند. {}n l n=m² for some natural number m گروه کامپيوتر نظریه زبانها و ماشینها صفحه8 :  1-3نظریه مجموعه ها یک مجموعه با اعضایش مشخص می شود. زیر مجموعه :مجموعه Yزیر مجموعهXاست به طوری که Y Xا\گر هر ع\ضو Yع\ضویاز Xن\\یز ب\\اشد. اگر Yیک زیر مجموعه از Xباشد و X≠Yآنگاه به Yیک زیر مجموعه کامل Xمیگوئیم. گروه کامپيوتر نظریه زبانها و ماشینها صفحه9 :  1-3نظریه مجموعه ها اجتماع دو مجموعه به صورت زیر تعریف می شود: ‏XυY = { z l z є X or z є }Y اختالف دو مجموعه به صورت زیر تعریف می شود: }X-Y = { z l z є X and z є Y مکمل Xنسبت به Uمجموعه عناصری در Uاست که در Xنمی باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه10 :  1-4استقراء ریاضی مفاهیم مورد استفاده در استقراء ریاضی پایه استقراء :عبارت به ازاء (n=1یا هر مقدار اولیه دیگر) درست است. فرض استقراء :عبارت برای هر عدد دلخواه (n≥1یا هر مقدار اولیه دیگر) درست است. گام استقراء :اگر عبارت به ازاء nدرست است ،آنگاه به ازاء n+1 نیز درست می باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه11 :  1-4استقراء ریاضی مثال: برای کلیه اعداد صحیح مثبت نشان می دهیم که )n(n  1 2 1 2  ..  n  )1(1 1 1 2 پایه استقراء :برای n=1داریم: فرض استقراء:فرض کنید که برای یک عدد صحیح مثبت دلخواه n )n(n  1 داریم: 1 2  ..  n  2 گام استقراء:الزم است که نشان دهیم: )(n  1)(n  2 2 گروه کامپيوتر 1 2  .. n  (n  1)  نظریه زبانها و ماشینها صفحه12 :  1-5قضایا و پیش قضای\ا قضیه در لغت به معنای گفتاری است که صحت آن باید اثبات شود. مثال:برای هر عدد صحیح ›0nداریم: )n(n  1 2 1 2  ..  n  پیش قضیه به عنوان یک قضیه کمکی برای اثبات قضایای دیگر به کار می رود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه13 :  1-6گراف ها نمایشی از یک گراف: ‏v2 1 2 6 ‏v4 3 ‏v1 4 ‏v3 5 اجزای یک گراف: دایره ها نشانگر گره ها()vertices خطوط ارتباط گره ها نشانگر لبه ()edge گروه کامپيوتر نظریه زبانها و ماشینها صفحه14 :  1-6گراف ها گراف جه\ت دار :اگ\ر ه\ر لب\ه گراف دارای جه\ت باش\د ب\ه آن گراف جهت دار()digraphمی گویند. گراف وزن دار :اگ\ر ب\ه لب\ه ه\ا مقادیری تخص\یص یافت\ه باشدب\ه آن مقادیر وزن و به آن گراف،گراف وزن دار می گوییم. مس\یر( :)pathدر ی\ک گراف جه\ت دارب\ه دنبال\ه ای از گره ه\ا ک\ه بین هر گره و گره بعدی یک لبه وجود داشته باشد گفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه15 :  1-6گراف ها چرخه( :)cycleبه مسیری که از یک گره شروع شده و به خودش باز می گردد گفته می شود. گراف چرخه ای :اگر گرافی شامل یک چرخه باشد به آن گراف چرخه ای گفته می شود. مسیر ساده :مسیری که از از یک گره دو بار عبور نکند. طول()lengthیک مسیر در یک گراف وزن دار برابر مجموع وزنهای مسیر است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه16 :  1-6گراف ها گراف بدون جهت :گرافی که لبه های ان هیچ جهتی نداشته باشند. گراف متصل:گرافی بدون جهت که بین هر دو گره دلخواه از آن یک مسیر مشخص وجود داشته باشد. درخت :یک گراف بدون جهت ،پیوسته و بدون چرخه است. درخت ریشه دار:درختی که در آن یک گره به عنوان ریشه درخت انتخاب می شود. درخت پوشا برای :Gیک زیر گراف متصل است که اوالً شامل همه گره های Gبوده و ثانی ًا یک درخت باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه17 : فصل دوم :زبان ها اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: مفاهیم رشته و زبان مشخصات زبان ها مجموعه های با قاعده گروه کامپيوتر نظریه زبانها و ماشینها صفحه18 :  2-1رشته ها و زبانها زبان :یک زبان یک مجموعه از رشته ها روی یک الفبا است. رشته :یک رشته روی یک مجموعه Xیک دنباله متناهی از عناصر Y است. الفبای زبان :به مجموعه عناصری که رشته ها از آن ساخته می شوند الفبای زبان گوئیم. رشته تهی :رشته فاقد عنصر را رشته تهی می نامیم که با λنشان می دهیم. گروه کامپيوتر نظریه زبانها و ماشینها صفحه19 :  رشته ها و زبانها2-1 : ∑* :عنصر *∑ شامل.} = ∑باشدa,b,c{ فرض کنید که 0 ط\ول: λ 1 ط\ول: a b c 2 ط\ول: aa ab ac ba bb bc ca cb cc 3 ط\ول: aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc 20 :صفحه نظریه زبانها و ماشینها گروه کامپيوتر  2-1رشته ها و زبانها یک زبان شامل رشته هایی روی الفبا است. تعریف زبان یک زبان روی یک الفبای ∑ یک زیر مجموعه از *∑ است. الحاق :الحاق ی\ک عم\ل دودوی\ی اس\ت ک\ه دو رشت\ه را به عنوان ورودی گرفت\ه و ب\ا چس\باندن آنه\ا در کنار ه\م ی\ک رشت\ه جدید ایجاد می کند .الحاق عمل اصلی در تولید رشته هاست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه21 :  2-1رشته ها و زبانها فرض کنی\د که *∑vєباشد.الحاق uو ،vک\ه ب\ه ص\ورت uvنوشت\ه می شودف ی\ک عم\ل دودوی\ی روی ∑* اس\ت ک\ه ب\ه ص\ورت زی\ر تعری\ف می شود: (iپایه :اگر length(v)=0باشد .آنگاهגּ =vو uv=uخواهد بود. ( iiگام بازگش\ت :فرض کنی\د ک\ه vی\ک رشت\ه با طول length(v)=n›0 باشد .در اینص\ورت ،ب\ه ازای برخ\ی رشت\ه های wب\ا طول n-1و a є ∑، ‏v=waو در نتیجه uv=(uw)aخواهد بود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه22 :  2-1رشته ها و زبانها مثال: فرض کنید که v=ca , u=abو w=bbباشد .در این صورت: ‏uv= abca ‏uw= cabb (u(vw)=abcann)uv گروه کامپيوتر نظریه زبانها و ماشینها ‏w=abcabb صفحه23 :  2-1رشته ها و زبانها قضیه :فرض کنید که *∑u,v,wєباشد. در این صورت ( w= u(vw))uvخواهد بود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه24 :  2-1رشته ها و زبانها معکوس رشته: فرض کنی\د ک\ه uی\ک رشت\ه در باشد .معکوس uبه صورت زی\ر تعریف می شود: ( iپایه . length(u)=n0:در این صورت u=λو ‏R ‏ ‏خواهد بود. ( iiگام بازگش\ت :اگ\ر length(u)=n›0باش\د ،در اینص\ورت برای برخی رشت\ه های wب\ه طول n-1و برخ\ی ∑u=wa , aєمعکوس رشته برابرخواهد بود: ‏R ‏R ‏u w a گروه کامپيوتر نظریه زبانها و ماشینها صفحه25 :  2-1رشته ها و زبانها قضیه :فرض کنید که є∑* u,vباشد. در این صورت (uv)R vRuRاست گروه کامپيوتر نظریه زبانها و ماشینها صفحه26 :  2-2مشخصات متناهی زبانها یک زبان به صورت یک مجموعه از رشته ها روی یک الفبا تعریف شده است. مثال: زبان Lاز رشته هایی روی { }a,bکه با یک aشروع شده و طول زوج دارند به صورت زیر تعریف می شود: ( iپایه. aa,abєL: ( iiگام بازگشت:اگر uєLباشد،آنگاهuaa,uab,uba,ubbєLاست. ( iiiهمبستگی:یک رشته uєLاست اگر آن بتواند با تکرار متناهی از مرحله گام بازگشت از عنصر پایه ای بدست آید. گروه کامپيوتر نظریه زبانها و ماشینها صفحه27 :  2-2مشخصات متناهی زبانها الحاق دو زبان :X,Y الحاق زبانهای Xو Yکه به صورت XYنشان می دهیم ،زبان }XY={uv l uєX and vєY ‏n 0 است n.مرتبه الحاق Xبا خودش را به صورت Xنشان می دهیم X .به صورت { }λتعریف می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه28 :  مشخصات متناهی زبانها2-2 در اینصورت. استY= {abb,ba} وX={a,b,c} فرض کنید که:مثال XY= aabb,babb,cabb,aba,bba.cba = 0X {}גּ 1 X =X= {a,b,c} 2 X =XX= {aa,ab,ac,ba,bb,bc,ca,cb,cc} 3 2 ,X =X X= {aaa,aab,aac,aba,abb,abc,aca,acb,acc baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc }caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc 29 :صفحه نظریه زبانها و ماشینها گروه کامپيوتر  2-2مشخصات متناهی زبانها فرض کنید که Xیک مجموعه باشد .در این صورت: ‏ ‏x  xi ‏ ‏i 1 ‏i ‏ * ‏x  x ‏i 0 *Xش..ام.لت..مام.یر.ش.ته هاییا.س.تک..ه م.یت..وا.ن.ند از ع.ناصر Xس..اخ.ته ش..وند. + .ت Xم.جموعه ر.ش.ته هایغ.یر ت..هیا.یجاد ش..ده .از Xا.س . گروه کامپيوتر نظریه زبانها و ماشینها صفحه30 :  2-2مشخصات متناهی زبانها مثال: زبان } *L={a,b}*{bb}{a,bشام\ل تمام\ی رشت\ه های روی { } a,bاست ک\ه دارای زی\ر رشت\ه bbم\ی باشد .الحاق مجموع\ه { }bbما را وجود bb در ه\ر رشت\ه از Lمطمئ\ن م\ی س\ازد .مجموع\ه های { * }a,bمشخ\ص می کنن\د ک\ه ه\ر تعدادی aو bب\ا ه\ر ترتیب\ی م\ی توان\د بع\د ی\ا قبل از bbقرار بگیرند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه31 :  2-3عب\ارات و مجموعه های با قاعده مجموع\ه باقاعده :مجموع\ه ای ب\ا قاعده اس\ت ک\ه بتوان\د با اس\تفاده از عملیات اجتماع ،الحاق و kleen starاز مجموعه ته\ی ،مجموع\ه شام\ل رشت\ه ته\ی و اعضای مجموع\ه الفب\ا تولید شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه32 :  2-3عب\ارات و مجموعه های با قاعده فرض کنی\د ک\ه∑ ی\ک الفب\ا باشد .مجموع\ه های باقاعده روی∑ به صورت بازگشتی زیر تعریف می شوند: ( iپای\هØ، λ :و {،}aب\ه ازاء ه\ر ،∑aєمجموع\ه هایی باقاعده روی∑ هستند. ( iiگام بازگش\ت :فرض کنی\د ک\ه Xو Yمجموع\ه هایی باقاعده روی∑ باشند .مجموع\ه های XY,XυYو *Xمجموع\ه هایی باقاعده روی∑ هستند. ( iiiهمبس\تگی X :ی\ک مجموع\ه باقاعده روی∑ اس\ت اگ\ر آ\ن بتوان\د با تکرار متناهی از مرحله گام بازگشت از عناصر پایه ای بدست آید. گروه کامپيوتر نظریه زبانها و ماشینها صفحه33 :  2-3عب\ارات و مجموعه های با قاعده مثال: مجموع\ه رشت\ه های\ی ک\ه ب\ا ی\ک aشروع شده و شامل حداق\ل ی\ک bهس\تند ،مجموع\ه ای با قاعده روی {}a,b است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه34 :  2-3عب\ارات و مجموعه های با قاعده عبارت با قاعده: فرض کنی\د ک\ه∑ ی\ک الفب\ا اس\ت .عبارات باقاعده روی∑ ب\ه صورت بازگشتی زیر تعریف می شوند: ( iپایه Ø، λ:و {،}aبه ازاء هر ،∑aєعباراتی باقاعده روی∑ هستند. ( iiگام بازگش\ت :فرض کنی\د ک\ه u,vعباراتی باقاعده روی∑ باشند.در این صورت عبارات uv, uυvو *uنیز عباراتی باقاعده روی∑ هستند. ( iiiهمبس\تگی u :ی\ک عبارت باقاعده روی∑ اس\ت اگ\ر آ\ن بتوان\د با تکرار متناهی از مرحله گام بازگشت از عناصر پایه ای بدست آید. گروه کامپيوتر نظریه زبانها و ماشینها صفحه35 :  2-3عب\ارات و مجموعه های با قاعده مثالهایی از عبارات با قاعده: ()*i a*ba*b(aυb (*ii (aυb)*ba*ba ()*iii (aυb)*b(aυb)*b(aυb ی\ک عبارت ب\ا قاعده برای مجموع\ه رشت\ه های\ی ک\ه شام\ل زی\ر رشته aaنم\ی باشن\د،عبارت ب\ا قاعده ، a*(ab+ )*υb*(ab +)*aممک\ن است شام\ل هی\چ پیشوندی از bه\ا نباشد .تمام\ی aه\ا بایس\تی حداق\ل ب\ه یک bختم شده و یا عنصر پایانی رشته باشند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه36 : فصل سوم :گرامرهای مستقل از متن اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: گرامرها و زبان های مستقل از متن اشتقاق و درخت آن گرامرهای قاعده گروه کامپيوتر نظریه زبانها و ماشینها صفحه37 :  3-1گرامرها و زبانهای مستقل از متن جمل\ه :ب\ه ی\ک رشت\ه درس\ت از لحاظ نحوی ،ی\ک جمله ( )sentenceاز زبان اطالق می کنیم. عناصر الفبا به عناصر پایانی زبان موسومند. عناص\ر اضاف\ی مورد اس\تفاده در فرآین\د تولی\د جمالت جهت اجرای محدودیتهای نحوی زبان به متغیرها یا عناصر غیر پایانی موسومند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه38 :  3-1گرامرها و زبانهای مستقل از متن گرامر مستقل از متن: ی\ک گرام\ر مس\تقل از مت\ن ،ی\ک چهارتای\ی ( )V,∑,P,Sاس\ت که درآ\ن Vی\ک مجموع\ه متناه\ی از متغیره\ا(∑،الفب\ا)ی\ک مجموع\ه متناهی از عناص\ر پایان\ی P،ی\ک مجموع\ه متناه\ی از قوانی\ن و Sی\ک عنصر مشخص از Vبه نام عنصر ابتدایی است. فرض می شود که Vو∑مجموعه هایی غیر الحاقی هستند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه39 :  3-1گرامرها و زبانهای مستقل از متن قانون: یک قانون که به آن یک تولید نیز می گویند ،عضوی از مجموعه )∑*V×(Vυاست .قانون [ ]A,wمعموالً به صورتA  W نوشته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه40 :  3-1گرامرها و زبانهای مستقل از متن نکته: از آنجائیکه رشته تهی در( *)∑Vυوجود دارد ،لذا λنیز ممکن است در سمت راست یک قانون قرار گیرد. نکته: قانونی به شکل A  به قانون تهی یا قانون المبدا موسوم است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه41 :  3-1گرامرها و زبانهای مستقل از متن مرحله اصلی در فرایند تولید ،تبدیل یک رشته با استفاده از یک قانون است. مثال:بکارگیری قانون A wبرای متغیر Aدر uAvرشته uwvرا ‏uAv uwv نشان می دهیم. تولید می کندکه آن را به صورت گروه کامپيوتر نظریه زبانها و ماشینها صفحه42 :  3-1گرامرها و زبانهای مستقل از متن یک رشته wاز vقابل اشتقاق است اگر یک دنباله متناهی از قوانین که vرا به wتبدیل می کنند وجود داشته باشد. * ‏v ‏ ‏ قابلیت اشتقاق wاز vرا به صورت w نشان می دهیم. گروه کامپيوتر نظریه زبانها و ماشینها صفحه43 :  3-1گرامرها و زبانهای مستقل از متن مجموعه رشته های قابل اشتقاق از :v فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن و )∑ *V є(Vυباشد .مجموعه رشته های قابل اشتقاق از vبه صورت بازگشتی زیر تعریف می شود: ( iپایه v:از vقابل اشتقاق است. ( iiگام بازگشت :اگر u=xAyاز vقابل اشتقاق بوده و wєP باشد ،آنگاه xwyاز vقابل اشتقاق خواهد بود. ‏A ( iiiهمبستگی :تمامی رشته های ایجاد شده از vبا بکارگیری تعداد متناهی گام بازگشت از vقابل اشتقاقند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه44 :  3-1گرامرها و زبانهای مستقل از متن نکته: ی\ک گرام\ر شام\ل ی\ک الفب\ا ی\ک روش تولی\د رشت\ه ه\ا اس\ت .این رشته ها ممکن است شامل متغیرها و عناصر پایانی باشند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه45 :  3-1گرامرها و زبانهای مستقل از متن فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن باشد. فرم جمله ای:یک رشته )∑ *w є(Vυیک فرم جمله ای از Gاست اگر یک اشتقاق S * wوجود داشته باشد. جمله:یک رشته *∑wєیک جمله از Gاست اگر یک اشتقاق* w Sدر Gوجود داشته باشد. زبان :Gکه آنرا با )L(Gنشان می دهند،مجموعه زیراست. * {w  | s  }  w گروه کامپيوتر * نظریه زبانها و ماشینها صفحه46 :  3-1گرامرها و زبانهای مستقل از متن فرم جمله ای ها ،رشته هایی قابل اشتقاق ازعنصرابتدایی گرامرهستند . جمالت فرم جمله ایهایی هستند که تنها شامل عناصر پایانی می باشند. به مجموعه ای از رشته ها روی یک مجموعه الفبا(∑) زبان مستقل از متن گفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه47 :  3-1گرامرها و زبانهای مستقل از متن A  uAvرا بازگشت مستقیم می نامیم. یک قانون Aبه شکل ‏ ‏A ‏ ‏W ‏ ‏ به یک اشتقاق  uAv که Aدر wنیست، بازگشت غیر مستقیم می گوییم. گروه کامپيوتر نظریه زبانها و ماشینها صفحه48 :  3-1گرامرها و زبانهای مستقل از متن مثال :گرامر Gکه یک زبان شامل رشته هایی با تعداد مثبت و زوجی از aها را تولید می کند. )G=(V,∑,P,S }V={S,A ∑ ={}a,b ‏AA ‏AAA l bA l Ab l a ‏P: S ‏A گروه کامپيوتر نظریه زبانها و ماشینها صفحه49 :  3-1گرامرها و زبانهای مستقل از متن اشتقاق راست و چپ: اشتقاق چپ:هر قانونی که به اشتقاق اولین متغیر سمت چپ رشته می پردازد. اشتقاق راست :به قوانینی که راست ترین متغیر موجود در هر رشته را تبدیل می کنند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه50 :  3-1گرامرها و زبانهای مستقل از متن درخت اشتقاق: فرض کنید که )G=(V,∑,P,Sیک گرامر مستقل از متن بوده و* S ‏w یک اشتقاق باشد.درخت اشتقاق S * wیک درخت مرتب شده است که به صورت زیر ساخته می شود: گروه کامپيوتر نظریه زبانها و ماشینها صفحه51 :  3-1گرامرها و زبانهای مستقل از متن ( iدرخت اشتقاق ()DTرا با ریشه Sمقداردهی کنید. ) xi (V   قانونی در اشتقاق بکار ( iiاگر A  x1x2x3....xnبا 2x3....xnرا1xبه xعنوان فرزندان رفته برای رشته uAvباشد ،آنگاه Aبه درخت اضافه کنید. (iiiاگر A  قانونی در اشتقاق بکار رغته برای رشته uAvباشد، آنگاه را به عنوان تنها فرزند Aبه درخت اضافه کنید. گروه کامپيوتر نظریه زبانها و ماشینها صفحه52 :  گرامرها و زبانهای مستقل از متن3-1 درخت اشتقاق S AA aA aAAA ترتیب برگها S S A S abAAA A b A A A A b A A b A S نظریه زبانها و ماشینها A a,b,a,b,A,A A a A a A S A a A b A A b A A A A a,b,a,b,a,A A a A b 53 :صفحه A A b A a,b,a,A,A A S a ababaa a,b,AAA S A a a A A A ababAAَ A A A abaAA a,,A,A,A A a S a ababaA A A A a S A,A a,A S a A a a گروه کامپيوتر A b A A a a,b,a,b,a,a  3-1گرامرها و زبانهای مستقل از متن پیش قضیه: ‏n vیک اشتقاق فرض کنید که Gیک گرامر مستقل از متن بوده وw در Gباشد که Vمی تواند به صورتv  w1A1w2 A2...wk Akwk1 با wنوشته شود.در این صورت رشته های )*pє(∑υVای وجود دارند که در شرایط زیر صدق می کنند: (Ai ti  pi i (v  w1 p1w2 p2...wk pk wk1 ii ‏k (iii ‏ti n ‏ ‏i ‏1 گروه کامپيوتر نظریه زبانها و ماشینها صفحه54 : م\ثا\له\ای\یاز گ\\را\مرها و ز\بانها3-2 فرض کنید که Gگرامری با قوانین زیر باشد: ‏aSa l aBa ‏bB l a ‏n ‏S ‏B ‏m ‏n در این صورت } L(G)={a b a l n >0 , m >0خواهد بود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه55 : م\ثا\له\اییاز گ\\را\مرها و ز\بانها3-2 گرامر زبان 2 ‏n ‏m ‏m ‏n {}a b c d l n ≥0 , m >0 ‏aSdd l A ‏bAc l bc ‏S ‏A یک رشته wمتقارن است اگر w=wRباشد. زبان مجموعه متقارن روی {}a,b گروه کامپيوتر گرامر ‏aSa l bSb نظریه زبانها و ماشینها ‏S صفحه56 : م\ثا\له\اییاز گ\\را\مرها و ز\بانها3-2 زبان {}an b ml 0≤n≤m≤2n زبان ‏mn n گرامر גּ aSb l aSbb l ‏G: S گرامر ‏n ({}l n≥0, m >0 ) cb( )nab גּabS cB l ‏bB l b گروه کامپيوتر نظریه زبانها و ماشینها ‏S ‏B صفحه57 : 3-3گرامرهای باقاعده گرامر باقاعده :یک گرامر مستقل از متن است که هر قانون آن دارای یکی از حاالت زیر است: ‏A (a ‏i (ii λ A (aB ‏iii A که در آن A,B є Vو ∑aєمی باشد. یک زبان با قاعده است اگر بتواند توسط یک گرامر با قاعده تولید شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه58 : 3-3گرامرهای باقاعده مثال: گرامر بی قاعده גּ abSA l ‏Aa l ‏Aגּ ‏aA l ‏A گرامر با قاعده גּ aB l ‏G: S ‏bS l bA ‏S ‏B גּ گروه کامپيوتر نظریه زبانها و ماشینها صفحه59 : 3-4مروری بر گرامرها و زبان ها گرامر زبان }L={a2n b3m l n>0 ‏AASB l AAB ‏a ‏G: S ‏A ‏B ‏bbb اثبات: قانون به کار رفته ‏AASB ‏S ‏AAB ‏S ‏a ‏A ‏bbb ‏B اشتقاق ‏n-1 ‏n-1 ‏Sn-1 (AA) SB ‏n ‏n ‏n ‏n (B )AA ‏n ()bbb( )aan 2n 3m گروه کامپيوتر (B )aa نظریه زبانها و ماشینها =a b صفحه60 : 3-4مروری بر گرامرها و زبان ها مثال: گرامر زبان גּaS l bB l )**L(G)=a*(a*ba*ba زبان ‏m 2n ‏S ‏aB l bS l bC ‏B גּ aC l ‏C گرامر ‏m ‏n {}a b c d l n ≥m >0 گروه کامپيوتر ‏G:S aSdd l A ‏A bAc l bc نظریه زبانها و ماشینها صفحه61 : فصل چهارم :مقدمه ای بر پارسر ها اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: اشتقاق چپ و ابهام گراف یک گرامر پارسر ها گروه کامپيوتر نظریه زبانها و ماشینها صفحه62 :  4-1اشتقاقهای چپ و ابهام اشتقاق در ی\ک گرام\ر مس\تقل از مت\ن مکانیزم\ی برای تولی\د رشته های زبان گرامر ایجاد می کند. الگوریتم تجزیه: یک سوال مهم اینست که چگونه می توان تعیین کرد که آیا دنباله ای از ک\د ی\ک زبان از قواع\د نحوی گرام\ر آ\ن زبان تبعی\ت م\ی کن\د ی\ا خیر؟ ی\ک رشت\ه از لحاظ نحوی درس\ت اس\ت اگ\ر آن بتوان\د ب\ا اس\تفاده از قوانین گرام\ر ،از عنص\ر ابتدائ\ی مشت\ق شود .الگوریت\م ه\ا بایس\تی برای تولید اشتقاق رشته ها در زبان یک گرامر طراحی شوند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه63 :  4-1اشتقاقهای چپ و ابهام زبان یک گرامر :مجموعه ای از رشته های پایانی است که می توانند به هر روشی از عنصر ابتدائی مشتق شوند. قضیه: فرض کنید) G=(V,∑,P,Sیک گرامر مستقل از متن باشد .یک رشته wدر ) L(Gاست اگر و تنها اگر یک اشتقاق چپ wاز Sوجود داشته باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه64 :  4-1اشتقاقهای چپ و ابهام یک گرامر مستقل از متن Gمبهم ( )ambiguousاست ،اگر یک رشته ) w L(Gوجود داشته باشد بطوریکه با دو اشتقاق چپ مجزا تولید شود. مثال: ‏aS l Sa l a گرامر ‏G: S \ت Gی\\کگ\\را\مر م\بهما\س\تز\یرا ر\ش\ته aaدارا\یدو ا\ش\تقاقچ\پم\جزا ا\س . ‏Sa ‏aS ‏S ‏aa ‏S ‏aa گروه کامپيوتر نظریه زبانها و ماشینها صفحه65 :  4-1اشتقاقهای چپ و ابهام ابهام از ویژگیهای گرامر است ،نه از ویژگیهای زبان. مثال: ‏bS l Sb l a گرامر ‏G: S زبان *G ،b*abاست.اشتقاقهای چپ زیر ابهام Gرا نشان می دهند. ‏Sb ‏bS ‏S ‏bSb ‏bSb ‏bab ‏bab گروه کامپيوتر ‏S نظریه زبانها و ماشینها صفحه66 :  4-1اشتقاقهای چپ و ابهام نکته :یک گرامر غیر مبهم است اگر در هر مرحله از یک اشتقاق چپ تنها یک قانون وجود داشته باشد که ما را به اشتقاق یک رشته کامل هدایت کند. ‏λ ‏S aSb l A l ‏A aAbb l abb گروه کامپيوتر نظریه زبانها و ماشینها صفحه67 :  4-2گراف یک گرامر اشتقاقهای چپ یک گرامر مستقل از متن Gمی تواند به وسیله یک گراف جهت دار )( g(Gگراف چپ گرامر)Gنشان داده شود .گره های گراف ،فرم جمله ای های چپ گرامر هستند. یک فرم جمله ای چپ ،رشته ای است که می تواند بوسیله یک اشتقاق چپ از عنصر ابتدایی نتیجه شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه68 :  4-2گراف یک گرامر فرض کنید که )G=(V,∑,P,Sیک گرامر مستقل از متن باشد. گراف چپ گرامر)،G،g(Gگراف جهت دار( )N,P,Aاست که گره ها و کمانهای آن به صورت زیر تعریف می شوند: (i * * }N {w (v   ) | s   w ‏L (}w by application of rule r گروه کامپيوتر ‏ii A={[v,w,r]єN×N×P ‏lv ‏L نظریه زبانها و ماشینها صفحه69 :  4-2گراف یک گرامر گرام\ر مس\تقل از مت\ن دارای تعداد محدودی قانون م\ی باشد ،لذا ه\ر گره نی\ز دارای تعداد محدودی فرزن\د خواه\د بود ،ب\ه گرافی با این ویژگی ،گراف متناهی محلی گوییم. گروه کامپيوتر نظریه زبانها و ماشینها صفحه70 :  4-2گراف یک گرامر دو استراتژی مختلف برای پیدا کردن یک اشتقاق wاز Sوجود دارد: -1پارسر باال به پائین :جستجواز گره Sشروع شده و تا یافتن رشته wادامه می یابد. -2پارسر پائین به باال:شروع جستجو با رشته پایانی wو ادامه آن تا یافتن عنصر ابتدایی است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه71 : الگوریتم های تجزیه الگوریتم های تجزیه: -1الگوریتم تجزیه باال به پایین سطحی -2الگوریتم تجزیه باال به پایین عمقی -3الگوریتم تجزیه پایین به باالی سطحی -4الگوریتم تجزیه پایین به باالی عمقی گروه کامپيوتر نظریه زبانها و ماشینها صفحه72 :  4-3پارسر باال به پایین سطحی نکته: یک پارسر تعیین می کند که آیا یک رشته ورودی از قوانین گرامر قابل اشتقاق است یا خیر. پارس\ر باال ب\ه پایی\ن :اشتقاقهای\ی را ب\ا اس\تفاده از قوانین روی متغیرهای چپ یک فرم جمله ای ایجاد می کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه73 :  4-3پارسر باال به پایین سطحی مس\یرهایی ک\ه ب\ا Sدر گراف ی\ک گرام\ر شروع م\ی شون\د بیانگر اشتقاق چ\پ گرام\ر هس\تند .کمانهای خارج شده از ی\ک گره قوانین قابل استفاده برای تجزیه گره را مشخص می کنند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه74 :  4-3پارسر باال به پایین عمقی امکان انتخاب نادرست یک آینده دو مشکل در پارسرهای عمقی ایجاد می کند: -1اول اینکه الگوریتم بایستی بتواند یک انتخاب نادرست را تشخیص بدهد. -2دوم اینکه پارسر پس از تشخیص یک انتخاب نادرست به عقب برگشته و اشتقاق دیگری را تولید نماید. گروه کامپيوتر نظریه زبانها و ماشینها صفحه75 :  4-3پارسر باال به پایین عمقی یک اشتقاق از ()b+b گرامر: }AE: V= {S,A,T = {}),(,+,b ‏A گروه کامپيوتر ‏P: 1- S ‏T -2 ‏A ‏T+T -3 ‏A ‏b -4 ‏T (A) -5 ‏T نظریه زبانها و ماشینها صفحه76 :  4-3پارسر باال به پایین عمقی اشتقاق ‏A پشته ‏S []S,1 ‏T []A,2 ()A []T,5 ()A+T [(]3,)A ()T+T [(]2,)A+T ()b+T [(]4,)T+T ()b+b [(]4,)b+T گروه کامپيوتر نظریه زبانها و ماشینها صفحه77 :  4-5تجزیه پایین به باال هنگامی که ساختار جستجو با رشته Pآغاز می شود ،الگوریتم حاصل یک پارسر پایین به باال خواهد بود. مثال: کاهش قانون (b+)b ‏b ‏T (b+)T ‏T ‏T (B)A )(A ‏T ‏T+b ‏T ‏A ‏A+b ‏b ‏T ‏A+T ‏A+T ‏A ‏A ‏A ‏S ‏S گروه کامپيوتر نظریه زبانها و ماشینها صفحه78 :  4-6پارسر پایین به باالی عمقی پارس\ر پایی\ن ب\ه باال م\ی توان\د ب\ه روش عمق\ی نی\ز ب\ه کار رود .کاه\ش ه\ا با اس\تفاده از عم\ل شیف\ت و روش مقایس\ه تشری\ح شده برای الگوریتم س\طحی تولی\د م\ی شوند .ترتی\ب پردازش کاه\ش ه\ا ب\ا ترتی\ب قوانین و تعداد شیفتهای مورد نیاز برای انجام انطباق مشخص می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه79 : فصل پنجم :فرم های نرمال اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: فرم های نرمال حذف قوانین المبدا حذف قوانین زنجیره ای ‏فرم نرمال شومسکی وگریباش گروه کامپيوتر نظریه زبانها و ماشینها صفحه80 : فصل پنجم :فرمهای نرمال ی\ک فرم نرمال ب\ا اعمال محدودیتهای\ی روی شک\ل قوانین موجود در گرام\ر تعری\ف م\ی شود .گرامره\ا در ی\ک فرم نرمال ،مجموعه کاملی از زبانهای مستقل از متن را تولید می کنند. فرم های نرمال برای گرامرهای مستقل از متن: -1فرم های نرمال شومسکی -2فرم های نرمال گریباش گروه کامپيوتر نظریه زبانها و ماشینها صفحه81 :  5-1حذف قوانین المبداء فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن باشد.یک گرامر )' G'=(V',∑,P',Sوجود دارد به طوریکه ()i L(G)=L(G ( iiقوانین 'Pبه شکل w Aمی باشند که 'A є Vو )∑ *w є ((V-{S'})υاست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه82 :  5-1حذف قوانین المبداء مثال:عنصر ابتدایی گرامر Gبازگشتی است. ‏S ''G':S ‏aS l AB l AC גּ גּ ‏aA l ‏aS l AB l AC ‏S גּ aA l ‏A ‏bB l bS ‏B ‏cC l ‏C گروه کامپيوتر ‏G:S גּ نظریه زبانها و ماشینها ‏A ‏bB l bS ‏B ‏cC l ‏C صفحه83 :  5-1حذف قوانین المبداء به متغیری که بتواند رشته تهی را مشتق کند ،میرا ( )nullableگفته می شود. یک گرامر بدون متغیرهای المبداء به گرامر غیر انقباضی ( )noncontractingموسوم است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه84 :  5-1حذف قوانین المبداء فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن باشد. الگوریتم زیر مجموعه ای از متغیرهای میرای Gرا تولید می کند. الگوریتم : ورودی :یک گرامر مستقل از متن )G=(V,∑,P,S .1גּ }єP ‏NULL : = {A l A ‏repeat .2 ‏PREV := NULL 2.1 ‏for each variable A є V do 2.2 ‏If there is an A rule A w and w є PREV* then }NULL : = NULL υ{A ‏until NULL = PREV گروه کامپيوتر نظریه زبانها و ماشینها صفحه85 :  5-1حذف قوانین المبداء فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن باشد. اگر A G* wباشد ،آنگاه گرامر )G'=(V,∑,P {A w},S معادل با Gاست. نکته :یک گرامر با قوانین المبداء غیر انقباضی نیست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه86 :  5-1حذف قوانین المبداء فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن ) G =(V ,∑,P ,S وجود دارد بطوریکه ‏L ‏L ‏L ‏L ()i L(G )=L(G ‏L ( ii Sیک متغیر بازگشتی نیست. ‏L (λiii A در Pوجود دارد اگر و فقط اگر ) єL(Gوגּ A=Sباشد. ‏L ‏L گروه کامپيوتر نظریه زبانها و ماشینها صفحه87 :  5-2حذف قوانین زنجیره ای بکارگیری ی\ک قانونA  Bن\ه تنه\ا طول رشت\ه مشتق شده را افزای\ش نم\ی ده\د ،بلک\ه عناص\ر پایان\ی اضاف\ی نی\ز تولی\د می کند. در واق\ع ،ای\ن قانون ی\ک متغی\ر رامجددا ً نامگذاری می کند. قوانینی به این شکل به قوانین زنجیره ای موسومند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه88 :  5-2حذف قوانین زنجیره ای قوانین زیر را در نظر بگیرید: ‏aA l a l B ‏A ‏bB l b l C ‏B قانون زنجیره ای A  B مشخ\ص م\ی کن\د ک\ه ه\ر رشت\ه قابل اشتقاق از ،Bاز Aنی\ز قابل اشتقاق اس\ت .بکارگیری یک قانون زنجیره ای ،ی\ک مرحلهاضاف\ی اس\ت ک\ه م\ی توان\د ب\ا افزودن قوانین Aحذف شود .قانون زنجیره ای A  Bرا م\ی توان ب\ا س\ه قانون Aب\ه صورت زیر جایگزین نمود: ‏A aA l a l bB l b l C ‏bB l b l C گروه کامپيوتر نظریه زبانها و ماشینها ‏B صفحه89 :  5-2حذف قوانین زنجیره ای پیش قضیه فرض کنید که Gیک گرامر مستقل از متن غیر انقباضی حقیقی است. الگوریتم زیر مجموعه متغیرهای قابل اشتقاق از Aرا تنها با استفاده از قوانین زنجیره ای تولید می کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه90 :  حذف قوانین زنجیره ای5-2 CHAIN(A) ایجاد مجموعه G=(V,∑,P,S) یک گرامر مستقل از متن غیر انقباضی حقیقی:ورودی CHAIN(A) : = {A} .1 PREV : = ø .2 repeat .3 NEW : = CHAIN(A)-PREV .3.1 PREV : = CHAIN(A) .3.2 for each variable BєNEW do .3.3 for each rule B C do CHAIN(A) : = CHAIN(A)υ{C} until CHAIN(A) = PREV 91 :صفحه نظریه زبانها و ماشینها گروه کامپيوتر  5-2حذف قوانین زنجیره ای قضیه فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن GCوجود دارد بطوریکه ()i L(G C)=L(G ( ii GCهیچ قانون زنجیره ای نداشته باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه92 :  5-3عناصر غ\یر مفید عناصر مفید و عناصر غیر مفید: فرض کنید Gیک گرامر مستقل از متن است .در این صورت یک ‏S عنصر ) x (Vمفید( )usefulاست اگر یک اشتقاق * uxwG * w ‏G وجود داشته باشد بطوری که )∑ *u,vє(Vυو * ∑wєباشد .به عنصری که مفید نیست ،غیر مفید( )uselessگفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه93 :  5-3عناصر غ\یر مفید ی\ک عنص\ر پایان\ی مفی\د اس\ت اگ\ر در ی\ک رشت\ه از زبان Gرخ دهد .یک متغی\ر مفی\د اس\ت اگ\ر در ی\ک اشتقاق ک\ه ب\ا ی\ک عنص\ر ابتدائی شروع شده و یک رشته پایانی را تولید می کند ،رخ دهد. دو شرط بایستی برای یک متغیر مفید برقرار باشد: -1متغیر بتواند در یک فرم جمله ای گرامررخ دهد یا به عبارتی در یک رشته قابل اشتقاق از Sوجود داشته باشد. -2اشتقاق یک رشته پایانی از ان متغیر وجود داشته باشد. به متغیری که در یک فرم جمله ای رخ می دهد،قابل دسترس ( )reachableاز Sگفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه94 :  5-3عناصر غ\یر مفید قضیه فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن است. الگوریتمی برای ایجاد یک گرامر مستقل از متن ) GT=(VT,∑T,PT,Sوجود دارد بطوریکه ()i L(G T)=L(G ( iiهر متغیر در GTیک رشته پایانی در GTرا مشتق کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه95 :  عناصر غ\یر مفید5-3 :مثال G: S VT = {S,A,B,E,F} AC l BS l B = {a,b}∑ A aA l aF T B CF l b PT = S C cC l D D BS l B A aA l aF aD l BD l C B b E aA l BSA E aA l BSA F bB l b F bB l b 96 :صفحه حذف متغیرهای غیر مفید نظریه زبانها و ماشینها گروه کامپيوتر  5-3عناصر غ\یر مفید پیش قضیه فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن است. الگوریتم زیر مجموعه ای کامل از متغیرهای قابل دسترس از Sرا تولید می کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه97 :  عناصر غ\یر مفید5-3 ایجاد متغیرهای قابل دسترس G=(V,∑,P,S) یک گرامر مستقل از متن:ورودی REACH := {S} .1 PREV : = ø .2 repeat .3 NEW := REACH – PREV 3.1 PREV := REACH 3.2 for each variable AєNEW do 3.3 for each rule A W do add all variables in w to REACH until REACH = PREV 98 :صفحه نظریه زبانها و ماشینها گروه کامپيوتر  5-3عناصر غ\یر مفید قضیه فرض کنید که ) G=(V,∑,P,Sیک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن GUوجود دارد بطوریکه ()i L(G U)=L(G ( ii GUهیچ عنصر غیر مفیدی ندارد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه99 :  5-3عناصر غ\یر مفید مثال گرامر زیر را در نظر بگیرید. ‏a l AB ‏b ‏G:S ‏A لزوم بکارگیری تبدیالت به یک ترتیب معین با بکارگیری فرآیندهای هر دو ترتیب و مقایسه نتایج آنها مشخص می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه100 :  5-3عناصر غ\یر مفید -1حذف عناصر غیر قابل دسترس: ‏a AB ‏S ‏b ‏A -1حذف متغیرهایی که رش\ته پایانی را تولید نمی کنند: ‏a ‏b -2حذف متغیرهایی که رشته پایانی را تولید نمی کنند: ‏a ‏S ‏b ‏A ‏A -2حذف عناصر غیر قابل دسترس: ‏a متغیر Aو عنصر پایانی Bغیر مفید هستند. گروه کامپيوتر ‏S نظریه زبانها و ماشینها صفحه101 : ‏S  5-4فرم نرمال شومسکی فرم نرمال شومسکی: یک گرامر مستقل از متن )G=(V,∑,P,Sدر فرم نرمال شومسکی است اگر هر قانون دارای یکی از حالتهای زیر باشد: (BC (a ‏iA ‏ii A (iii Sגּ که } B,CєV-{Sاست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه102 :  5-4فرم نرمال شومسکی درخت اشتقاق در یک گرامر به فرم شومسکی یک درخت دودویی است. قضیه فرض کنی\د ک\ه ) G=(V,∑,P,Sی\ک گرام\ر مس\تقل از متن باشد. الگوریتم\ی وجود دارد ک\ه ی\ک گرامر )' G'=(V',∑,P',Sدر فرم نرمال شومسکی و معادل با Gایجاد کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه103 :  5-4فرم نرمال شومسکی مثال ‏A'T1 a ‏aABC l a ‏G' : S ‏G: S ‏a 'A ‏aA l a ‏A ‏AT2 ‏T1 ‏bcB l bc ‏B ‏BC ‏T2 ‏A'A a ‏A ‏B'T3 B'C 'B ‏C'B ‏T3 ‏C'C c ‏C ‏b 'B ‏c 'C گروه کامپيوتر فرم شومسکی نظریه زبانها و ماشینها ‏cC l c ‏C صفحه104 :  5-4فرم نرمال شومسکی مثال: ‏AY l b l LZ ‏S )A+T l b l (A ‏S ‏AR ‏Z )A+T l b l (A ‏A ‏AY l b l LZ ‏A )b l (A ‏T ‏b l LZ ‏T ‏PT ‏Y \ت Yب\\یان\گرT+ا\س . + P \ت Zب\\یان\گر )Aا\س . \ت Lب\\یان\گر( ا\س . ( L \ت Rب\\یان\گر) ا\س . ) R \ت Pب\\یان\گر +ا\س . گروه کامپيوتر نظریه زبانها و ماشینها صفحه105 :  5-5حذف بازگشت چپ مستقیم قانون بازگشت چپ مستقیم A A+Tدر گرامر AEمحاسبات پایان ناپذیری را در هر الگوریتم سطحی و عمقی امکانپذیر می سازد. برای اجتناب از وقوع ی\ک تجزی\ه پایان ناپذی\ر بایستی قوانین بازگشت چپ را از گرامر حذف کنیم. گروه کامپيوتر نظریه زبانها و ماشینها صفحه106 :  5-5حذف بازگشت چپ مستقیم مثال: )1 )2 ‏bZ l b ‏A ‏aZ l a ‏Z ‏aA l b ‏bZ l cZ l b l c ‏A ‏aZ l bZ l a l b ‏Z گروه کامپيوتر ‏A ‏Aa l Ab l b l c نظریه زبانها و ماشینها ‏A صفحه107 :  5-5حذف بازگشت چپ مستقیم پیش قضیه فرض کنی\د ک\ه ) G=(V,∑,P,Sی\ک گرام\ر مس\تقل از متن بوده و AєVی\ک متغی\ر بازگشت\ی چ\پ مستقیم در Gباشد. الگوریتم\\\ی وجود دارد ک\\\ه ی\\\ک گرامر معادل )' G'=(V',∑,P',Sایجاد نمای\د بطوریک\ه Aی\ک متغیر بازگشتی چپ مستقیم نباشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه108 :  5-6فرم نرمال گریباش ایجاد پیشوندهای پایان\ی کش\ف ب\ن بس\ت ه\ا را توس\ط الگوریتم های تجزی\ه باال ب\ه پایی\ن تس\هیل م\ی کند .ی\ک فرم نرمال ( نظیر فرم گریباش) طوری ارائ\ه م\ی شود ک\ه بکارگیری ه\ر قانون بتواند طول پیشون\د پایان\ی رشت\ه مشت\ق شده را افزای\ش ده\د ک\ه ای\ن ام\ر ما را از وجود بازگش\ت چ\پ ،چ\ه مس\تقیم و چ\ه غی\ر مس\تقیم ،مطمئ\ن می سازد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه109 :  5-6فرم نرمال گریباش فرم نرمال گریباش: یک گرامر مستقل از متن )G=(V,∑,P,Sدر فرم نرمال گریباش است اگر هر قانون دارای یکی از حالتهای زیر باشد: (λ i S (a ‏ii A (aA1A2…An ‏iii A که ∑aєو برای هر } i=1,2,….n ، AiєV-{Sاست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه110 :  فرم نرمال گریباش5-6 S SaB l aB B bB lגּ فرم شومسکی S' a ST l SA l AB l S ST l SA l AB l a B CB l b T AB S' aBZT l aZT l aBT l aT l aBZA l aZA l aBA l aA l aB l a A a S aBZ l aZ l aB l a C b B bB l b T aB A a C b Z aBZ l aZ l aB l a فرم گریباش فرم گریباش 111 :صفحه :مثال نظریه زبانها و ماشینها گروه کامپيوتر  فرم نرمال گریباش5-6 S G SaB abaab اشتقاق چپ رشته:مثال فرم نرمال شومسکی فرم نرمال گریباش 'S SA 'S aBZA SaBaB STA abZA SaBaBaB SATA abaZA aBaBaBaB ABATA abaaBA abBaBaBaB aBATA abATA abaabA abaBaBaB abaaba abaTA abaaBaB abaABA abaabBaB abaaBA abaabaB abaabA abaaba abaaba 112 :صفحه نظریه زبانها و ماشینها گروه کامپيوتر فصل ششم :آتاماتای متناهی اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: آتاماتای قطعی دیاگرام حالت ‏آتاماتای غیر قطعی گروه کامپيوتر نظریه زبانها و ماشینها صفحه113 : فصل ششم :آتاماتای متناهی ب\ه ی\ک روال موث\ر برای تعیی\ن اینک\ه آی\ا ی\ک رشت\ه ورودی متعل\ق به یک زبان است یا خیر یک پذیرنده زبان گفته می شود. ویژگی عمومی همه ماشینها پردازش ورودی و تولید خروجی است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه114 :  6-2آتاماتای متناهی قطعی()Finite-State Machine ی\ک آتاماتای متناه\ی قطع\ی ( )DFAب\ه ص\ورت پن\ج تایی ) M=(Q,∑,∂,q0,Fبیان م\ی شود ک\ه در آ\ن Qی\ک مجموع\ه متناهی از حاالت ∑،ی\ک مجموع\ه متناه\ی موس\وم ب\ه الفب\ا q0єQ،مبی\ن حالت ابتدای\ی F،زیرمجموع\ه ای از Qشام\ل حاالت نهای\ی یا حاالت پذیرش، و∂ ی\ک تاب\ع جام\ع از ∑×Qب\ه Qک\ه ب\ه تاب\ع گذر موس\وم اس\ت می باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه115 :  6-2آتاماتای متناهی قطعی()Finite-State Machine حاالت یک DFAبیانگر وضعیت داخلی ماشین هستند. ورودی ،یک دنباله متناهی از الفبای ∑ است. ی\ک محاس\به آتامات\ا شام\ل اجرای مجموع\ه ای از دستورالعملها است .اجرای یک دستورالعمل حالت ماشین را تغییر می دهد. هدف از محاس\به ی\ک آتامات\ا تعیی\ن قابلی\ت پذیرش یک رشته ورودی است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه116 :  6-2آتاماتای متناهی قطعی()Finite-State Machine فرض کنید که ) M=(Q,∑,∂,q0,Fیک DFAباشد .زبان ،Mکه با ) L(Mنشان داده می شود ،مجموعه ای از رشته ها در *∑ است که توسط Mپذیرفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه117 :  6-2آتاماتای متناهی قطعی()Finite-State Machine مثال: DFA Mی\\کم\جموعه از ر\ش\ته هاییرا رو\ی{ }a,bم\یپ\\ذیرد ک\\ه ش\\ام\لز\یر ر\ش\ته bbه\ستند؛ ب\\دینصور\تک\\ه \ت ) *L(M)=(aυb)*bb(aυbا\س . }M : Q={q0,q1.q2 ∑= {}a,b }F={q2 گروه کامپيوتر نظریه زبانها و ماشینها صفحه118 :  6-2آتاماتای متناهی قطعی()Finite-State Machine تاب\ع گذر در ی\ک جدول ب\ه نام جدول گذر داده شده اس\ت.حاالت به ص\ورت عمودی و الفب\ا ب\ه ص\ورت افق\ی در جدول قرار گرفته اند. عملکرد آتامات\ا در حال\ت qiب\ا ورودی ، aب\ا یافت\ن نقط\ه مشترک سطر متناظر qiو ستون متناظر aتعیین می شود. ∂ ‏b ‏a ‏q1 ‏q0 ‏q0 ‏q1 ‏q0 ‏q1 ‏q2 ‏q2 ‏q2 گروه کامپيوتر نظریه زبانها و ماشینها صفحه119 :  6-2آتاماتای متناهی قطعی()Finite-State Machine تابع گذر توسعه یافته ^∂ از یک DFAبا تابع گذر ∂ تابعی است از *∑×Qبه Qکه به صورت بازگشتی زیر روی طول رشته ورودی تعریف می شود: ( iپایه . length(w)=0 :در این صورت גּ =wو ∂(=) ,qiגּ^ qi است. . length(w)=1در این صورت (=a wبرای برخی )∑aєو ∂(^ )qi,a( ∂ =) qi,aاست. ( iiمرحله بازگشت :فرض کنید length(w)>1باشد.آنگاه w=uaو ∂ (∂(^ ∂ =)qi,ua( ^)a,)qi,u خواهد بود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه120 :  6-3دی\اگرامهای حالت و مثالها دیاگرام حالت یک ،DFAیک گراف جهت دار بر چسب شده است که گره های آن مبین حاالت ماشین بوده و کمانهایش از تابع گذر بدست آمده است. مثال: ‏a,b ‏q2 ‏a ‏b ‏q1 ‏b ‏q0 > ‏a گروه کامپيوتر نظریه زبانها و ماشینها صفحه121 :  6-3دی\اگرامهای حالت دیاگرام حالت یک M=(Q,∑,∂,q0,F) DFAیک گراف بر چسب دار Gبا شرایط زیر است: ( iگره های Gعناصر Qهستند. ( iiبرچسب کمانهای Gعناصر∑ هستند. ( iii q0گره ابتدایی با فرم نمایشی >است. ( iv Fمجموعه گره های پذیرش است که هرگره پذیرش با مشخص می ش\ود. ( vیک کمان از گره qiبه qjبا برچسب aوجود دارد اگر ∂( qj=)qi,aباشد. ( viبرای هر گرهqiوعنصر є∑aدقیق ًا یکی کمان با برچسب aاز qiخارج می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه122 :  6-3دی\اگرامهای حالت و مثالها محاسبه DFAبا ورودی ababbو مسیر متناظر آن در دیاگرام به صورت زیر است: ,q0 [ ]q0,ababb ,q0 []q0,babb ,q1 []q1,abb ,q0 []q0, bb ,q1 []q1,b ‏q2 [גּ] ,q2 ┴ ┴ ┴ ┴ ┴ مسیر محاسبه رشتهababbقابل پذیرش است زیرا در حالت پایانی q2متوقف شده است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه123 :  6-3دی\اگرامهای حالت و مثالها مثال: رشته هایی روی { }a,bکه شامل زیر رشته bbنمی باشند. ‏a ‏b ‏q3 ‏q2 ‏a ‏a ‏q1 ‏b ‏b ‏q5 ‏a ‏a ‏q0 > ‏b ‏b ‏q4 ‏a,b گروه کامپيوتر نظریه زبانها و ماشینها صفحه124 :  6-3دی\اگرامهای حالت و مثالها مثال: DFA Mز\بان\یش\\ام\لر\ش\ته ها رو\ی{ }a,bب\\ا ت\\ع\داد زو\ج\یaو ت\\ع\داد ف\\رد\ی bرا م\یپ\\ذیرد. ‏b > []ea,eb []ea,ob ‏b ‏a ‏a ‏a :'M ‏a ‏b []oa,eb []oa,ob ‏b گروه کامپيوتر نظریه زبانها و ماشینها صفحه125 :  6-3دی\اگرامهای حالت و مثالها دیاگرام حال\ت زی\ر DFAغی\ر کامل\ی را تعری\ف م\ی کن\د که عبارت ( c*)abرا می پذیرد. ‏a ‏q1 ‏q0 ‏b > ‏c ‏q2 گروه کامپيوتر نظریه زبانها و ماشینها صفحه126 :  6-4آتاماتای متناهی غیر قطعی ی\ک آتاماتای متناه\ی غی\ر قطع\ی ی\ک پن\چ تایی )M=(Q,∑,∂,q0,F اس\ت ک\ه در آ\ن Qی\ک مجموع\ه متناه\ی از حاالت ∑،ی\ک مجموعه متناه\ی موس\وم ب\ه الفب\ا q0єQ،مبی\ن حال\ت ابتدای\ی F،زیرمجموعه ای از Qشام\ل حاالت نهای\ی ی\ا حاالت پذیرش ،و∂ ی\ک تاب\ع جام\ع از ∑×Qبه ) P(Qمی باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه127 :  6-4آتاماتای متناهی غیر قطعی زبان NFA Mکه با ) L(Mنشان داده می شود ،مجموعه ای از رشته های پذیرفته شده به وسیله Mاست .بدین صورت که ┴ }qiєFגּL(M)={w l there is a comutation [q0,w] *[qi, ] with گروه کامپيوتر نظریه زبانها و ماشینها صفحه128 :  6-4آتاماتای متناهی غیر قطعی دیاگرام حالت یک M=(Q,∑,∂,q0,F) NFAیک گراف جهت دار Gبا شرایط زیر است: ( iگره های Gعناصر Qهستند. ( iiبرچسب کمانهای Gعناصر ∑ هستند. ( iii q0گره ابتدایی است. ( iv fمجموعه گره های پذیش است. ( vیک کمان از گره qiبه qjبا برچسب aوجود دارداگر ∂(qj=)qi,a باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه129 :  6-4آتاماتای متناهی غیر قطعی مثال: دیاگرامهای حالت M1و M2آتاماتای متناهی را تعریف می کنند که ( *bb(aυb)*)aυbرا می پذیرند. ‏a,b ‏q2 ‏a ‏b ‏q1 ‏b ‏q0 > :M1 ‏a ‏a,b ‏q2 گروه کامپيوتر ‏a,b ‏b ‏q1 ‏b نظریه زبانها و ماشینها ‏q0 > :M2 صفحه130 :  6-4آتاماتای متناهی غیر قطعی ‏a,b ‏q2 ‏a ‏q1 ‏a ‏a,b ‏q0 ‏a,b ‏q4 > :NFA ‏b ‏b گروه کامپيوتر ‏q3 نظریه زبانها و ماشینها صفحه131 :  6-5گذرهای المبدا ی\ک آتاماتای متناه\ی غی\ر قطع\ی ب\ا گذرهل\ی المبدا ی\ک پن\چ تایی ) M=(Q,∑,∂,q0,Fمشاب\ه NFAاس\ت ب\ا ای\ن تفاوت ک\ه ∂ تابعی از Q×(∑υ{ })λبه ) P(Qمی باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه132 :  6-5گذرهای المبدا مثال: م\ی خواهی\م از گذرهای المبدا برای ایجاد ی\ک גּ -NFAک\ه رشت\ه های\ی به طول زوج را بروی { }a,bم\ی پذیرد ،اس\تفاده کنیم .ابتدا دیاگرام حال\ت را برای ماشینی که رشته های به طول دو را می پذیرد تشکیل می دهیم. ‏q2 ‏a,b گروه کامپيوتر ‏q1 ‏a,b ‏q0 نظریه زبانها و ماشینها > صفحه133 :  6-5گذرهای المبدا برای پذیرش رشت\ه ته\ی ،ی\ک کمان المبدا از q0ب\ه q2اضاف\ه م\ی شود .رشت\ه هایی ب\ه طول زوج مثب\ت ب\ا اس\تفاده از کمان المبدای q2ب\ه q0برای تکرار دنباله q2,q1,q0پذیرفته می شوند. גּ ‏q2 ‏a,b ‏q1 ‏a,b ‏q0 > גּ گروه کامپيوتر نظریه زبانها و ماشینها صفحه134 :  6-6حذف غ\یر قطعیت همبستگی المبدای یک حالت ، qiکه با –)closure(qiגּ نشان داده می شود ،به صورت بازگشتی زیر تعریف می شود. ( iپایهclosure(qi)– :גּ є qi ( iiمرحله بازگشت :فرض کنید که qjیک عنصر از qkє∂(qباشد ،آنگاه )closure(qiגּ باشد.اگر ) j,גּ )closure(qjגּ є qkاست. – – ( iiiهمبستگی qj :در –)closure(qiגּ است اگر بتواند با یک تکرار متناهی ازمرحله بازگشت بدست آید. گروه کامپيوتر نظریه زبانها و ماشینها صفحه135 :  6-6حذف غ\یر قطعیت مثال: جدولهای گذر برای تابع گذر∂ و تابع گذر ورودی tیک גּ -NFAبه همراه دیاگرام Mارائه شده است .زبان *M،a+c*bمی باشد. ‏b ‏a ‏a ‏q1 ‏q0 > :M ‏a גּ ‏q2 ‏c گروه کامپيوتر نظریه زبانها و ماشینها صفحه136 :  6-6حذف غ\یر قطعیت גּ ‏c ‏b ‏a ∂ ‏ø ‏ø ‏ø {}q1,q2,q3 ‏q0 ‏ø ‏ø { }q1 ‏ø ‏q1 { }q1 {}q2 ‏ø ‏ø ‏c ‏b ‏a ‏t ‏ø ‏ø {}q1,q2,q3 ‏q0 ‏ø { }q1 ‏ø ‏q1 {}q1,q2 { }q1 ‏ø گروه کامپيوتر نظریه زبانها و ماشینها ‏q2 ‏q2 صفحه137 :  6-6حذف غ\یر قطعیت مثال: ماش\ینهای M1و M2به ترتیب )*a(baو *aرا می پذیرند. ‏a ‏a ‏q3 > :M2 ‏q2 ‏q1 ‏b گروه کامپيوتر نظریه زبانها و ماشینها > :M1 صفحه138 :  6-6حذف غ\یر قطعیت با ایجاد یک حالت ابتدایی جدید و اتصال آن به حاالت ابتدایی ماشینهای اصلی با استفاده از گذر المبدا می توانیم یک MגּNFA- بسازیم که *a(ba)*υaرا بپذیرد. ‏a ‏q1 ‏q2 ‏b גּ ‏q0 ‏a > :M גּ ‏q3 گروه کامپيوتر نظریه زبانها و ماشینها صفحه139 :  6-6حذف غ\یر قطعیت تابع گذر ورودی Mبه صورت زیر است: ‏b ‏a ‏t ‏ø {}q2,q3 ‏q0 ‏ø {}q1 ‏q1 {}q1 ‏ø ‏ø {}q3 گروه کامپيوتر ‏q2 ‏q3 نظریه زبانها و ماشینها صفحه140 : فصل هفتم :زبانها و مجموعه های با قاعده اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: آتاماتای متناهی و مجموعه های با قاعده گراف عبارت ‏زبان بی قاعده گروه کامپيوتر نظریه زبانها و ماشینها صفحه141 : فصل هفتم :زبانها و مجموعه های با قاعده گرامرها به عنوان تولید کننده های زبان ،و آتاماتای متناهی به عنوان پذیرنده های زبان معرفی شده اند. هر آتاماتای متناهی با الفبای ∑ یک زبان روی ∑ را می پذیرد. خانواده زبانهای پذیرفته شده توسط آتاماتا دقیق ًا شامل مجموعه های باقاعده روی ∑ است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه142 :  7-1آتاماتای متناهی و مجموعه های با قاعده مجموع\ه های ب\ا قاعده ب\ا استفاده از عملیات اجتماع، الحاق و عملگر س\تاره( )kleen starاز عناصر پایه ای ایجاد می شوند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه143 :  7-1آتاماتای متناهی و مجموعه های با قاعده فرض کنید که FM ,SMو F M,S Mبه ترتیب حاالت ابتدایی و پایانی ‏M1و M2باشند.حاالت ابتدایی و پایانی ماشین را با Sو Fنشان می دهیم .زبان ) L(M1)υL(M2توسط ماشین زیر پزیرفته می شود: 1 גּ 1 2 2 ‏M1 ‏FM1 ‏SM1 גּ >S ‏F גּ ‏FM2 ‏M2 گروه کامپيوتر ‏S ‏M2 نظریه زبانها و ماشینها גּ صفحه144 :  7-2گراف عبارات گراف عبارات :ی\ک گراف جه\ت دار اس\ت که برچسب کمانهای آ\ن عبارات ب\ا قاعده م\ی باشند .ی\ک گراف عبارت ،همانن\د یک دیاگرام حال\ت ،شام\ل ی\ک گره ابتدای\ی مجزا و ی\ک مجموعه از گره های پذیرش است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه145 :  7-2گراف عبارات دیاگرام حال\ت ی\ک آتامات\ا ب\ا الفبای ∑ را م\ی توان ب\ه عنوان یک گراف عبارت در نظ\ر گرفت .برچس\ب ه\ا شام\ل المبدا و عبارات متناظ\ر با عناص\ر ∑ م\ی باشند .کمانهای ی\ک عبارت م\ی توانن\د با øنی\ز برچسب دار شوند .ه\ر مس\یر در ی\ک گراف عبارت ،ی\ک عبارت ب\ا قاعده تولید م\ی کند .زبان ی\ک گراف عبارت اجتماع\ی از مجموع\ه های ارائه شده توسط عبارات با قاعده پذیرفته شده است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه146 :  7-2گراف عبارات مثال: ‏b ‏b ‏cc 3 > 1 این گراف عبارت *b*ccbرا می پذیرد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه147 :  7-2گراف عبارات قضیه : kleen یک زبان Lتوسط یک DFAبا الفبای∑ پذیرفته می شود اگر و تنها اگر Lیک مجموعه با قاده روی∑ باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه148 :  7-3گرامرهای باقاعده و آتاماتای متناهی ی\ک محاس\به در ی\ک آتامات\ا ب\ا رشت\ه ورودی شروع شده ،چپ تری\ن عنص\ر را ب\ه ترتی\ب پردازش کرده و پ\س از تحلی\ل کامل رشت\ه متوق\ف م\ی شود.از طرف دیگ\ر ،تولی\د ب\ا عنص\ر ابتدایی گرام\ر شروع شده و عناص\ر پایان\ی را ب\ه پیشون\د فرم جمله ای مشتق شده اضافه می کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه150 :  7-3گرامرهای باقاعده و آتاماتای متناهی مثال: گرامر زیر زبان ) a*(aυb+را تولید نموده و NFA Mآن را می پذیرد. ‏b ‏a ‏B ‏b ‏S > :M ‏aS l Bb a גּ ‏G: S ‏bB l ‏a ‏Z گروه کامپيوتر نظریه زبانها و ماشینها صفحه151 : ‏B  7-3گرامرهای باقاعده و آتاماتای متناهی مثال: ‏b ‏S ‏B > ‏b ‏a ‏a ‏a ‏a ‏b ‏A ‏C ‏aA l bB ‏S ‏aS l bC ‏A גּ bS l aC l ‏B ‏aB l bA ‏C ‏b گروه کامپيوتر نظریه زبانها و ماشینها صفحه152 :  7-4ویژگیهای همبستگی زبانهای باقاعده یک زبان روی الفبای با قاعده است ،اگر آن: ( iیک مجموعه (عبارت) باقاعده روی∑ ( iiپذیرفته شده توسط NFA,DFAیا גּ -NFA ( iiiتولید شده توسط یک گرامر با قاعده باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه153 :  7-4ویژگیهای همبستگی زبانهای باقاعده قضیه اگر L1و L2دو زبان با قاعده باشند ،آنگاه L1L2 , L1υL2و *L1نیز زبانهای باقاعده خواهند بود. بسته هستند .اگر Lروی الفبای∑ زبانهای باقاعده نسبت به عمل مکمل _ با قاعده باشد ،آنگاه L=∑*-Lنیز با قاعده خواهند بود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه154 :  7-4ویژگیهای همبستگی زبانهای باقاعده قضیه _ اگر Lیک زبان با قاعده باشد ،آنگاه Lنیز باقاعده است. قضیه اگر L1و L2زبانهایی باقاعده باشند ،آنگاه L1∩L2نیز باقاعده است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه155 :  7-5یک زبان بی قاعده زبانهای بی قاعده: زبان { }ai bi l i≥0با قاعده نیست. فرض کنید که Lیک زبان روی∑ باشد .اگر رشته های є∑ ui و( *∑viє)i≥0با uiviєLو u/ivjєLبرای i≠jوجود داشته باشد ،آنگاه L یک زبان باقاعده نیست. ال مجموعه Lشامل رشته های متقارن روی {، }a,bباقاعده نیست. مث ً گروه کامپيوتر نظریه زبانها و ماشینها صفحه156 :  7-5یک زبان بی قاعده نکته: اشتراک دو زبان باقاعده یک زبان با قاعده تولید می کند. نکته: اشتراک یک زبان با قاعده با یک زبان مستقل از متن باقاعده نیست. قضیه: فرض کنید که L1یک زبان با قاعده و L2یک زبان مستقل از متن باشد .زبان L1∩L2لزوم ًا باقاعده نیست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه157 :  7-6پیش قضیه فشار برای زبانهای باقاعده فرض کنید که Gدیاگرام حالت یک DFAبا kحالت بوده و pیک مسیر به طول kیا بیشتر باشد .در این صورت مسیر pرا می توان به زیر مسیرهای r,pو sتجزیه نمود بطوریکه p=qrsو length(qr)≤kبوده و rیک چرخه باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه158 :  7-6پیش قضیه فشار برای زبانهای باقاعده قضیه: فرض کنید که Lیک زبان با قاعده است که توسط یک DFA M با kحالت پذیرفته می شود و فرض کنید که zهر رشته موجود در Lبا length(z)≤kباشد.در این صورت zمی تواند به صورت uwvنوشته شود بطوریکه length(uv)≤k ، length(v)>0و به ازای هر i≥0 ، uv ‏i w є Lباشد. پیش قضیه فشار ابزار قدرتمندی برای اثبات بی قاعدگی زبانها است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه159 :  7-6پیش قضیه فشار برای زبانهای باقاعده مثال: برای اینک\ه نشان دهی\م { }a i b i l i≥0ب\ا قاعده نیس\ت بایس\تی رشته ای را ب\ا طول مناس\ب در Lپیدا کنی\م ک\ه هی\چ رشت\ه فشردن\ی برای آن وجود نداشت\ه باشد.فرض م\ی کنی\م ک\ه Lباقاعده اس\ت K .را تعداد مشخص شده توس\ط پی\ش قضی\ه فشار در نظ\ر م\ی گیریم .با فرض اینکه zرشته a ‏k bkاس\ت ،هر تجزیه uvwاز zک\ه در شرایط پی\ش قضیه فشار صدق می کند بایستی به شکل زیر باشدکه i+j≤kو j>0است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه160 :  7-6پیش قضیه فشار برای زبانهای باقاعده ‏k ‏w ‏a k-i-jb ‏v ‏j ‏a ‏j ‏u ‏ai ‏k فشار هر زیر رشته به این شکل uv w=a b a a b =a a bk ،را تولید می کند که در زبان Lوجود ندارد .از آنجائیکه zєLهیچ تجزیه ای ندارد که در شرایط پیش قضیه صدق کند ،لذا نتیجه می گیریم که زبان Lبا قاعده نیست. گروه کامپيوتر ‏k ‏j ‏j ‏i ‏k-i-j نظریه زبانها و ماشینها 2 صفحه161 :  7-6پیش قضیه فشار برای زبانهای باقاعده قضیه: فرض کنید که Mیک DFAبا kحالت باشد. () i L(Mاگر وتنها اگر Mیک رشته zبا length(z)>kرا بپذیرد. () ii L(Mبه تعداد نا متناهی عضو دارد اگر وتنها اگر Mیک رشته zبا length(z)<2kرا بپذیرد. فرض کنید که M1و M2دو DFAباشند .یک روال تصمیم گیری برای تعیین هم ارزی M1و M2وجود دارد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه162 : فصل هشتم :آتاماتای Pushdown اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: آتاماتای Pushdown انواع PDA ‏آتاماتای دو پشته ای ‏بهینه سازی DFA گروه کامپيوتر نظریه زبانها و ماشینها صفحه163 : زبانهای باقاعده ب\ه عنوان زبانهای\ی تولی\د شده توسط گرامرهای باقاعده و پذیرفته شده توسط آتاماتای متناهی شناخته می شود. ی\ک آتاماتای ، pushdownی\ک ماشی\ن ب\ا حاالت متناه\ی همراه با ی\ک حافظ\ه پشت\ه ای خارج\ی اس\ت .افزودن ی\ک پشت\ه ب\ه آتاماتا قابلیت مدیریت حافظه LIFOرا فراهم می کند. ‏LIFO : Last-In , First-Out گروه کامپيوتر نظریه زبانها و ماشینها صفحه164 :  8-1آتاماتای pushdown ∩ یک آتاماتای ، pushdownیک شش تایی ( )Q,∑,Γ,∂,q0,Fاست که Qیک مجموعه متناهی از حاالت ∑ ،یک مجموعه متناهی موسوم به الفبای ورودی Γ ،یک مجموعه متناهی موسوم به الفبای پشته q0،حالت F _ Q ،یک مجموعه متناهی از حاالت پایانی ،یک تابع ابتدایی گذر از )} Q×(∑υ{λ}) ×(Γ υ{λبه زیر مجموعه های )}Q× (Γ υ{λ می باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه165 :  8-1آتاماتای pushdown یک PDAدارای دو الفباست: -1الفبای ورودی ∑که رشته های ورودی را شکل می دهد. -2الفبای Γکه عناصر آن ممکن است روی پشته ذخیره شوند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه166 :  8-1آتاماتای pushdown نکته عناصر الفبای پشته ای را با حروف بزرگ نشان می دهیم. رشته های عناصر پشته ای را با استفاده از حروف یونانی نشان می دهیم. یک PDAبا استفاده از حالت جاری ،عنصر ورودی و عنصر باالیی پشته رفتار ماشین را تعیین می کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه167 :  8-1آتاماتای pushdown گذر زیر سبب می شود: عنصر جاری ورودی عنصر جدید پشته [ ∂ ( q1 , a , A ) ] qj , B عنصر جاری پشته ‏є حالت جدید حالت جاری الف) حالت ماشین را از qiبه qjتغییر می دهد. ب) عنصر aرا پردازش کند( هد نوار را به جلو براند). ج) Aرا از باالی پشته حذف کند( عمل .) pop د) Bرا در پشته قرار دهد ( عمل .) pop گروه کامپيوتر نظریه زبانها و ماشینها صفحه168 :  8-1آتاماتای pushdown یک آتاماتای pushdownمی تواند توسط یک دیاگرام حالت نیز توصیف شود .برچسب روی کمانها ،عنصر ورودی و عمل پشته را مشخص می کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه169 :  8-1آتاماتای pushdown ‏i }a bi li≥0ایجاد حال می توانیم یک PDA Mبرای پذیرش زبان { کنیم. }M: Q={q0,q1 גּ /b A ‏q1 ∑={}a,b ‏A/גּ a גּ /b A ‏q0 }Γ ={A > }F={q0,q1 ∂(q0,aגּ}]q0,A[{=) , גּ ∂(}] ,q1[{=)q0,b,A גּ گروه کامپيوتر ∂(}] ,q1[{=)q1,b,A نظریه زبانها و ماشینها صفحه170 :  8-1آتاماتای pushdown ┴ فرض کنید که ( )Q,∑,Γ,∂,q0,Fیک PDAباشد .یک رشته محاسبه [, ,qi[ * ] ,qλ0,w *∑wєتوسط Mقابل پذیرش است اگر یک λ λ ] وجود داشته باشد بطوریکه qi є Fباشد .زبان Mمجموعه تمامی رشته های پذیرفته شده توسط Mاست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه171 :  8-1آتاماتای pushdown ب\ه محاس\به ای ک\ه ی\ک رشت\ه ورودی را م\ی پذیرد ،محاسبه موفق گفت\ه م\ی شود و به محاس\به ای که تمام رشته ورودی را پذیرفت\ه و در ی\ک حال\ت غی\ر پذیرش متوق\ف می شود، محاسبه ناموفق گفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه172 :  8-1آتاماتای pushdown مثال: PDA Mز\بان{} }*w c Rw l wє{a,bرا م\یپ\\ذیرد. }])={[q0,Aגּ ∂(q0,a, }M: Q={q0,q1 }])={[q1,Bגּ ∂(q0,b, ∑={}a,b,c גּ גּ ∂(q1,c, )={[q }] 1, ∂גּ(}] ,q1[{=)q1,a,A }Γ={A,B }F={q1 ∂גּ(}] ,q1[{=)q1,b,B ‏B/גּ b ‏A/גּ a גּ /b B גּ /a A ‏q1 گروه کامپيوتر גּ/גּ c ‏q0 > نظریه زبانها و ماشینها صفحه173 :  8-1آتاماتای pushdown یک PDAقطعی است اگر حداکثر یک گذر برای هر ترکیبی از حالت، عنصر ورودی و عنصر باالی پشته وجود داشته باشد. دو گذر [ є∂(qi.u.A)]qj,cو [ є∂(qi,v,B)]qk,Dسازگار هستند اگر یکی از شرایط زیر را دارا باشند: ( i u=vو .A=B גּ גּ ( ii u=vو =Aیا . =B גּ ( iii A=Bو u=vیا . =v גּ גּ גּ גּ ( =iv uیا =vو =Aیا . =B گروه کامپيوتر نظریه زبانها و ماشینها صفحه174 :  8-1آتاماتای pushdown یک PDAقطعی است اگر آن شامل گذرهای سازگار مجزا نباشد. مثال: ‏i } L={ai l i≥0} {a ib I≥0شامل aها یا تعداد یکسانی از aها و زبان ‏bها است .پشته PDA Mکه زبان Lرا می پذیرد. גּ /b A ‏q1 ‏A/גּ a גּ /b A 0 > :M q גּ /גּ גּ גּ /Aגּ گروه کامپيوتر ‏q2 نظریه زبانها و ماشینها صفحه175 :  8-2انواع PDA هر گذر در PDAبا سه عمل همراه است: pop-1کردن پشته ‏push-2کردن یک عنصر پشته ای -3پردازش یک عنصر ورودی یک PDAساده (اتمی) است اگر هر گذر تنها موجب وقوع یکی از این عملیات شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه176 :  8-2انواع PDA گذر ها در یک PDAساده به اشکال زیر می باشند: ‏qj,Aגּ] ) є ∂(qi, , [ גּ [,qjגּ ] ) ∂(qi,a,גּє [] ,qjגּ)∂(qi, ,Aגּє ی\ک گذر توس\عه یافت\ه ،ی\ک عم\ل روی PDAاس\ت ک\ه ی\ک رشته از عناص\ر را در پشت\ه pushم\ی کند .گذر[ є∂(qi,u,A)]qi,BCDرشته BCDرا در پشته pushمی کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه177 :  8-2انواع PDA مثال: فرض کنید که } L={ai bi l i≥1است. ‏PDAت\\وس\عه ی\\اف\ته }Q={q0,q1 ‏PDA ‏Q={q0,q س,q\2 },q3,q4 \اد\1ه\ )={[}] ,q3 ∂גּ( ,q0,aגּ )={[}]q2,A ∂( ,q0,aגּ ∂(גּ}] ,q1[{=) q0,b,A }]q2,A ∂( , ,q3גּ )={[ גּ )={[ גּ ∂( , ,q2גּ }]q0,A ∂גּ(}] ,q1[{=)q1,b,A )={[ גּ ∂( , ,q2גּ }]q0,A ∂(גּ}] ,q1[{=)q0,b,A ∂גּ( ,q0,bגּ )={[}] ,q4 ∂גּ(}] ,q1[{=)q1,b,A )={[}]q2,A ∂( ,q0,aגּ ‏PDA }Q={q0,q1,q2 ∂(גּ1[{=)q4, ,Aגּ}] ,q גּ ∂( ,q1,bגּ)={[] ,q4 گروه کامپيوتر نظریه زبانها و ماشینها صفحه178 :  8-2انواع PDA پیش قضیه: فرض کنی\د Lی\ک زبان پذیرفت\ه شده توسط (PDA )Q,∑,Γ,∂,q0,F Mب\ا پذیرش تعری\ف شده توس\ط حال\ت پایان\ی باشد .در ای\ن صورت ی\ک PDAوجود دارد ک\ه زبان Lرا توس\ط حال\ت پایان\ی و پشت\ه خالی بپذیرد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه179 :  8-2انواع PDA پیش قضیه: فرض کنی\د Lی\ک زبان پذیرفت\ه شده توسط (PDA M )Q,∑,Γ,∂,q0,F ب\ا پذیرش تعری\ف شده توس\ط پشت\ه خال\ی باشد .در ای\ن ص\ورت یک PDAوجود دارد ک\ه زبان Lرا توس\ط حال\ت پایان\ی و پشت\ه خالی بپذیرد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه180 :  8-2انواع PDA قضیه: شرایط زیر با هم معادلند: ( iزبان Lتوسط برخی PDAها پذیرفته می شود. ( iiیک PDAM1با LF(M1)=Lوجود دارد. ( iiiیک PDAM2با LE(M2)=Lوجود دارد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه181 :  8-3آتاماتای pushdownو زبانهای مستقل از متن قضیه: فرض کنی\د ک\ه Lی\ک زبان مس\تقل از متن باشد .در ای\ن ص\ورت PDAای وجود دارد که زبان Lرا بپذیرد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه182 :  8-3آتاماتای pushdownو زبانهای مستقل از متن فرض کنید که ( M= )Q,∑,Γ,∂,q0,Fیک PDAباشد ،یک PDA ′Mتوسعه یافته با تابع گذر∂ ′بوسیله گذرهای ∂ از Mایجاد می شود: є∂(qباشد ،آنگاه برای هر AєΓداریم ( iاگر [,qiגּ ]) i,u,גּ ). є∂′(qi,u,A []qj,A ( iاگر [ גּ є∂(qi,u, )]qj,Bباشد ،آنگاه برای هر AєΓداریم [. є∂′(qi,u,A) ]qj,BA گروه کامپيوتر نظریه زبانها و ماشینها صفحه183 :  8-3آتاماتای pushdownو زبانهای مستقل از متن مثال: یک گرامر از PDA Mایجاد می کنیم .زبان Mمجموعه {}a n cb nl n≥0 است. }])={[q0,Aגּ ∂(q0,a, }M: Q={q0,q1 }]גּ )={[q1,גּ ∂(q0,c, ∑={}a,b,c גּ}] ∂(q1,b,A)={[q1, }Γ={A }F={q1 گروه کامپيوتر نظریه زبانها و ماشینها صفحه184 :  8-3آتاماتای pushdownو زبانهای مستقل از متن قضیه: فرض کنی\د ک\ه Mی\ک PDAباشد .در این ص\ورت ی\\ک گرام\ر مس\تقل از مت\ن Gبا ) L(G)=L(Mوجود دارد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه185 :  8-4پیش قضیه فشار برای زبانهای مستقل از متن پیش قضیه: فرض کنید که Gیک گرامر مستقل از متن در فرم نرمال شومسکی و n-1از *∑ w єبا درخت اشتقاق Tباشد .اگر عمقT A * wیک اشتقاق برابر nباشد ،آنگاه length(w)≤2خواهد بود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه186 :  8-4پیش قضیه فشار برای زبانهای مستقل از متن فرض کنی\د ) G=(V,∑,P,Sی\ک گرام\ر مس\تقل از متن در فرم نرمال شومسکی و S * wیک اشتقاق از ) w L(Gاست. اگ\ر length(w)≤2ⁿباش\د ،آنگاه عم\ق درخ\ت اشتقاق حداقل برابر n+1خواهد بود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه187 :  8-4پیش قضیه فشار برای زبانهای مستقل از متن قضیه (پیش قضیه فشار برای زبانهای مستقل از متن) فرض کنی\د ک\ه Lی\ک زبان مس\تقل از مت\ن باشد.ی\ک عدد kوابس\ته به L وجود داردبطوریک\ه ه\ر رشت\ه ZєLب\ا length(z)>kم\ی توان\د ب\ه صورت z=uvwxyنوشته شود که دارای شرایط زیر باشد. (i length(vwx)≤ k (ii length(v)+length(x)>0 ( iiiبرای ii≥0 i ، uv wx y є L زبان } ) length(wاول است .L={w єa* lمستقل از متن نیست گروه کامپيوتر نظریه زبانها و ماشینها صفحه188 :  8-5خصوصیات همبستگی زبانهای مستقل از متن قضیه: مجموعه زبانهای مستقل از متن نسبت به عملیات اجتماع ،الحاق و عملگر ستاره ( )kleen starبسته هستند. قضیه: مجموعه زبانهای مستقل از متن نسبت به عملیات اشتراک و مکمل بسته نیست. قضیه: فرض کنید که Rیک زبان با قاعده و Lیک زبان مستقل از متن باشد. در این صورت R∩Lمستقل از متن است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه189 :  8-6آتاماتای دو پشته ای آتاماتای دو پشته ای: \ت PDAدو پ\\شته ا\یدارا\یس\\اخ\تار ( )Q,∑,Γ,∂,q0,Fا\س . Q,∑,Γ,∂,q0,Fم\شاب\ه PDAت\\کپ\\شته ا\یم\یب\\اش\ند .ت\\اب\ع گ\\ذر∂ ،ت\\اגּب\عی از )} גּ{ })×(Γυגּ { Q×(∑υ{ })×(Γυب\\ه ز\یر גּ \ت م\جموعه هاییاز )}גּ { Q×(Γυ{ })×(Γυا\س . حالت عناصر ورودی و عناصر باالی هر دو پشته تعیین می کنند که کدام گذر بایستی انتخاب شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه190 :  8-6آتاماتای دو پشته ای مثال: PDAدو پ\\شته ا\یت\\ع\ریفش\\ده\ ز\یر ز\بان} L={a i b i c i l i≥ 0را م\ی پ\\ذیرد. }]גּ ,גּ )={[q2,גּ ,גּ ,גּ ∂(q0, }M: Q={q0,q1,q2 }]גּ )={[q0,A,גּ ,גּ ∂(q0,a, ∑={}a,b,c }],Aגּ )={[q1,גּ ∂(q0,b,A, }Γ={A גּ }])={[q1, ,Aגּ ∂(q1,b,A, }F={q2 }]גּ ,גּ ,A)={[q2,גּ ∂(q1,c, }]גּ ,גּ ,A)={[q2,גּ ∂(q2,c, گروه کامپيوتر نظریه زبانها و ماشینها صفحه191 : فصل نهم:ماشینهای تورینگ اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: ماشین تورینگ انواع پذیرش ‏ماشین های چند شیاره ‏ماشین های تورینگ غیر قطعی گروه کامپيوتر نظریه زبانها و ماشینها صفحه192 : فصل نهم :ماشینهای تورینگ ماشین تورینگ یک ماشین با حاالت متناهی است که هر گذر آن عنصری را روی نوار چاپ می کند. ماشی\ن تورین\گ ی\ک پن\چ تای\ی ( )Q,∑,Γ,∂,q0اس\ت ک\ه در آ\ن Qمجموعه متناه\ی از حاالت Γ ،ی\ک مجموع\ه متناه\ی موس\وم ب\ه الفبای نوارشام\ل یک عنص\ر ویژ\ه Bک\ه نماینگ\ر فاص\له خال\ی اس\ت∑ ،ی\ک مجموعه از }Γ–{B موس\وم ب\ه الفبای ورودی∂ ،ی\ک تابع جزئ\ی از Γ × Qبه }Q×Γ× {L×R موس\وم ب\ه تاب\ع گذر و q0єQی\ک حال\ت مشخ\ص ب\ه نام حال\ت ابتدایی می باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه193 :  9-1ماشین تورینگ استاندارد نوار یک ماشین تورینگ در یک جهت تا بی نهایت ادامه می یابد. مکانهای نوار با اعداد طبیعی از چپ به راست شماره گذاری می شوند. 1 0 … 5 4 3 2 … ‏q0 گروه کامپيوتر نظریه زبانها و ماشینها صفحه194 :  9-1ماشین تورینگ استاندارد یک گذر شامل سه عمل است: -1تغییر حالت -2نوشتن یک عنصر روی مربع در حال پویش توسط هد نوار -3حرکت هد نوار. جهت حرکت توسط آخرین جزء گذر تعیین می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه195 :  9-1ماشین تورینگ استاندارد ای\ن گذر حال\ت ماشی\ن را از qiب\ه qjتغیی\ر داده ،عنص\ر xنوار را با y جایگزین نموده و هد نوار را یک مکان به چپ حرکت می دهد. ی\ک ماشی\ن تورین\گ هنگام\ی متوق\ف م\ی شود ک\ه برای زوج مرتب حال\ت جاری و عنص\ر ورودی ،هی\چ گذری تعری\ف نشده باشد .یک گذر ممک\ن اس\ت بخواه\د از مکان ص\فر نوار ی\ک حرک\ت ب\ه چپ محدوده نوار انجام ده\د ک\ه در ای\ن ص\ورت متوق\ف م\ی شود و ب\ه این نوع توق\ف ،توق\ف غی\ر عادی گوییم .هرگاه م\ی گویی\م ی\ک محاسبه متوقف می شود ،منظور توقف در شرایط عادی است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه196 :  9-1ماشین تورینگ استاندارد مثال: ماشین تورینگ COPYبا الفبای ورودی { }a,bیک کپی از رشته ورودی را تولید می کند .به عبارتی ،محاسبه ای که با نوار شامل BuBشروع می شود با نوار BuBuBمتوقف می گردد. ‏X/X R ‏Y/Y R ‏a/a R ‏b/b R ‏a/a R ‏b/b R ‏B/a L ‏a/a L ‏b/b L ‏B/B L ‏q4 ‏q3 ‏B/B R ‏q2 ‏B/b L ‏a/X R ‏b/Y R ‏q6 ‏B/B R ‏q5 ‏q1 ‏B/B R ‏q0 > :COPY ‏B/B L ‏q7 ‏a/a R ‏b/b R گروه کامپيوتر ‏a/a R ‏b/b R ‏X/a L ‏Y/b L نظریه زبانها و ماشینها صفحه197 :  9-2ماشین تورینگ به عنوان پذیرنده زبان فرض کنی\د که ( )Q,∑,Γ,∂,q0,Fیک ماشین تورینگ باشد. ی\ک رشت\ه *∑Uєتوس\ط حال\ت پایان\ی پذیرفت\ه م\ی شود اگر محاس\به Mب\ا ورودی uدر ی\ک حال\ت پایان\ی متوقف شود. محاس\به ای ک\ه ب\ه طور غی\ر عادی متوق\ف م\ی شود رشته ورودی را بدون توج\ه ب\ه حال\ت پایان\ی ماشی\ن رد م\ی کند .زبان ، Mکه ب\ا ) L(Mنشان داده م\ی شود ،مجموع\ه تمام\ی رشته های پذیرفته شده توسط Mاست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه198 :  9-2ماشین تورینگ به عنوان پذیرنده زبان یک زبان پذیرفته شده توسط یک ماشین تورینگ به زبان بازگشتی شمارش پذیر موسوم است. ماشین تورینگی که برای تمامی رشته های ورودی متوقف می شود زبانی را می پذیرد که به آن بازگشتی گویند. بازگشت\ی بودن از ویژگیهای ی\ک زبان اس\ت ن\ه از خصوصیات ماشین تورینگ پذیرنده آن. گروه کامپيوتر نظریه زبانها و ماشینها صفحه199 :  9-2ماشین تورینگ به عنوان پذیرنده زبان مثال: ماش\ین تورینگ ‏b/b R ‏q3 ‏a/a R ‏q2 ‏a/a R ‏q1 ‏B/B R > :M q 0 ‏b/b R زبان ( *aa(aυb)*)aυbرا می پذیرد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه200 :  9-3انواع پذیرش در ماشینهای توری\نگ انواع پذیرش در ماشینهای تورینگ: در ماشی\ن تورینگ\ی ک\ه برای پذیرش توس\ط توقف طراح\ی شده اس\ت ،ی\ک رشت\ه ورودی پذیرفت\ه می شود اگر محاسبه رشته موجب توقف ماشین شود. فرض کنی\د ک\ه ( )Q,∑,Γ,∂,q0,Fی\ک ماشی\ن تورین\گ با پذیرش توس\ط توق\ف باشد .ی\ک رشت\ه *∑Uєتوس\ط توقف پذیرفت\ه م\ی شود اگ\ر محاس\به Mب\ا ورودی uبه طور عادی متوقف شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه201 :  9-3انواع پذیرش در ماشینهای توری\نگ مثال :زبان (*aa(aυb)*)aυb ‏b/b R ‏q3 ‏a/a R ‏q2 ‏B/B R ‏a/a R ‏q1 ‏b/b R ‏B/B R ‏B/B R > q0 ‏a/a R ‏b/b R ‏qf ‏a/a R ‏b/b R ‏B/B R گروه کامپيوتر نظریه زبانها و ماشینها صفحه202 :  9-3انواع پذیرش در ماشینهای توری\نگ نوع\ی از پذیرش موس\وم ب\ه پذیرش توس\ط ورود ک\ه از حال\ت پایانی استفاده کرده و هیچ نیازی به محاسبات پذیرس جهت توقف ندارد. ی\ک رشت\ه پذیرفت\ه م\ی شود اگ\ر محاس\به وارد یک حالت پایانی شده باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه203 :  9-4ماشینهای چند شیاره یک نوار چند شیاره نواری است که به شیارهای متععدی تقسیم شده باشد .یک مکان در یک نوار nشیاره شاما nعنصر از الفبای نوار است. دیاگرام زیر یک نوار دو شیاره با هد نوار در حالت پویش دو مکان معین را نشان می دهد. شیار 2 شیار 1 ‏qi گروه کامپيوتر نظریه زبانها و ماشینها صفحه204 :  9-4ماشینهای چند شیاره قضیه: ی\ک زبان Lتوس\ط ی\ک ماشی\ن تورینگ دو شیاره پذیرفت\ه م\ی شود اگ\ر و تنه\ا اگ\ر آ\ن توس\ط یک ماشین تورینگ استاندارد پذیرفته شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه205 :  9-5ماشین تورینگ با نوار دو طرفه ماشین تورینگ با نوار دو طرفه: ی\ک ماشی\ن تورین\گ ب\ا ی\ک نوار دو طرف\ه مشاب\ه ماشین تورین\گ اس\تاندارد اس\ت ب\ا ای\ن تفاوت ک\ه نوار آ\ن از هر دو طرف تا بینهایت ادامه می یابد. ی\ک ماشی\ن ب\ا نوار دو طرف\ه م\ی توان\د ب\ا قراردادن ی\ک عنصر ویژ\ه روی نوار جه\ت نمای\ش محدوده چ\پ نوار ی\ک طرفه، عملیات یک ماشین استاندارد را شبیه سازی کند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه206 :  9-5ماشین تورینگ با نوار دو طرفه مثال: ماشین تورینگ استاندارد Mرشته هایی را روی { }a,bمی پذیرد که در آن قبل از هر ،bدر صورت وجود ،حداقل سه aوجود داشته باشد. ‏a/a R ‏q5 ‏a/a L ‏B/B L ‏q4 ‏a/a L ‏B/B L ‏q3 گروه کامپيوتر ‏a/a L ‏B/B L ‏q2 ‏b/b L ‏q1 نظریه زبانها و ماشینها ‏B/B R > :M q 0 صفحه207 :  9-5ماشین تورینگ با نوار دو طرفه قضیه: ی\ک زبان Lتوس\ط ی\ک ماشی\ن تورین\گ ب\ا یک نوار دوطرف\ه پذیرفت\ه م\ی شود اگ\ر و تنه\ا اگ\ر آ\ن توسط یک ماشین تورینگ استاندارد پذیرفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه208 :  9-6ماشینهای چند نواره ی\ک ماشی\ن kنواره شام\ل kنوار و kه\د مجزا اس\ت.حاالت و الفباهای یک ماشی\ن چن\د نواره مشاب\ه ماشی\ن تورین\گ اس\تاندارد اس\ت .ماشی\ن به طور همزمان نواره\ا را م\ی خواند.ای\ن کار ب\ا اتص\ال ه\ر ی\ک از هده\ا ب\ه یک ثبّات کنترلی مجزا که حاوی حالت جاری است انجام می شود. نوار 3 نوار 2 نوار 1 ‏qi گروه کامپيوتر نظریه زبانها و ماشینها صفحه209 :  9-6ماشینهای چند نواره یک گذر در یک ماشین چند نواره ممکن است: ( iحالت را تغییر دهد. ( iiیک عنصر روی هر یک از نوارها بنویسد. ( iiiهر یک از هدها را به صورت مجزا جابجا کند. قضیه: یک زبان Lتوسط یک ماشین تورینگ چند نواره پذیرفته می شود اگر و تنها اگر آن توسط یک ماشین تورینگ استاندارد پذیرفته می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه210 :  9-6ماشینهای چند نواره مثال: ماشین تورینگ دونواره ای که دیاگرام حالت آن درزیرآمده است،زبان {} }*uu l uє{a,bرا می پذیرد. ‏x/x R , B/x R ‏q3 ‏x/x L , y/y L ‏x/x L , y/y S ‏x/x R , x/x R ‏q2 ‏B/B L , B/B L ‏q1 ‏B/B R , B/B R > q0 ‏B/B R , y/y R ‏q4 ‏y/y R , B/B R ‏q3 گروه کامپيوتر نظریه زبانها و ماشینها صفحه211 :  9-6ماشینهای تورینگ غیر قطعی ی\ک ماشی\ن تورین\گ غی\ر قطع\ی ممک\ن اس\ت ی\ک تعداد متناه\ی از گذرها را برای ی\ک وضعی\ت مشخ\ص تعی\ن کند .اجزا ی\ک ماشی\ن غی\ر قطع\ی ،به ج\ز تاب\ع گذر ،عین ًا مشاب\ه اجزا ماشی\ن تورین\گ اس\تاندارد اس\ت .گذرها در ی\ک ماشی\ن غی\ر قطع\ی ی\ه وس\یله ی\ک تاب\ع جزئ\ی از Q×Γب\ه زیر مجموعه هایی از } Q×Γ×{L,Rتعریف می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه212 :  9-6ماشینهای تورینگ غیر قطعی مثال: ماشین غیر قطعی زیر رشته هایی را می پذیرد که در آن یک cقبل یا بعد از ab وجود داشته باشد. ‏a/a R ‏b/b R ‏c/c R ‏q4 ‏b/b R ‏q3 ‏a/a R ‏q2 ‏q7 ‏a/a L ‏q6 ‏c/c R ‏q1 ‏B/B R > q0 ‏c/c L گروه کامپيوتر ‏b/b L ‏q5 نظریه زبانها و ماشینها صفحه213 : فصل دهم:طبقه بندی شومسکی اهداف رفتاري: دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: گرامرهای بدون محدودیت گرامرهای وابسته به متن ‏آتاماتای خطی محدود ‏طبقه بندی شومسکی گروه کامپيوتر نظریه زبانها و ماشینها صفحه214 : فصل دهم :طبقه بندی شومسکی گرامرهای بدون محدودی\ت بزرگترین گروه از گرامرهای عبارت م\ی باشند .ی\ک قانون u vمشخ\ص م\ی کن\د ک\ه یک رخداد از زیررشت\ه uدر ی\ک رشت\ه ممک\ن اس\ت ب\ا رشته v جایگزی\ن شود .ی\ک اشتقاق دنبال\ه ای از جایگزین\ی ها مجاز اس\ت .تنه\ا محدودیت\ی ک\ه روی ی\ک قانون از ی\ک گرامر اعمال م\ی شود ای\ن اس\ت ک\ه س\مت چ\پ آ\ن نبایس\تی ته\ی باشد .ب\ه این س\یستمهای بازنویس\ی رشت\ه ه\ا ،گرامرهای نوع ص\فر نی\ز گفت\ه می شود. گروه کامپيوتر نظریه زبانها و ماشینها صفحه215 :  10-1گرامرهای بدون محدودیت یک گرامر بدون محدودیت یک گرامر چهارتایی( )V,∑,P,Sاست که Vیک مجموعه متناهی از متغیرها( ∑ ،الفبا)یک مجموعه متناهی از عناصر پایانی P،یک مجموعه از قوانین و Sیک عنصر مشخص در V می باشد .یک قانون از یک گرامر بدون محدودی به شکل u v + است که در آن )∑ uє(Vυو )∑ *vє(Vυمی باشد.فرض می شود که مجموعه های Vو∑ غیر الحاقی هستند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه216 :  10-1گرامرهای بدون محدودیت گرامرهای باقاعده و مستقل از متن زیر مجموعه هایی از گرامرهای بدون محدودیت هستند .یک گرامر مستقل ازمتن یک گرامر عبارت است که در سمتچپ هر قانون آن تنها یک متغیر وجود دارد .قوانین یک گرامر باقاعده به یکی از اشکال (aB (a ‏iA ‏ii A (λ A ‏iii می باشد که A,BєVو ∑ є aاست. گروه کامپيوتر نظریه زبانها و ماشینها صفحه217 :  10-1گرامرهای بدون محدودیت مثال: ‏i i ‏i گرامر بدون محدودیت زیر با عنصر ابتدایی Sزبان{}a b c l i≥0را تولید می کند. }V={S,A,C ∑={}a,b,c گروه کامپيوتر גּ aAbc l ‏S גּ aAbc l ‏A ‏bC ‏Cb ‏cc ‏Cc نظریه زبانها و ماشینها صفحه218 :  10-1گرامرهای بدون محدودیت قضیه: فرض کنید که ) G= (V,∑,P,Sیک گرامر بدون محدودیت باشد. در این صورت ) L(Gیک زبان بازگشتی شمارش پذیر است. قضیه: فرض کنید که Lیک زبان بازگشتی شمارش پذیر باشد .در این صورت یک گرامر بدون محدودیت Gبا L(G)=Lوجود دارد. قضیه: مجموعه زبانهای بازگشتی شمارش پذیرنسبت به عمل اجتماع ،الحاق و عملگر ستاره ( )kleen starبسته است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه219 :  10-2گرامرهای وابسته به متن گرامرهای وابس\ته ب\ه مت\ن ی\ک مرحل\ه میان\ی بی\ن گرامرهای مس\تقل از متن و گرامرهای بدون محدودی\ت م\ی باشند .در ای\ن گرامره\ا ،هیچ محدودیت\ی برای س\مت چ\پ ی\ک قانون وجود ندارد ،ام\ا طول س\مت راست آن بایستی حداقل به اندازه طول سمت چپ باشد. گروه کامپيوتر نظریه زبانها و ماشینها صفحه220 :  10-2گرامرهای وابسته به متن یک گرامر عبارت وابسته به متن است اگر هر قانون به شکل v + باشد که )∑ uє(Vυو )∑ *vє(Vυو) length(u)≤length(vاست. ‏u ب\ه قانون\ی ک\ه در شرای\ط فوق ص\دق کن\د یکنواخ\ت( )monotonicگفته می شود. قضیه: هر زبان وابسته به متن بازگشتی است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه221 :  10-3آتاماتای خطی محدود ی\\\ک آتاماتای خط\\\ی محدود( )LBAی\\\ک ساختار (=Q,∑,Γ,∂,q0,<,>,F) Mاس\ت ک\ه در آن Q,∑,Γ,∂,q0, F مشاب\ه ماشی\ن تورین\گ غی\ر قطع\ی م\ی باشند .عناص\ر > <,عناصری مشخص از ∑ هستند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه222 :  10-3آتاماتای خطی محدود قضیه: فرض کنی\د ک\ه Lی\ک زبان وابس\ته ب\ه مت\ن اس\ت .در ای\ن صورت، یک آتاماتای خطی محدود Mبا L(M)=Lوجود دارد. قضیه: فرض کنی\د ک\ه Lی\ک زبان پذیرفت\ه شده توس\ط یک آتاماتای خط\ی محدود باشد .در ای\ن ص\ورت }גּ { -Lی\ک زبان وابس\ته به متن است. گروه کامپيوتر نظریه زبانها و ماشینها صفحه223 :  10-4طبقه بندی شومسکی طبقه بندی شومسکی شامل چهار گروه از گرامرها(زبانها) است: -1گرامرهای بدون محدودیت -2گرامرهای وابسته به متن -3گرامرهای مستقل از متن -4گرامرهای باقاعده که به ترتیب به گرامرهای نوع ، 0نوع ، 1نوع ، 2و نوع 3معروفند. گروه کامپيوتر نظریه زبانها و ماشینها صفحه224 :  10-4طبقه بندی شومسکی گرامرها زبانها ماشینهای پذیرنده گرامرهای نوع ،0 زبانهای بازگشتی ماشین تورینگ، گرامرهای عبارات، شمارش پذیر ماشین تورینگ غیر قطعی گرامرهای بدون محدودیت گرامرهای نوع ،1 زبانهای وابسته به متن آتاماتای خطی محدود گرامرهای وابسته به متن، گرامرهای یگنواخت گرامرهای نوع ،2 زبانهای مستقل از متن آتاماتای pushdown گرامرهای مستقل از متن گرامرهای نوع ،3گرامرهای باقاعده، زبانهای باقاعده گرامرهای خطی چپ،گرامرهای خطی راست گروه کامپيوتر آتاماتای متناهی قطعی، آتاماتای متناهی غیر قطعی نظریه زبانها و ماشینها صفحه225 :