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

صفحه 1:
ضح 46 = (اشكله ریم و نظریه زبانها و ماشینها تهیه کننده: سیده فاطمه نورانی گروه: کامپیوتر a 

صفحه 2:
ah ۳ Ae ‏عنوان منبع: نظريه زبانها و ماشينها‎ 3 ‘aa ‏مترجم: مهندس سید حجت الّه جلیلی رس(‎ 2 0۱25 ۸ ۵۲ (WAS = ‏انتشاراتة‎ © كروه كامبيوتر نظريه زبانها و ماشينها صفحه: 2 

صفحه 3:
WY ‏جایگاه درس در رشته کامپیوتر‎ 7 ضرورت این درس: * ضرورت نیاز به زبانهای سطح بالا 5 © ضرورت ترجمه برنامه های نوشته شده با زبان سطح بالا به برنامه به زبان ماشین تنوع زبانهای برنامه نویسی سطح بالا ۴ دروس پیش نیاز: ۴ نوع درس: © تعداد کل ساعات تدریس: 7" تعداد جلسات تدریس: 

صفحه 4:
مقدماتی ات إل: رياضيا فصل او مفا شد: انشجو فصر هد خوا آشنا خوا زير غاهي با ۱ : ۱ : اين هیم ۱ از مطالعه ۱ پس شجو پ دانشح اهیم ری و مغهو تابع اقا اد گذا 3 معهوم ‎wen.‏ ‎a‏ ستقراء ریا 1 گراف و نواع آن ۰ ۲ 

صفحه 5:
UY ‏نمادگذاری‎ ۱-۱ ۴ نماد ۲ «[: اشاره به کوچکترین عدد صحیح بزرگتر يا مساوی ‎anim ote‏ دارد. ۲ -۲۰۷ [--۲ 2۲ ۵ نماد ۲« را حرء صحیم <می نامیم. "1 نماد ام« اشاره به بزرگترین عدد صحیح کوچکتر یا مساوی عدد حقیقی « دارد. ۲۰۷-۲ ۴-۲ ا۵ لب ع نماد ول را ‎je‏ صحيح بابين > مى ناميم. 

صفحه 6:
۱-۲ توابع تلبع ۰۶ تشکیل شده از یک متغیر با قاعده و قانون می باشد که به آزاء یک مقدار «<. مقدار منحصر به فردی رابه (۳6 نسبت می دهد. نمودار یک تابع: مجموعه ای است از کلیه زوجهای مرتب که بوسیله تابع تعیین می شوند. دامنه یک تابع: مجموعه مقادیری است که تابع به ازاء آنها تعریف می شود كروه كامبيوتر_ || نظریه زبانها و ماشینها )| صفحه: 5 

صفحه 7:
WY ‏توابع‎ ۱-۲ تابع جامع: تابعی که از کابه ۷ یک رابطه دودویی روی 2*۲ را داراست. نایم سرنی:رابطه بین ۷*است وقتی که ‎[x,ve]‏ 6و [مر] 6۳ تابع بت به يت تابعی که در آن هر عنصر عبه یک عنصر مجزا در برد تصویر شود. تابع /87- ‎PI‏ برشاست اگر که برد 6 کل مجموعه ۲باشد. 

صفحه 8:
۱-۳ نظریه مجموعه ها نمادهای مجموعه نماد 6 به معنای عضویت است. بطوریکه 2 6 « مشخص می کند که «< یک عضو یا عنصر مجموعه است. از دو براکت [ ] برای تعریف یک مجموعه استفاده می شود. ‎X= {40,9 }‏ مجموعه هایی که تعداد زیاد یا تعداد نامتناهی عضو دارند بایستی به صورت ضمنی تعریف شوند. ‎suber w}‏ سم ‎{ol =? Por sowe‏ 

صفحه 9:
۱-۳ نظریه مجموعه ها زیر مت ت< مجموعه زیر مجموعه )است به طوری که ل" لكر هر عضو ۷۲ عضوعاز نیز باشد اگر ۲ یک زیر مجموعه از کاباشد و ۷(آنگاه به ۲ایک زير مجموعه کامل لا ميگوتيم. 

صفحه 10:
۱-۳ نظریه مجموعه ها اجتماخ دو مجمو به صورت زیر تعریف می شود: 6 2 0۲ 2 6 72 721 ) < 209۷ ‎Y}‏ ‏اختلاف دو مجموعه به صورت زیر تعریف می شود: (۷ 6 72 2901 2 6 7 4۱21 < 2-۷ مكمل © نسيت به آمجموعه عناصری در تآاست که در * نمی باشد. 

صفحه 11:
۱-۴ استقراء ریاضی مفاهیم مورد استفاده در استقراء ریاضی بابه استةرا: عبارت به ازاء 20(یا هر مقدار اولیه دیگر) درست است. ترش استتراء: عبارت برای هر ‎sre‏ دلخواه 20(یا هر مقدار اولیه دیگر) درست است. كام اسنتراء: اكر عبارت به ازاء » درست است. آنگاه به ازاء 1 +10 نيز درست می باشد. 

صفحه 12:
۱-۴ استقراء ریاضی مثال: برای کلیه اعداد صحیح مثبت نشان می دهیم که ‎n+ 1)‏ ‎24+..4n=‏ +14 2 بايه استقراء: براى 0>عداريم: 1=1020 فرض استةرا:فرض كنيد كه براى یک عدد صحیح مثبت دلخواه » 1+ 24+ ..+ naa) 2 ‏داريم:‎ كام استتراء لازم است كه نشان دهيم: ۷( ساب (2+1) جم +.. +2 +1 

صفحه 13:
۱-۵ قضایا و پیش قضلیا :2 در لغت به معنای گفتاری است که صحت آن باید اثبات شود. مثال:برای هر عدد صحیح © ©) داریم: ‎Mn+)‏ 1+2+..4+n= 2 برش تشه به عنوان یک قضیه کمکی برای اثبات قضایای دیگر به کار می رود. 

صفحه 14:
۱-۶ گراف ها نمایشی از یک گراف: اجزای یک گراف: دایره ها نشانگر گره ها(عصسصه خطوط ارتباط گره ها نشانگر لبه (سلحی) 

صفحه 15:
۱-۶ گراف ها كراف جيت دار:اكر هر لبه گراف دارای جهت باشد به آن گراف جهت دار( )می گویند. ترا رزن <ار: اگر به لبه ها مقادیری تخصیص يافته باشدبه آن مقادیر وزن و به آن گراف. گراف وزن دار می گوییم. مسير در یک گراف جهت داربه دنبلله ای از گره ها که بین هر گره و گره بعدی یک لبه وجود داشته باشد گفته می شود. 

صفحه 16:
۱-۶ گراف ها بر ۸2(-): به مسیری که از یک گره شروع شده و به خودش باز می گردد گفته می شود. ترا سره ای.اگر گرافی شامل یک چرخه باشد به آن گراف چرخه ای گفته می شود. مسر ساده: مسیری که از از یک گره دو بار عبور نکند. ‎ob‏ يى مسير در يى كراف وزن دار برابر مجموع وزنهاى ‎Saal ‏مسير‎ ‎ ‎ 

صفحه 17:
۱-۶ گراف ها ترا بدرن رت گرافی که لبه های آن هیچ جهتی نداشته باشند. ترا متس ,گرافی بدون جهت که بین هر دو گره دلخواه از آن یک مسیر مشخص وجود داشته باشد. در .یک گراف بدون جهت. پیوسته و بدون چرخه است. درخت ريشه دار :درختى كه در آن يى كره به عنوان ريشه درخت انتخاب مى شود. درخت يوشا براى 8): يى زير كراف متصل است كه اولآً شامل همه كره هاى ©) بوده و ثانياً يى درخت باشد. 

صفحه 18:
فصل دوم: زبان ها ‎EOE‏ ۲ اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: " مفاهیم رشته و زبان © مشخصات زیان ها " مجموعه های با قاعده 

صفحه 19:
WY ‏رشته ها و زبانها‎ ۲-۱ زبان: یک زبان یک مجموعه از رشته ها روی یک الفبا است. رشته: يك رشته روی یک مجموعه ا یک دنباله متناهی از عناصر ۱۷ است. النباى زبان: به مجموعه عناصرى كه رشته ها از آن ساخته مى شوند الفباى زبان كوثيم. رشته نبي رشته فاقد عنصر را رشته تهی می نامیم که با نشان مى دهیم. 

صفحه 20:
۲-۱ رشته ها و زبانها ‎ye‏ ‏فرض کنید که ‎pais sbby = {abo}‏ * 2 شامل: ۸ طول. وه : طول۱ ‎we ba bb bo va cb oo‏ له كت : طول۲ ‎cob war ube ubb obo wo ub wo‏ تدده ‎Wb‏ ‎bea bub bas bb bbb bbe bra bob bor‏ ‎ob ooo‏ ددج عجان جات دجا ‎pee pub cao‏ 

صفحه 21:
۲-۱ رشته ها و زبانها یک زبان شامل رشته هایی روی النبا است. یک زبان روی یک الفبای 2 یک زیر مجموعه از # 2 است. : الحاق یک عمل دودویی است که دو رشته را به عنوان ورودی گرفته وبا چسباندن آنها در کنار هم یک رشته جدید ایجاد می کند. الحاق عمل اصلی در تولید رشته هاست. 

صفحه 22:
۲-۱ رشته ها و زبانها ‎iS‏ فرض كنيد كدعب 8* باشد الحأة, ::: كه به صورت رف نوشته می شودف یک عمل دودویی روی #2 است که به صورت زير تعريف مى شود: (بابه: اكر 00>(ن)ك ابوط باشد. آنكاه رد و كرف خواهد بود. (8 كام باز كنات: فرض كنيد كه مدي رشته با طول ‎fearth(V)=WO‏ باشد. در اينصورت , به ازاى برخى رشته هاىبمابا طول ‎TE De oer‏ كيو در نتيجة ه(بيى) 2نف خواهد بود. 

صفحه 23:
۲-۱ رشته ها و زبانها مثال فرض كنيد که تلدكف , موب و راکب باشد. در اين صورت: حامج خسن سره کرت ‎w=uboubb (vw) =cbra(w)‏ 

صفحه 24:
۲-۱ رشته ها و زبانها 

صفحه 25:
۲-۱ رشته ها و زبانها معکوس رشته فرض کنید که یک رشته در باشد. معکوس » به صورت زیر تعریف می شود: ‎R‏ ‏( پایه2۰(د) لبط . در اين صورت كب و 2 خواشد بود. )# گام باز گشت: اگر 200() ابا باشد. در اینصورت برای برخی ‎ar Gla aid,‏ طول 4 و برخی ۰6 , سبحی2 معکوس رشته برایرخواهد بود اح كر سح كلو 

صفحه 26:
2-1 رشته ها و زبانها قضيه: فرض كنيد كدسرى *[6 باشد. در این صورت ۷227 < *12۷) است 

صفحه 27:
۲-۲ مشخصات متناهی زبانها یک زبان به صورت یک مجموعه از رشته ها روی یک الفبا تعریف شده است مثالء | زبان مااز رشته هايى روى ارك [ كه با يى ‏ شروع شده و طول زوج دارند به صورت زير تعريف مى شود: (ايايه:را6تدرهه . (8 كام باز گشت:اگر باب باشد. آنگاه رام ماما ,تك رطس رددىاست. (# همبستگی:یک رشته باب است اگر آن بتواند با تکرار متناهی از مرحله گام باز گشت از عنصر پایه ای بدست آید. 

صفحه 28:
۲-۲ مشخصات متناهی زبانها الحاق دو زبان ۲ ,۷ الحاق زبانهای او ۷ که به صورت 2۷ نشان می دهیم. زبان ‎veX aad ve}‏ ا ‎XY=fw‏ است.» مرتبه الحاق 26 با خودش را به صورت ‏ نشان می دهیم. 6 به صورت ۸) [ تعریف می شود. 

صفحه 29:
۲-۲ مشخصات متناهی زبانها ۰ فرض کنید که (صرط,هت)>7 و إدطرتاط) > است. در اينصورت ‎X= ucbb bobb, cobb, drubbarba‏ ‎=X taf‏ ‎X=X= {u,b,0}‏ ‎XO {ug,0b,07,bu,bb,be,ca,cb,00}‏ ‎XC CXS {oon 00h 007 cbu,cbb cbr ,ac0,0cb 007‏ ‎bra, bub, bur, bbu bbb, bbe bru, bob bor‏ ‎{owa, cob car, cba,cbb, che oruocb,oor‏ 

صفحه 30:
2-2 مشخصات متناهی زبانها فرض کنید که 2 یک مجموعه باشد. در این صورت: ‎¥=Ux x =x‏ ‎ial‏ 1-0 شاملت-مامی‌یشته هایی‌دستکه می‌تولنند از عناصر ۷ ساخته شوند ( مجموعه يشته های‌غیر تهیایجاد شدهاز الست 

صفحه 31:
2-2 مشخصات متناهی زیانها زبان ‎ab={a,b}*{bb}u,b}‏ شامل تمامی رشته های روی (اره ۲ است که دارای زیر رشته ‎Qo bb‏ باشد. الحاق مجموعه (عاط] ما را وجود علط در هر رشته از با مطمتن می سازد. مجموعه های (طاره! # مشخص می کنند که هر تعدادی وبا هر ترتيبى مى تولند بعد يا قبل از عاط قرار بگیرند. كروه كامبيوت نظريه زبانها و ماشینها ‏ صفحه 31 | 

صفحه 32:
۲-۳ عبارات و مجموعه های با قاعده مجموعه باقاعده: مجموعه ای با قاعده است که بتواند با استفاده از عملیات اجتماع. الحاق و هبو معط از مجموعه تهی. مجموعه شامل رشته تهی و اعضای مجموعه الفبا تولید شود. 

صفحه 33:
۲-۳ عبارات و مجموعه های با قاعده فرض کنید که ۶ يك الفبا باشد. مجموعه هاي باتاعده روى 2 به صورت بازكشتى زير تعريف مى شوند: ۱ ۰:۱ .0و (عابه ازاء هر 206 مجموعه هايى باقاعده روی 2 تند. (8 تام باز کت فرض کنید که او ۷ مجموعه هایی باقاعده روی 2 باشند. مجموعه ‎KY UY ole‏ و + مجموعه هایی باقاعده روی 2 هستند. ‎tt)‏ ۰۰..: ۷ یک مجموعه باقاعده روی 2 است اگر آن بتولند با تکرار متناهی از مرحله گام باز گشت از عناصر پایه ای بدست آید. ‎ ‎ 

صفحه 34:
۲-۳ عبارات و مجموعه های با قاعده مثال: مجموعه رشته هایی که با یک ۰ شروع شده و شامل حداقل یک ۲ هستند. مجموعه ای با قاعده روی (طره) است. 

صفحه 35:
۲-۳ عبارات و مجموعه های با قاعده عبارت با قاعده فرض كنيد كه 8 یک الفبا است. عبارات باقاعده روی 2 به صورت باز گشتی زیر تعریف می شوند: (۱ ۸۰:۱ .0 و (هابه ازاء هر 206 عباراتی باقاعده روی 2 هستند. (8 کام باز ۰-۳ فرض کنید که مره عباراتی باقاعده روی ۶ باشند.در این صورت عبارات ‎WW‏ ,معاو 1ك نیز عباراتی باقاعده روی 2 هستند. ‎tt)‏ ...7 :ی یک عبارت باقاعده روی ۶ است اگر آن بتواند با تکرار متناهی از مرحله گام بازگشت از عناصر پایه ای بدست آید. ‎ ‎ 

صفحه 36:
۲-۳ عبارات و مجموعه های با قاعده a <tbo*b(aub)) st (wUb)*ba*ba) sat (aUb)*b(aUb)*b(aub)) ‏یک عبارت با قاعده برای مجموعه رشته هایی که شامل زیر رشته‎ ‏نمی باشند.عبارت با قاعده ۳0( طح)*طلا*( )۳ .ممکن است‎ ۰ ‏شامل هیچ پیشوندی از طها نباشد. تمامی هه بایستی حداقل به یک‎ ‏طختم شده و یا عنصر پایانی رشته باشند.‎ 

صفحه 37:
فصل سوم. گرامرهای مستقل از متن لل سبل لوا ‎le eee‏ ۸ اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: " گرامرها و زبان های مستقل از متن 7 اشتقاق و درخت آن ۲ گرامرهای قاعده 

صفحه 38:
۳-۱ گرامرها و زبانهای مستقل از متن به یک رشته درست از لحاظ نحوی. یک جمله (عمصحی از ۱ زبان اطلاق می کنیم. عناصر الفبا به زبان موسومند. عناصر اضافی مورد استفاده در فرآیند تولید جملات جهت اجرای محدودیتهای نحوی زبان به متغیرها یا موسومند. نظریه زبانها و ماشینها |[ صفحه: 38 

صفحه 39:
۳-۱ گرامرها و زبانهای مستقل از متن گرامر مستقل از متن یک گرامر مستقل از متن. یک چهارتایی (2,)۳,9,)) است که درآن کیک مجموعه متناهی از متغیرهاء 2(الفبا/لیک مجموعه متناهی از عناصر پایانی:۳) یک مجموعه متناهی از قوانین و 5) یک عنصر مشخص از ۵) به نام عنصر ابتدایی است. S فرض می شود که ()و 2مجموعه هایی غیر الحاقی هستند 

صفحه 40:
۳-۱ گرامرها و زبانهای مستقل از متن قانون: یک قانون که به آن یک تولید نیز می گویند. عضوی از مجموعه (۵<))0۷02+است. قانون [س,)] معمولاً به صورتال۷ ‎A‏ ‏نوشته می شود. 

صفحه 41:
۲-۱ گرامرها و زبانهای مستقل از متن از آنجائیکه رشته تهی در(ل() )+ وجود دارد. لذا ( نیز ممکن است در سمت راست یک قانون قرار گیرد. قانونی به شکل2 <- به قانون تهی یا قانون لامبدا موسوم است. 

صفحه 42:
۳-۱ گرامرها و زبانهای مستقل از متن مرحله اصلى در فرايند تباید تبدیل یک رشته با استفاده از یک قانون است. ۰ بکار گیری قانون مب« -() برای متغیر 9)در 7 رشته مهما تولید می کند که آن را به صوریل۲۷ 12 ۲2 4قشان می دهیم. 

صفحه 43:
UY ‏گرامرها و زبانهای مستقل از متن‎ ۳-۱ یک رشته مب از مه قابل اشتقاق است اگر یک دنباله متناهی از قوانین كه بارا به مه تبدیل می کنند وجود داشته باشد. قابلیت اشتقاق ‎vil‏ را به صورت ‎vow‏ نشان می دهیم. 

صفحه 44:
UY ‏گرامرها و زبانهای مستقل از متن‎ ۳-۱ مجموعه رشته های قابل اشتقاق از , فرض کنید که (),۳, 0,2))<) یک گرامر مستقل از متن و ‎xO 6)0102(‏ باشد. مجموعه رشته های قابل اشتقاق از ب به صورت با زگشتی زیر تعریف می شود: ( با ,»مه از مه قابل اشتقاق است. ( ام از .گر اکن از با قابل اشتقاق بوده و 6۳ 6 باشد. آنگاه بپرمهد از مه قابل اشتقاق خواهد بود. ‎tt)‏ ...۰ تمامی رشته های ایجاد شده از مه با بکار گیری تعداد ‏متناهی گام باز گشت از م قابل اشتقاقند. ‎ 

صفحه 45:
۳-۱ گرامرها و زبانهای مستقل از متن نکته: یک گرامر شامل یک الفبا یک روش تولید رشته ها است. اين رشته ها ممکن است شامل متغیرها و عناصر پایانی باشند. 

صفحه 46:
۳-۱ گرامرها و زبانهای مستقل از متن فرض کنید که (),, 60,2)<) یک گرامر مستقل از متن باشد. فرم جمله اى:يى رشته (6)0108 بيه يى فرم جمله اى از 8©) است اكر يك اشتقاق رربجك 8) وجود داشته باشد. .یک رشته #26 یک جمله از 8) است اگر یک اشتقاق*: ‎wer‏ ‏۶ در) وجود داشته باشد. ‎ob)‏ <): که آثرا با (2))رانشان م, دهند.محموعه زد ات ‎ ‏7 بو[ رعس ‎ ‎ 

صفحه 47:
۳-۱ گرامرها و زبانهای مستقل از متن فرم جمله اي «اء رشته هایی قابل اشتقاق ازعنصرابتدایی گرامرهستند . سا رم جمله ایهایی هستند که تنها شامل عناصر پایانی می باشند. به مجموعه ای از رشته ها روی یک مجموعه الفبا( 2) زبان مستئل از متن كفته می شود. 

صفحه 48:
۳-۱ گرامرها و زبانهای مستقل از متن یک قانون 0) به شکل 14 4 را باز کشت سیم می نامیم. به یک اشتقاق 4۲ مت ۲۷ بفکه 6۵ در رب نیست. باز گشت غیر مستقیم می گوییم. 

صفحه 49:
۳-۱ گرامرها و زبانهای مستقل از متن ۰.۰ گرامر 68 که یک زبان شامل رشته هایی با تعداد مثبت و زوجی از "ها را تولید می کند. (62)0,2,,۵) ‎O={6,0}‏ ‎{ab} =>‏ 65-0 :6 ۰.۰ ©) يوحت 

صفحه 50:
۳-۱ گرامرها و زبانهای مستقل از متن اشتقاق راست و چپ ات هر قانونی که به اشتقاق اولین متغیر سمت چپ رشته می پردازد. ‎a ۲‏ شته را انتناق ‎ays)‏ قوانینی که راست ترین متغیر موجود در هر رشته را تبدیل می کنند. ‎ 

صفحه 51:
۳-۱ گرامرها و زبانهای مستقل از متن ۱ درخت اشتقاق فرض کنید که (9),(), ,92)6)یک گرامر مستقل از متن بوده و9) w = یک اشتقاق باشد.درخت اشتقاق مه * 8) یک درخت مرتب شده است که به صورت زیر ساخته می شود: 

صفحه 52:
۳-۱ گرامرها و زبانهای مستقل از متن درخت اشتقاق ‎ain, b LOT)‏ 2)مقداردهی کنید. (باگر ‏ بد...جدینبد یا ۰ ۰ (۲۱/۵2۵) قاونی در اشتقاق بکار رفته برای رشته ,2 باشد. آنگاه 26۰۰6 بل عنوان فرزندان © به درخت اضافه کنید. ‎Sty)‏ 2 <-4قانونی در اشتقاق بکار رغته برای رشته 9 باشد. آنگاه را به عنوان تنها فرزند) به درخت اضافه کنید. ‎ ‎ 

صفحه 53:
۳-۱ گرامرها و زبانهای مستقل از متن => 3 oe ares => wo 6 ‏م جم‎ 2 ۳ ۵ = 1 ‏حم‎ 00 LOCO, a = 2 ‏موی سل‎ oo = 1 a> a ‏درط‎ 00 ‎ab‏ مس ‎dt00- 5‏ >= ,0 بط ‎aye‏ ‎wt‏ ‎dd ae 3‏ > ‎۱ ‎1 ‏د‎ oe abby ® Dis ap) See 3 4k » abbas ‎ 

صفحه 54:
۳-۱ گرامرها و زبانهای مستقل از متن فرض کنید که ) یک گرامر مستقل از متن بوده وررست یب یک اشتقاق در ‎B‏ باشد که «) می تواند ‎V> WAWA...WAWi 2 jqu0 dy‏ با مها نوشته شود.در این صورت رشته های (#۳6)2106ای وجود دارند که در شرایط زیر صدق می کنند: A> PB?) V> WRAWDP WP War k 2 =n ») ۳ 

صفحه 55:
مثالهایی‌از گرلمرها و زبان‌ها9-60 فرض کنید که 0 گرامری با قوانین زیر باشد: ‎G— ۰‏ ه 1 هك ات دراين صورت (0< > , 0< »٠ك‏ ”ا 3)-(8)را خواهد بود. 

صفحه 56:
مثالهایی‌از گرلمرها و زبانها3-2 ‎Obs‏ گرام ‎bod a20 , w>O}‏ ها ‎ae‏ 2 یک رشته بم متقارن است اگر لک باشد. زبان كرامر مجموعه متقارن روی (طاره) ‎ul bGb‏ و 

صفحه 57:
مثالهایی‌از گرلمرها و زبانها3-2 سس سس سس ‎G+ WbiwGbbia iwht OsuSwSCu}‏ :@ — گر امر ‎cb) (b})‏ ) ۵۳۰ ,۱۱0۸۵۰ 2۵ 98 6 طاهط ه 

صفحه 58:
۳-۳ گرامرهای باقاعده كرامر باتاعده: یک گرامر مستقل از متن است که هر قانون آن دارای یکی از حالات زیر است: 1—® a) —r AQ) ‏مهو‎ WD) که در آن 0 6 ,9) و 206 می باشد. یک زبان با قاعده است اگر بتواند توسط یک گرامر با قاعده تولید شود. 

صفحه 59:
۳-۳ گرامرهای باقاعده مثال: | قاعده ‎pol‏ با قاعده ۰980 ب :66 ۷۱3 5 ‎Out‏ 3 بيه © بت 

صفحه 60:
۳-۴مروری بر گرامرها و زبان ها زیان گرامر ‎Dae Peo}‏ 0- 6:6 ۰ 6 > ‎bbb‏ 6 قانون به کار رفته اشتقاق 9-0 0 ام جه ‎G— Gee‏ ۲ " وهی ‎Ou‏ ؟ " ريه ‎(bbb) (a3) 5 O— bb‏ Or Ow ube 

صفحه 61:
۲-۴مروری پر گرامرها و زبان ها للا بان كباس 6ط 6-5 ‎aL (©)=0"(o"bo'ba*)‏ ۵ ۱۵ هس ‎0-٠-2‏ ‎obs‏ گرامر (0< م22 5 8{ ‎owe‏ 

صفحه 62:
| فصل چهارم: مقدمه ای بر پارسر ها 1 حمل تاعارم ‎nee‏ 1۳ اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: اشتقاق جب و ابهام " گراف یک گرامر ‎push ©‏ ها 

صفحه 63:
۴-۱ اشتقاقهای چپ و ابهام انتتان در یک گرامر مستقل از متن مکانیزمی برای تولید رشته های زبان گرامر ایجاد می کند. الگوریتم تجزیه؛ یک سوال مهم اینست که چگونه می توان تعیین کرد که آیا دنباله ای از کد یک زبان از قواعد نحوی گرامر آن زبان تبعیت می کند یا خیر؟ یک رشته از لحاظ نحوی درست است اگر آن بتولند با استفاده از قوانین گرامر. از عنصر ابتدائی مشتق شود. الگوریتم ها بایستی برای تولید اشتقاق رشته ها در زبان یک گرامر طراحی شوند. 

صفحه 64:
۴-۱ اشتقاقهای چپ و ابهام زبان یک گرامر: مجموعه ای از رشته های پایانی است که می توانند به هر روشی از عنصر ابتدائی مشتق شوند. قضیه: فرض کنید(92)00,۶,۳,0) یک گرامر مستقل از متن باشد. یک رشته ممادر (()) با است اگر و تنها اگر یک اشتقاق چپ سمااز 2) وجود داشته باشد. 

صفحه 65:
۴-۱ اشتقاقهای چپ و ابهام یک گرامر مستقل از متن 2) مبهم (صسجطاجه) است. اگر یک رشته (0)را مم وجود داشته باشد بطوریکه با دو اشتقاق چپ مجزا تولید شود. مثال كرامر 61 ‎١‏ هد هق ينم ۶ یکگرلمر مبهملسزیرا يشته مه دارلی‌دو لشتقاق‌چمجزا لست ‎=—>G Gu‏ 6 6 جح 

صفحه 66:
۴-۱ اشتقاقهای چپ و ابهام ابهام از ویژگیهای گرامر است . نه از ویژگیهای زبان. مثال: گرامر ۱۵9۱۰ 9۵ ‎G‏ :@ زبان طه*ط 0+ است.اشتقاقهای چپ زیر ابهام 8) را نشان می دهند. << 86 ۵ = G ۰ => bGb => bGb => bub => bub 

صفحه 67:
۴-۱ اشتقاقهای چپ و ابهام یک گرامر غیر مبهم است اگر در هر مرحله از یک اشتقاق چپ تنها یک قانون وجود داشته باشد که ما را به اشتقاق یک رشته کامل هدایت کند. ‎G Ghee! ۸‏ هعد ‎w@bb | ubb‏ 

صفحه 68:
۴-۲ گراف یک گرامر اشتقاقهای چپ یک گرامر مستقل از متن 2) می تواند به وسیله یک گراف جهت دار (۰60( ,۰:۱ -.. تراسر ()نشان داده شود. گره های گراف , فرم جمله ای های چپ گرامر هستند. یک ‎ol ae‏ رشته ای است که می تواند بوسیله یک اشتقاق چپ از عنصر ابتدایی نتیجه شود. 

صفحه 69:
۴-۲ گراف یک گرامر فرض كنيد که (),), 6,2)<)یک گرامر مستقل از متن باشد. گرا ‎G(B) 5 oe‏ 1 گراف جهت دار(),۳),()) است که گره ها و کمانهای آن به صورت زیر تعریف می شوند: * #۴ N={we(vu J’) |s—> wh a 1O={Pwr]eOx@aP byw by wpplodtiow oP re r}) 

صفحه 70:
۴-۲ گراف یک گرامر گرامر مستقل از متن دارای تعداد محدودی قانون می باشد. لذا هر گره نیز دارای تعداد محدودی فرزند خواهد بود. به گرافی با اين ویژگی. گراف متناهی محلی گوییم. 

صفحه 71:
۴-۲ گراف یک گرامر دو استراتژی مختلف برای پیدا کردن یک اشتقاق عمااز 2 وجود دارد: ‎-١‏ يارسر بالا به يا رب ادامه می ‎wh‏ ‏ن: جستجواز گره 8) شروع شده و تا یافتن رشته ‎ ‏۲- پارسر پائین به بالااشروع جستجو با رشته پایانی سم و ادامه آن تا یافتن عنصر ابتدایی است. ‎ 

صفحه 72:
WY ‏الگوریتم های تجزیه‎ الگوریتم های تجزیه: 6 ۱- الگوریتم تجزیه بالا به پایین سطحی ۲- الگوریتم تجزیه بالا به پایین عمقی ۳- الگوریتم تجزیه پایین به بالای سطحی ۴- الگوریتم تجزیه پایین به بالای عمقی 

صفحه 73:
UY ‏پارسر بالا به پایین سطحی‎ ۴-۳ ‏یک پارسر تعیین می کند که آیا یک رشته ورودی از قوانین گرامر‎ ‏قابل اشتقاق است یا خیر.‎ پارسر بالا به پایین: اشتقاقهایی را با استفاده از قوانین روی متغیرهای چپ یک فرم جمله ای ایجاد می کند. 

صفحه 74:
۴-۳ پارسر بالا به پایین سطحی مسیرهایی که با 5) در گراف یک گرامر شروع می شوند بیانگر اشتقاق چپ گرامر هستند. کمانهای خارج شده از یک گره قوانین قابل استفاده برای تجزیه گره را مشخص می کنند. 

صفحه 75:
۴-۳ پارسر بالا به پایین عمقی امکان انتخاب نادرست یک آینده دو مشکل در پارسرهای عمقی ایجاد می کند ۱- اول اینکه الگوریتم بایستی بتواند یک انتخاب نادرست را تشخیص بدهد. ۲- دوم اینکه پارسر پس از تشخیص یک انتخاب نادرست به عقب بر گشته و اشتقاق دیگری را تولید نماید. 

صفحه 76:
۴-۳ پارسر بالا به پایین عمقی یک اشتقاق از (طاجوا) آمر: كرامر }6,0,7{ ‎O=‏ :@@ - (ط+() به وم عد لام © مس مب و بب وا 2 مه () 2 

صفحه 77:
۴-۳ پارسر بالا به پایین عمقی اشتقاق پشته [6,4] [©,8] ‎ITS]‏ ‏(,۳] ‎[VY @+)]‏ [رب/,۴] زرسی),۴] 

صفحه 78:
WY ‏تجزیه پایین به بالا‎ ۴-۵ هنگامی که ساختار جستجو با رشته ۲) آغاز می شود. الگوریتم حاصل یک پارسر پایین به بالا خواهد بود. مثال: قانون كاهث ‎bP) Tb‏ ‎ce.‏ )@® ‎Db 1D—(0)‏ ‎On or‏ ‎Orr Tb‏ ‎oor‏ © ومى و 

صفحه 79:
۴-۶ پارسر پایین به بالای عمقی يارسر يايين به بالا مى تولند به روش عمقی نیز به کار رود. کاهش ها با استفاده از عمل شیفت و روش مقایسه تشریح شده برای الگوریتم سطحی تولید مى شوند. ترتیب پردازش کاهش ها با ترتیب قوانین و تعداد شيفتهاى مورد نياز براى انجام انطباق مشخص می شود. 

صفحه 80:
فصل بنجم: فرم های نرمال اهداف رفتارى: دانشجو يس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: ‎cla pd”‏ نرمال ‏"" حذف قوانین لامبدا ‏* حذف قوانین زنجیره ای ""فرم نرمال شومسکی وگریباش ‎ 

صفحه 81:
فصل پنجم: فرمهای نرمال یک قرم نرمال با اعمال محدودیتهلیی روی شکل قوانین موجود در گرامر تعریف می شود. گرامرها در یک فرم نرمال. مجموعه کاملی از زبانهای مستقل از متن را تولید می كنند. فرم های نرمال برای گرامرهای مستقل از متن: ۱- فرم های نرمال شومسکی ۷- فرم های نرمال گریباش گروه کامپیوتر || _نظریه زبانها و ماشینها ۰ _صفحه: 81 

صفحه 82:
۵-۱ حذف قوانین لامبداء فرض کنید که (,), 9<)60,2) یک گرامر مستقل از متن باشد.یک گرامر (۳,)۵), 2"2))",2) وجود دارد به طوریکه t L()=(@)) ‎gaily’ tt)‏ 0" به شکل ما ۰ 27) می باشند که 0 و (۵468[(۷2)) 6 ببه: است. 

صفحه 83:
۵-۱ حذف قوانین لامبداء ۰ عنصر ابتدایی گرامر 6 باز گشتی است. 6:65 ‏6مس‎ ١ 66 ١60 ‘SG G ۵ ‏۱ب‎ 6 ۱ ۵ cal Ze, C wel a 6 BIL CoC wet 3 

صفحه 84:
WY ‏حذف قوانین لامبداء‎ ۵-۱ به متغیری که بتواند رشته تهی را مشتق کند. میرا (عاطاهلج) گفته می شود. یک گرامر بدون متغیرهای لامبداء به گرامر غیر انقباضی زا مت موسوم است. گروه کامپیوتر نظریه زبانها و ماشینها عن 324 

صفحه 85:
۵-۱ حذف قوانین لامبداء فرض كنيد که (2)00,۶,)۳,)9) یک گرامر مستقل از متن باشد. الگوریتم زیر مجموعه ای از متغیرهای میرای) را تولید می کند. الگوریتم ورودی: یک گرامر مستقل از متن (,,92)60,2) ‎OO := {O10 2).‏ ‎reped‏ ۳860 :۶ 00 ۱ Por ewh vor )© ‏ع‎ 0 ۲ ‘Phere wi ® nike 9 wood w EPREO" tea WOLD : = DOW ufo} cl DOLL = PREO 

صفحه 86:
۵-۱ حذف قوانین لامبداء نکته: یک گرامر با قوانین لامبداء غیر انقباضی نیست. 

صفحه 87:
۵-۱ حذف قوانین لامبداء فرض کنید که (92))0,2,۳,)۵) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن (:,.), 92)60.,2) وجود دارد بطوريكه 1L@.)=L(6)) ‏یک متغیر بازگشتی نیست.‎ 1G.) ‏در ,۲) وجود دارد اگر و فقط اگر (),6 22,3) باشد.‎ - )2( 

صفحه 88:
۵-۲ حذف قوانین زنجیره ای بکار گیری یک ‎By gi‏ 4۸7 تنها طول رشته مشتق شده را افزلیش نمی دهد. بلکه عناصر پایلنی اضافی نیز تولید می کند. در واقع. این قانون یک متغیر رامجدداً نامگذاری می کند. قوانینی به این شکل به قوانین زنجیره ای موسومند. 

صفحه 89:
۵-۲ حذف قوانین زنجیره ای قوانین زیر را در نظر بگیرید: 0اه اط ها سه قانون زنجيره اى 2 سم مشخص مى كند كه هر رشته قابل اشتقاق از 629 از) نیز قابل اشتقاق است. بکار گیری یک قانون زنجیره ای. یک مرحلهاضافی است که می تولند با افزودن قوانین ۶) حذف شود. قانون زنجیره ای 2 <-را می توان با سه قانون ()به صورت زیر جایگزین نمود: 0ص 9 + 

صفحه 90:
۵-۲ حذف قوانین زنجیره ای پیش فضیه فرض کنید که #) یک گرامر مستقل از متن غیر انقباضی حقیقی است. الگوریتم زیر مجموعه متغیرهای قابل اشتقاق از 0 را تنها با استفاده از قوانین زنجیره ای تولید مى کند. 

صفحه 91:
۵-۲ حذف قوانین زنجیره ای ایجاد مجموعه ‎OWOSW()‏ ‏ورودى: يك كرامر مستقل از متن غير انقباضى حقيقى (0,7:,0:,8)-©) ‎CLO) : - )©( .0‏ ©. مه د : ۰80۵0 ©. سب ‎O€O : = OLOW(G)PREO 0‏ ‎REO : = OLO1O(C) 0.8‏ Por pack verkbe BEOBO te 0.9 ‏لط © طح عاسم ل‎ CLOW) : - ‏(مب(0)ه هون‎ sd OL.B10(6) = PREO 

صفحه 92:
۵-۲ حذف قوانین زنجیره ای قصيه فرض کنید که (۳,8), 2)60,2) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن 20) وجود دارد بطوریکه 1L(® 0)=L(@)) ‏هیچ قانون زنجیره ای نداشته باشد.‎ 8 )00( 

صفحه 93:
WY ‏عناصر غیر مفید‎ ۵-۳ عناصر مفید و عناصر غیر مفید فرض کنید 8 یک گرامر مستقل از متن است. در اين صورت یک عنصر ()) « مفید(لاصص) است اگر یک اشتقاق مه *حپهوی ‎s‏ ‏وجود داشته باشد بطوری 45 ‎Div 9 tuvE(OUD)‏ &% باشد. به عنصری که مفید نیست. غیر مفید(ححعاوص گفته می شود. 

صفحه 94:
۵-۳ عناصر غیر مقید یک عنصر پایلنی مفید است اگر در یک رشته از زبان ظ) رخ دهد. یک متغیر مفید است اگر در یک اشتقاق که با یک عنصر ابتدائی شروع شده و یک رشته پایانی را تولید می کند. رخ دهد. باشد ط باد ای یک متغیر مفید برقر خ دهد پا به عبارتی در به متغیری که در یک فرم جمله ای رخ می دهد.قابل دسترس ‎(reachable)‏ 51 2) گفته می شود. 

صفحه 95:
۵-۳ عناصر غیر مقید قضیه فرض کنید که (),۳), 9<)6,2) یک گرامر مستقل از متن است. الگوریتمی برای ایجاد یک گرامر مستقل از متن (9(2)6(,2:۳,)۳,۵) وجود دارد بطوریکه 1L(G »)=L(6)) (9 هر متغیر در )یک رشته پایانی در )را مشتق کند. 

صفحه 96:
۵-۳ عناصر غیر مفید مثال ‎Or = {6,0,0,6,F}‏ 6:8 ® lw ‏3م‎ © Clb ‏مق درم‎ 0 9 ۱0 © Di وا © 8.۰0 © مومبم © موه هو © ‏ع طاهط‎ Let 

صفحه 97:
۵-۳ عناصر غير مفيد بيش أقغ فرض كنيد كه (6>)0,92,8,08) يى كرامر مستقل از متن است. الكوريتم زير مجموعه اى كامل از متغيرهاى قابل دسترس از © را توليد مى كند. 

صفحه 98:
۵-۳ عناصر غیر مقید یجاد متغیرهای قابل دسترسر 52909 یک گرامر مستقل از متن (2)0,2,,6 ۳880 :2 0 ۲ Por ewk vortble PEDEO wh V1 Por each nie ® Oth ahd od bes rw te REGCOW snl REGO'W = PREO 

صفحه 99:
۵-۳ عناصر غير مفيد ‎aad‏ فرض کنید که (۴,2), 9<)),2) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن 60 وجود دارد بطوریکه 1L(@ 0) =L(@)) (0) 8 هیچ عنصر غیر مفیدی ندارد. 

صفحه 100:
۵-۳ عناصر غیر مقید مثال گرامر زیر را در نظر بگیرید. ۵:۵0 تاو لزوم بکار گیری تبدیلات به یک ترتیب معین با بکارگیری فرآیندهای هر دو ترتیب و مقایسه نتایج آنها مشخص می شود. 

صفحه 101:
WY ‏عناصر غیر مفید‎ ۵-۳ ۱- حذف عناصر غیر قابل دسترس: ۱-حذف متغیرهایی که رشته پایانی را ‎Gu 0D‏ تولید نمی کنند: ‎Gu 6‏ ۲ 86 = ۲-حذف متفیرهایی که رشته پایانی ۲- حذف عناصر غیر قابل دسترس: را تولید نمی کنند: نوت نوت Ob wad Sade pt DB ‏متغیر 8) و عنصر پایانی‎ 

صفحه 102:
۵-۴ فرم نرمال شومسکی فرم نرمال شومسکی یک گرامر مستقل از متن (۳,)9), 0<)6(,2)در فرم نرمال شومسکی است اگر هر قانون دارای یکی از حالتهای زیر باشد: ۱6+ )00( 0 ©و — 46) «cl B,CCO-{G} a5 ل ‎set oS‏ ماننا. ]رفح 22 ] 

صفحه 103:
۵-۴ فرم نرمال شومسکی درخت اشتقاق در یک گرامر به فرم شومسکی یک درخت دودویی است. as فرض کنید که (,), 2,())<) یک گرامر مستقل از متن باشد. الگوریتمی وجود دارد که یک گرامر (۳,۵), 2<)0,2) در فرم نرمال شومسکی و معادل با 08 ايجاد کند. نظریه زبانها و ماشینها 

صفحه 104:
۵-۴ فرم نرمال شومسکی WY مثال 04 0 ع مه بو 64 4 T Te © Te o oO 6: 8- 166۵۱۰ © ‏واه‎ ‎© ‏داهم‎ ‎C Ale 

صفحه 105:
۵-۴ فرم نرمال شومسکی مثال باط © ٠ه‏ 6 موز اطع راط حم ۲ بیانگر+لست نوی ۶ بسیانگر 0) لست ‎+P‏ ‏باب یانگر( لست > © بيانكر) لست ‎CR‏ © بيانكر+ لست (©) اط ‎G+ G+‏ (©) اط كبن حو 1 (©) اطاحم 

صفحه 106:
۵-۵ حذف باز گشت چپ مستقیم قانون باز گشت چپ مستقیم ‎BHM‏ ) در گرامر 90) محاسبات پایان ناپذیری را در هر الگوریتم سطحی و عمقی امکانپذیر می سازد. 

صفحه 107:
UY ‏حذف باز گشت چپ مستقیم‎ ۵-۵ مثال 0 ای سس 6-۱۷ ‎Twila‏ ‎Ov tA ibic ۳‏ سس را ‎@—Oul Obi bic‏ 

صفحه 108:
۵-۵ حذف باز گشت چپ مستقیم فرض كنيد که (2)60,2,)۳,۵<) یک گرامر مستقل از متن ‎Sa DEO 5 025‏ متفیر باز گشتی چپ مستقیم در ظ) باشد. الگوریتمی وجود دارد که یک گرامر معادل ,۳ 0,2)<) ایجاد نماید بطوریکه 0 یک متغیر باز گشتی چپ مستقیم نباشد. گروه کامپیوتر | نظریه زبانها و ماشینها صفحه: 108 

صفحه 109:
۵-۶ فرم نرمال گریباش ایجاد پیشوندهای پایلنی كشف بن بست ها را توسط الگوریتم های تجزيه بالا به يايين تسهيل می کند. یک فرم نرمال ( نظیر فرم گریباش) طوری ارلته می شود که بکارگیری هر قانون بتواند طول پیشهند پایلنی رشته مشتق شده را افزليش دهد که لین امر ما را از وجود بازگشت چپ. چه مستقیم و جه غير مستقيم؛ مطمئن می سازد. 

صفحه 110:
۵-۶ فرم نرمال گریباش فرم نرمال گریباش یک گرامر مستقل از متن (۳,)9), 0,۶))<)در فرم نرمال گریباش است اگر هر قانون دارای یکی از حالتهای زیر باشد: —hiG) ۲ 0 #B we...) cul FOS,....1 «BEO{G} ‏و برای هر‎ Dueas 

صفحه 111:
WY ‏فرم نرمال گریباش‎ ۵-۶ موی ذا ۵ حي مثال: ۷ ۱ ۳ 1 9 ۱۵۱۵۱۰ 9۵۱۲ ‏مق يي‎ DIT IT | ‏:1ك‎ | 1١ ١ ‏ئها‎ ١ ‏تاساك‎ 009 ١ ‏جه‎ ١ © ١١ ‏نهديو ع2‎ 9 Ob Ib میم Ora سم TOLL Ila 

صفحه 112:
۵-۶ فرم نرمال گریباش مثال: اشتقاق چپ رشته ماه فرم نرمال كريباش فرم نرمال ش فرم نرمال کریباش فرم نرمال شومسکی 09 لوب ‎=6TO‏ ‏09 لوب << 0ج 70۳0 

صفحه 113:
فصل ششم: آتاماتاى متناهى لس ‎Wo Oe‏ اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: ۲ آتاماتای قطعی * دیاگرام حالت "آتاماتای غیر قطعی 

صفحه 114:
فصل ششم : آتاماتای متناهی به یک روال موثر برای تعیین اينکه آیا یک رشته ورودی متعلق به یک زبان است يا خیر یک بذبرنده زبان گفته می شود. ویژگی عمومی همه ماشینها پردازش ورودی و تولید خروجی است. گروه کامپیوتر نظریه زبانها و ماشینها مع 114 

صفحه 115:
۶-۲ آتاماتای متناهی قطعی() 6 11010000000 

صفحه 116:
۶-۲ آتاماتای متناهی قطعی(0»۷ ۵۵/) حالات یک 00208 بيانكر وضعيت داخلی ماشین هستند. ورودی. یک دنباله متناهی از الفبای 2 است. یک محاسبه آتاماتا شامل اجرای مجموعه ای از دستورالعملها است. اجرای یک دستورالعمل حالت ماشین را تغییر می دهد. هدف از محاسبه یک آتاماتا تعیین قابلیت پذیرش یک رشته ورودی است. [ey eee sets ‏ل‎ 

صفحه 117:
WY (Prote-Orte ‏آتاماتای متناهی قطعی(عداده0)‎ ۶-۲ فرض ‎wus‏ که (,,8, 2<)0,۶) یک 00*69 باشد. زبان ۸0 که با (0))ما نشان داده می شود. مجموعه ای از رشته ها در *.2 است که توسط ) پذیرفته می شود. گروه کامپیوتر نظریه زبانها و ماشینها ۶۷۳ 

صفحه 118:
۶-۲ آتاماتای متناهی قطعی(سداه) سس مثال ) ©0000 ی کمجموعه از يشته هایی‌را ریی(,۳) مىيذيرد كه شامززير يشته حاط هستند بد ينصورتكه ‎cul #(D)=(aub)*bb(aub)‏ ‎O: G={p,q-7}‏ ‎{ab} =>‏ ‎=f}‏ 

صفحه 119:
۶-۲ آتاماتای متناهی قطعی(2) ۳ تلبع گذر در یک جدول به نام جدول گذر داده شده است.حالات به صورت عمودی و الفبا به صورت افقی در جدول قرار گرفته اند. عملکرد آتاملتا در حللت + با ورودی .با یافتن نقطه مشتر ک سطر متناظر ب و ستون متناظر » تعیین می شود. b 8 44 4/4 444 ww ww 9 

صفحه 120:
۶-۲ آتاماتای متناهی قطعی(2) ۳ ۳ تابع گذر توسعه يافته و از یک 000 با تابع گذر 2 تابعی است از 9< به © كه به صورت باز گشتی زیر روی طول رشته ورودی تعریف می شود: ( پایه: (0-(س بط . در اين صورت ‏ ريت و ۵(و, )چه اسث. 0 ت(س)كابحط . در اين صورت ,ی بک(برای برخی 26) و cul (qa) 0 -) ۵ (8 مرحله بازگشت: فرض کنید 6<(ر) بط باشد.آنگاممی‌عرب و 2 (2(بر,و),ه) (س,و)- 0 خواهد بود. ل كرد كس إلى سيد ‎[Pee ets‏ 

صفحه 121:
WY ‏دیاگرامهای حالت و مثالها‎ ۶-۳ دياكرام حالت يى 707( یک گراف جهت دار بر چسب شده است که گره های آن مبین حالات ماشین بوده و کمانهایش از تابع گذر بدست آمده است. مثال: 

صفحه 122:
۶-۳ دیاگرامهای حالت دياكرام حالت يى ©0020 (2,90,0, 2, )007 يى كراف بر چسب ‎LB jlo‏ شرايط زير است: (؛ كره هاى 8) عناصر ) هستند. (# برجسب كمانهاى 8) عناصر 5[ هستند. (۷0 8 كره ابتدايى با فرم نمايشى ()كاست. (8) م مجموعه كره هاى بذيرش است كه هركره يذيرش با 2)مشخص مى شود. (م يك كمان از كره وبهو با برجسب ه وجود دارد اكر 8(كري) -ز]© باشد. ‎ly vt)‏ هر گره‌چوعنصر 620دقيقاً یکی کمان با برچسب ه از چ خارج مى شود. ‎ ‎ 

صفحه 123:
۶-۳ دیاگرامهای حالت و مثالها محاسبه ‎drab 52979 b DPB‏ و مسير متناظر آن در دياكرام به صورت یز انستا: ‎pa‏ محاسیف- | ,دب ‎feo bbb]‏ ‎F fect]‏ ‎F fa, bb]‏ ‎Fim]‏ ‎Fi‏ ‎444444 ‏رشته ءاطاه‌قابل پذیرش است زیرا در حالت پایانی مبمتوقف شده است. ‎ ‎ 

صفحه 124:
ت و مثالها ۶-۲ دیاگرامهای حالت و مثال شته ير رشته حاط نمى باشند 1 ) هایی روی اره! که شامل ز یی 7 

صفحه 125:
۶-۳ دیاگرامهای حالت و مثالها مثال 0 06۳69) زبانی‌شامليشته ها ریی(۳,) با تعداد زوجیتو تعداد فردیت را می‌بذیرد. 

صفحه 126:
۶-۳ دیاگرامهای حالت و مثالها دیاگرام حالت زیر ©0008 غير كاملى را تعريف مى كند كه عبارت (طله)© را مى يذيرد. 

صفحه 127:
۶-۴ آتاماتای متناهی غیر قطعی يى آتاماتاى متناهى غير ای یک پنچ تایی (,2)6,2,2,۷۳) است که در آن 0 یک مجموعه متناهی از حالات. 2 یک مجموعه متناهی موسوم به النباء663ه۹ مبین حللت ابتدایی.۳) زیرمجموعه ای از 3 شامل حالات نهلیی یا حالات پذیرش, و8 یک تلبع جامع از 2*0 به (۳)6۵) می باشد. 

صفحه 128:
WY ‏آتاماتای متناهی غیر قطعی‎ ۶-۴ زبان ‎OD‏ 20*9) که با (0)),ا نشان داده می شود. مجموعه ای از رشته های پذیرفته شده به وسیله 0) است. بدین صورت که L(O)= {uw there ts 0 cowutativs [gow] *[q, Hutage®?} 

صفحه 129:
۶-۴ آتاماتای متناهی غیر قطعی دیاگرام حالت یک *) (,0,۷, 2)0,2() یک گراف جهت دار 8 با شرایط زیر است: )1 گره های ۶) عناصر © هستند. ‎tt)‏ برچسب کمانهای ) عناصر 2 هستند. ‎qo)‏ #ا گره ابتدایی است. ‏( به مجموعه گره های پذیش است. ‏(ب یک کمان از گره ب به و با برچسب » وجود دارداگر 0(3,)-0 باشد. ‎ ‎ 

صفحه 130:
WY ‏آتاماتای متناهی غیر قطعی‎ ۶-۴ ‏مثال‎ دیاگرامهای حالت 20و 29) آتاماتای متناهی را تعریف می کنند که (طناه):(طنا3) ططعه را می پذيرند. ab <0@—+-@+-© 

صفحه 131:
۶-۴ آتاماتای متناهی غیر قطعی 

صفحه 132:
۶-۵ گذرهای لامبدا یک آتاماتای متناهی غیر قطعی با گذرهلی لامبدا یک پنچ تایی (),0,0, 22)6,2) مشلبه (06۳6) است با لین تفاوت که 0 تابعی از( )0۵*620 به (۳)0) می باشد. 

صفحه 133:
UY ‏گذرهای لامبدا‎ ۶-۵ مثال: می خواهیم از گذرهای لامبدا برای ایجاد یک 006۳03- که رشته هایی به طول زوج را بروى ‎ub)‏ می پذیرد. استفاده کنیم. بتدا دیاگرام حللت را برای ماشینی که رشته های به طول دو را می پذیرد تشکیل می دهیم. <@—“*—_@——_@ 

صفحه 134:
۶-۵ گذرهای لامبدا برای پذیرش رشته تهی . یک کمان لامبدا از «به هچ اضافه می شود. رشته هایی به طول زوج مثبت با استفاده از کمان لامبدای‌م به هچ برای تکرار دنباله مبرمپرص پذیرفته می شوند. a <Q=—O=—@ 

صفحه 135:
۶-۶ حذف غیر قطعیت همبستگی لامبدای یک حالت + که با -(ج)عمعحوم نشان داده می شود. به صورت باز گشتی زیر تعریف می شود. 6 9 Acbswe(y)- 4b 1) (8 مرحله بازكشت: فرض كنيد كه و يى عنصر از - (ج)سعحطهد باشد.ا گر ( ,)6ج باشد. آنگاه = (و)عسمحطه( ب 6 است. ‎il)‏ همبستكى: و در -(و)عحاه3 است اگر بتواند با یک تکرار متناهی ‏ازمرحله باز گشت بدست آید. ‎ ‎ 

صفحه 136:
WY ‏حذف غیر قطعیت‎ ۶-۶ مثال جدولهای گذر برای تابع گذر8 و تابع گذر ورودی !یک 00*603)- به همراه دیاگرام 0 ارائه شده است. زبان "۳ (:: می باشد. 

صفحه 137:
{x} {ea} -]ة 52 55] 

صفحه 138:
۶-۶ حذف غير قطعيت WY مثال ماشینهای 00)و9() به ترتیب ()«و: را می پذیرند. 049 > هوم > 

صفحه 139:
۶-۶ حذف غیر قطعیت با ایجاد یک حالت ابتدایی جدید و اتصال آن به حالات ابتدایی ماشینهای اصلی با استفاده از گذر لامبدا می توانیم یک 0 063 بسازیم که هلا*(م)ه: را بپذیرد. 

صفحه 140:
۶-۶ حذف غیر قطعیت WY تابع گذر ورودی 0 به صورت زیر است: 

صفحه 141:
WY فصل هفتم : زبانها و مجموعه های با قاعده اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: ۳ آتاماتای متناهی و مجموعه های با قاعده © گراف عبارت آزبان بی قاعده 

صفحه 142:
گرامرها به عنوان تولید کننده های زبان, و آتاماتای متناهی به عنوان پذیرنده های زبان معرفی شده اند. فصل هفتم ۰ زبانها و مجموعه های با قاعده هر آتاماتای متناهی با الفبای 2 یک زبان روی 2 را می پذیرد. خانواده زبانهای پذیرفته شده توسط آتاماتا دقیقاً شامل مجموعه های باقاعده روی 2 است. ۱ | صفحه: 142 نظریه زبانها و ماشینها 

صفحه 143:
WY ‏آتاماتای متناهی و مجموعه های با قاعده‎ ۷-۱ مجموعه های با قاعده با استفاده از عملیات اجتماع» الحاق و عملگر ستاره(20۳ محطل) از عناصر پایه ای آیجاد می شوند. 

صفحه 144:
۷-۱ آتاماتای متناهی و مجموعه های با قاعده فرض كنيد کهو3),,) ری ‎GG‏ * به ترتیب حالات ابتدایی و پایانی 0 باشند.حالات ابتدايى و يايانى ماشين را با 0و0 نشان مى دهيم. زبان (009)رالا(0(0)را توسط ماشين زير يزيرفته مى شود: 

صفحه 145:
۷-۷ گراف عبارات ‎OLS‏ را :یک گراف جهت دار است که برچسب کمانهای آن عبارات با قاعده می باشند. یک گراف عبارت. همانند یک دیاگرام حللت. شامل یک گره ابتدلیی مجزا و یک مجموعه از گره های پذیرش است. ‎ 

صفحه 146:
۷-۲ گراف عبارات دیاگرام حللت یک آتاملتابا الفبای ۶ را می توان به عنوان یک گراف عبارت در نظر گرفت. برچسب ها شامل لامبدا و عبارات متناظر با عناصر ۶ می باشند. کمانهای یک عبارت می توانند باه نیز برچسب دار شوند. هر مسیر در یک گراف عبارت یک عبارت با قاعده تولید می کند. زبان یک گراف عبارت اجتماعی از مجموعه های ارائه شده توسط عبارات با قاعده پذیرفته شده است. 

صفحه 147:
۷-۲ گراف عبارات مثال: این گراف عبارت عس*ط:: را می پذیرد. 

صفحه 148:
۷-۲ گراف عبارات Hera 425 یک زبان با توسط یک 0600 با الفبای ۲ پذیرفته می شود اگر و تنها اگر با یک مجموعه با قاده روی ۶ باشد. 

صفحه 149:
۷-۳ گرامرهای باقاعده و آتاماتای متناهی 5 یک محاسبه در یک آتاماتا با رشته ورودی شروع شده. چپ ترین عنصر را به ترتیب پردازش کرده و پس از تحلیل کامل رشته متوقف می شود.از طرف دیگر. تولید با عنصر ابتدایی گرامر شروع شده و عناصر پایلنی را به پیشوند فرم جمله ای مشتق شده اضافه می کند. 

صفحه 150:
۷-۲ گرامرهای باقاعده و آتاماتای متناهی مثال گرامر زیر زبان ( قالاح)*ه را تولید نموده و 0 0000 آن را مى يذيرد. 6: 6008۱09 ۰ 6 MA a 

صفحه 151:


صفحه 152:
WY ‏ویژگیهای همبستگی زبانهای باقاعده‎ ۷-۴ یک زبان روی الفبای با قاعده است . اگر آن: (۱ یک مجموعه (عبارت) باقاعده روی 2 (8 پذیرفته شده توسط ‎-OP@ a OPO,OEP‏ ‎tt)‏ تولید شده توسط یک گرامر با قاعده باشد. 

صفحه 153:
۷-۴ ویژگیهای همبستگی زبانهای باقاعده قضیه اگر »راو را دو زبان با قاعده باشند. آنگاه رالاه‌را , وربا وراه نیز زبانهای باقاعده خواهند بود. زبانهای باقاعده نسبت به عمل مکمل بسته هستند. اگر ما روی الفبای 2 با قاعده باشد. آنگاه ر-* 22 با نیز با قاعده خواهند بود. 

صفحه 154:
۷-۴ ویژگیهای همبستگی زبانهای باقاعده قضیه اگر بایک زبان با قاعده باشد. آنگاه ما نیز باقاعده است. قضیه اكرهدا وه‌با زبانهایی باقاعده باشند. آنگاه ۲9 نیز باقاعده است. 

صفحه 155:
۷-۵ یک زبان بی قاعده زبانهای بی قاعده زيان (20 لط با قاعده نیست. فرض کنید که با یک زبان روی 2 باشد. اگر رشته های ۰ 62 و(60200:/ا 2 با باعمسو باعمف برای 19 وجود داشته باشد. آنگاه با یک زبان باقاعده نیست. مثلاً مجموعه با شامل رشته های متقارن روی (طره] باقاعده نیست. 

صفحه 156:
۷-۵ یک زبان بی قاعده 

صفحه 157:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده فرض كنيد كه ) دیاگرام حالت یک 06*6 با »| حالت بوده و ع یک مسیر به طول > یا بیشتر باشد. در این صورت مسیر ۲ را می توان به زیر مسیرهای ۲,۲ و2 تجزیه نمود بطور یکه وحم و >اک(چ)ابجط بوده و ۳ یک چرخه باشد. 

صفحه 158:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده فرض کنید که با یک زبان با قاعده است که توسط یک ‎DEB DM‏ با حالت پذیرفته می شود و فرض کنید که < هر رشته موجود در دابا 2(51) !بط باشد.در اين صورت ‏ می تواند به صورت مب نوشته شود بطوریکه #0 . اک(بی)ایجط و به ازای ‎DO cw 4m‏ با 6 تب باشد. پیش قضیه فشار ابزار قدر تمندی برای اثبات بی قاعدگی زبانها است. 

صفحه 159:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده برای اينکه نشان دهیم (0۲۱200) با قاعده نیست بایستی رشته ای را با طول مناسب در با پیدا کنیم که هیچ رشته فشردنی برای آن وجود نداشته باشد.فرض می کنیم که با باقاعده است. ‏ را تعداد مشخص شده توسط پیش قضیه فشار در نظر می گيریم. با فرض اینکه < رشته » 6 آست . هر تجزیه سمی از < که در شرایط پیش قضیه فشار صدق می کند بایستی به شکل زیر باشد که ‎HHS‏ و 00< است. 

صفحه 160:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده u uv w a a! uMb* فشار هر زیر رشته به این شکل ب 25 ۱9 اه نا لب بت را تولید می کند که در زبان با وجود ندارد. از آنجائیکه 6 هیچ تجزیه ای ندارد که در شرایط پیش قضیه صدق کند. لذا نتیجه می گیریم که زبان با با قاعده نیست. 

صفحه 161:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده فرض ‎dbl dle kL OPO KD aS uF‏ ((0)),ا۱اگر وتنها اگر 0) یک رشته 2 با <(2)#طرا بپذیرد. ((81/)00 به تعداد نا متناهی عضو دارد اگر وتنها اگر 0 یک رشته با ا ©>(2) بدا را بيذيرد. فرض كنيد كه 009 و 000 دو 00209 باشند. يك روال تصميم گیری براى تعيين هم ارزى 000 و ©() وجود دارد. 

صفحه 162:
فصل هشتم. آتاماتای ۳۱500۷۷5۵ اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: 7 آتاماتای مسطللی۳) ۴ انواع ‎POO‏ "آتاماتای دو پشته ای "بهینه سازی ‎DPD‏ 

صفحه 163:
زبانهای باقاعده به عنوان زبانهایی تولید شده توسط گرامرهای باقاعده و پذیرفته شده توسط آتاماتای متناهی شناخته می شود. یک آتاماتای سطصم . یک ماشین با حالات متناهی همراه با یک حافظه پشته ای خارجی است . افزودن یک پشته به آتاماتا قابلیت مدیریت حافظه ‎oe pl LIPO‏ کند. LIPO : beta, PrstOu گروه کامپیوتر || نظریه زبانها و ماشینها صفحه: 164 

صفحه 164:
121151201018712 ‏آتاماتاى‎ 6-١ بى اتاماتاى تسس یک شش تایی (),0,0, آ, 2,) است که 3 یک مجموعه متناهی از حالات ۰ 2 یک مجموعه متناهی موسوم به الفبای ورودی. ] یک مجموعه متناهی موسوم به الفبای پشته.0 حالت ابتدایی ۰ 20۰ *) یک مجموعه متناهی از حالات پایانی, یک تابع گذر از ([)۷ ۲)* ([00 ۵*02 به زیر مجموعه هاى ([7)نا 1) © مى باشد. 

صفحه 165:
WY 121151201018012 ‏آتاماتاى‎ ۸-۱ یک 60009 داراى دو الفباست ۱-الفبای ورودی 2 که رشته های ورودی را شکل می دهد. ۲- الفبای ] که عناصر آن ممکن است روی پشته ذخیره شوند. 

صفحه 166:
۸-۱ آتاماتاى 121151201018012 نكته عناصر الفباى يشته اى را با حروف بزرك نشان مى دهيم. رشته هاى عناصر يشته اى را با استفاده از حروف يونانى نشان مى دهيم. یک 000008 با استفاده از حالت جارى : عنصر ورودی و عنصر بالایی يشته رفتار ماشين را تعيين مى كند. 

صفحه 167:
WY pushdown ‏آتاماتای‎ ۸-۱ گذر زیر سیب می شود: عنصر جاری ورودی مسر عدي كه اند ‎a(m,4,@)‏ 8 عنصر جاری پشته . حالت جاری حالت جدید الف) حالت ماشین را از و به ‎٩‏ تغییر می دهد. ب) عنصر ه را پردازش کند( هد نوار را به جلو براند). ج) © را از بالای پشته حذف کند( عمل ۳۶۳). د) ) را در پشته قرار دهد ) ‎A pop Jos‏ 

صفحه 168:
pushdown ‏آتاماتای‎ ۸-۱ یک آتاماتای مسط(صح می تواند توسط یک دیاگرام حالت نیز توصیف شود. برچسب روی ‎pais ILS‏ ورودی و عمل پشته را مشخص می کند. 

صفحه 169:
۸-۱ آتاماتاى 121151201018012 حال كليم می توانیم یک 60 00000 برای پذیرش زبان 1200 ۲ ايجاد (ب,م/عه :0 1-۶ ۲<0( اجرج فدرم تن 2 قرهطه- !زه 3 هط :]1 

صفحه 170:
pushdown ‏آتاماتای‎ ۸-۱ فرض کنید که (0,۷0,4, آ, (,) یک ۳606) باشد. یک رشته مسب(« توسط () قابل بذ برش است اگر یک لحالسبه [ما,: ] ۶ [نز6 ] وجود داشته باشد بطوریکه ) 6 ب باشد. زبان (0) مجموعه تمامی رشت های پذیرفته شده توسط () است. 

صفحه 171:
UY pushdown butt A-\ به محاسبه ای که یک رشته ورودی را می پذیرد. محاسبه موفق گفته می شود و به محاسبه ای که تمام رشته ورودی را پذیرفته و در یک حالت غیر پذیرش متوقف می شود. محاسبه ناموفق گفته می شود. گروه کامپیوتر اتلدريف زعافها زد رماشدتها صفحه؛ 172 

صفحه 172:
۸-۱ آتاماتاى 121151201018012 مثال ‎auc lwef{ab}iols POR O‏ را مىيذيرد. ‎O: Q={q0,9} 2, (۲,0‏ ([1۳۵-( ,2۳ ۶ اه ‎B‏ ۳ سجة (۲2)۵,۵ 09 ۳ ۱۳ 2م 1] 0:1 8 

صفحه 173:
WY 121151201018012 ‏آتاماتاى‎ ۸-۱ يى 20)209) قطعى است اكر حداكثر يى كذر براى هر تركيبى از حالت: عنصر ورودى و عنصر بالاى يشته وجود داشته باشد. دو كذر [عترو](.لا.:]60)0 و [00,ج](8, /ا,:[60)0 سازكار هستند اكر يكى از شرايط زير را دارا باشند ‎=O 91 u=v)‏ ‎a 2‏ (مكدةو ©)- يا 28 . a ‏مد‎ 0 NEV 9 tt o~0) a a 0 LO 5 ‏يا رد‎ ww) 

صفحه 174:
pushdown ‏آتاماتای‎ ۸-۱ یک 600*) قطعی است اگر آن شامل گذرهای ساز گار مجزا نباشد. مثا مثال زبان (4<00 ط4) (11:200 2)9را شامل ه ها یا تعداد یکسانی از "ها و طها است. پشته 0 60009 كه زبان بارا مى يذيرد. -36/ tb ®a 

صفحه 175:
۸-۲ انواع 10۸ هر گذر در تسس ۳۳۲-۱ کردن پشته ۲-(صحکردن یک عنصر پشته ای ۳-پردازش یک عنصر ورودی اگر هر گذر تنها موجب وقوع یکی از این عملیات شود. نظریه زبانها و ماشینها 

صفحه 176:
۸-۲ انواع ‎PDA‏ ‏گذر ها در یک ۳)062) ساده به اشکال زیر می باشند: ‎IAP]‏ ) , 696 & Aas, ) [a5] aay, .©)[ a] یک گذر توسعه یافته. یک عمل روی ‎POD‏ است كه يى رشته از عناصر را در پشته ‎pork‏ می کند. گذر[68)01:,0,۵(],)000 رشته 0 را در پشته اصح می کند. 

صفحه 177:
۸-۲ انواع 1۳10۸ مثال فرض كنيد كه (1:<0 لط )با است. 0089 )توسعه 22 يافته (و,م)-© یچ (مربرجعه 1 قاس رو ۱۱ فعسم ‎fd AR-(‏ ‎{L eh) (gob, 098‏ فص , امهو فص , اسجره. .و 91-۳8 ]1 8 , )-1]08۵8 ,۱-۵ ]1 #تطرج )2[», ]1 ۱۱-۷۲8 ]1 1] ‏,مم القه.‎ One ] 93 ‏بر‎ 

صفحه 178:
۸-۲ انواع ۳10۸ پیش قضیه فرض کنید ایک زبان پذیرفته شده توسط (,6,(,۲,2,0) ‎PDA‏ ‏با پذیرش تعریف شده توسط حالت پایلنی باشد. در اين صورت یک 66) وجود دارد که زبان را توسط حللت پایلنی و پشته خالی بيذ يرد. 

صفحه 179:
۸-۲ انواع ۳10۸ پیش فضیه فرض کنید میک زبان پذیرفته شده توسط (,6:,۳,۵,۷) ۲۸ 80۸ با پذیرش تعریف شده توسط پشته خللی باشد. در این صورت یک 08 وجود دارد که زبان با را توسط حالت پایانی و پشته خالی بپذیرد. 

صفحه 180:
W ۳1۸ ‏انواع‎ ۸-۲ شرایط زیر با هم معادلند: ( زبان با توسط برخی ۳0069)ها پذیرفته می شود. )# يى 000008000 با بات(000) هنا وجود دارد. (# يى 000008006 با بت(0)هنا وجود دارد. 

صفحه 181:
۸-۳ آتاماتای ۳0115101010 و زبانهای مستقل از 5 قضيه: فرض كنيد که بایک زبان مستقل از متن باشد. در این صورت ی وجود دارد که زبان با را بپذیرد. 

صفحه 182:
۸۳ آتاماتای 101251201010 و زبانهای مستقل از متن" فرض کنید که (,6۵,2,],2,0) - يى 00009 باشد. يى 0 0 توسعه يافته با تابع گذر2" بوسیله گذرهای 2 از 0) ایجاد می شود: (۱اگر [ج2 ]( ,68)01:,00 باشد. آنگاه برای هر 96۲) داریم [©,و] ‎-€0'(qi,U,A)‏ (۱اگر [,و]( ,60)01:,00 باشد. آنگاه برای هر 67) داریم [0),م] (601)0:,۷,۵. 

صفحه 183:
۸۳ آتاماتای 101251201010 و زبانهای مستقل از متن" مثال یک گرامر از ‎O‏ ۳006 ایجاد می کنیم. زبان (0)مجموعه (109۱۰20 است. 0: ‏,مه (جرجعه‎ 9], ‏<-اصطه)‎ a7, ls, B T={0} ‏باع(هطج2‎ ۶ -)( 

صفحه 184:
WY ‏آتاماتای 101251201010 و زبانهای مستقل از متن"‎ ۸۳ dud فرض كنيد كه () يك 0008 باشد. در اين صورت يى كرامر مستقل از متن © با (00ك(6)نا وجود دارد. 

صفحه 185:
۸-۴ پیش قضیه فشار برای زبانهای مستقل از متن پیش قضیه فرض کنید که 8 یک گرامر مستقل از متن در فرم نرمال شومسکی و تیگ یک اشتقاق از 6 ‎w‏ 2*: با درخت اشتقاق ۳ باشد. اگر عمق برابره باشد. آنگاه ©ك(س)كابدطا خواهد بود. 

صفحه 186:
۸-۴ پیش قضیه فشار برای زبانهای مستقل از متن فرض كنيد (,۴), 6,2)-) یک گرامر مستقل از متن در فرم نرمال شومسکی و مه * 2) یک اشتقاق از (0))ىا سس است. اگر 9 ک(س)ابجط باشد. آنگاه عمق درخت اشتقاق حداقل برابر + خواهد بود. 

صفحه 187:
۸-۴ پیش قضیه فشار برای زبانهای مستقل از متن قضيه (بيش قضییه فشار برای زبانهای مستقل از متن) فرض كنيد که میک زبان مستقل از متن باشدیک عدد 6 وابسته به با وجود داردبطوریکه هر رشته 6 با <(2 بط می تولند به صورت ‎Za waway‏ نوشته شود که دارای شرایط زیر باشد. ‎bk)‏ ک(هسم با (40<(ه) اپ + (ن) بسا و ‎2O'.wwexy 6b sla) ‎ ‏زبان ( (س)ك/بحط اول است ! *3© رست را.مستقل از متن نيست ‎ ‎ 

صفحه 188:
قضیه: مجموعه زبانهای مستقل از متن نسبت به عملیات اجتماع. الحاق و عملگر ستاره (99 محطل) بسته هستند. قضیه: مجموعه زبانهای مستقل از متن نسبت به عملیات اشتراک و مکمل بسته فرض کنید که *) یک زبان با قاعده و با یک زبان مستقل از متن باشد. در این صورت ب(۲٩)‏ مستقل از متن است. 

صفحه 189:
۸-۶ آتاماتای دو پشته ای آتاماتاى دو يشته اى: 00009 دو يشته لودارلىوساختار (2,00,0, | 9,2) لست ,2,7 آ, 0,2 مشابه 080008 تكيشته لىمىباشند تلبع كنرت. تقبعىاز (( ا ا)*(( )9 [)*(( 06 2)*© به زير مجموقه هايئاز (3 )نا 1)*([ )لا 1)*© لست حالت عناصر ورودى و عناصر بالاى هر دو يشته تعيين مى كنند كه كدام كذر بايستى انتخاب شود 

صفحه 190:
۸-۶ آتاماتای دو پشته ای مثال 08 دو پشته لی‌تعریفشده زیر بان( ۱۱۶ ۴ ۲ )<بارا می بذيرد. 0: ‏(مججمجعه‎ ] 4,3, 3)={Iee, 3 al} fabio} =5 ‏بو‎ 3 2۲۳,۵۰, 3 هد هب2 50 ‎J={fx, AB]‏ ] (ج)ع ‏3 3 ,م])-(3۵ ,مه زا ‎ ‎ 

صفحه 191:
فصل نهم :ماشينهاى توريتك اهداف رفتارى: دانشجو يس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: ” ماشين توريتك ۲ انواع پذیرش "آماشین های چند شیاره #ماشین های تورینگ فیر قطعی 

صفحه 192:
فصل نهم ۰ ماشینهای تورینگ ۳ ماشین تورینگ یک ماشین با حالات متناهی است که هر گذر آن عنصری را روی نوار چاپ می کند. ماشین تورینگ یک ‎ae‏ تلیی (۶,۲,8:0,) است که در آن 3) مجموعه متناهی از حالات . یک مجموعه متناهی موسوم به الفبای نوارشامل یک عنصر ویژه 0) که نماینگر فاصله خللی است. یک مجموعه از (0)-] موسوم به الفبای ورودی: یک تابع جزتی از 0 * ۲ به () | © موسوم به تلبع گذر و 0663 یک حللت مشخص به نام حللت ابتدایی مى باشد. رد مت ]سره ماب .رصح 33 ] 

صفحه 193:
‎٩-۱‏ ماشین تورینگ استاندارد ‎ ‏نوار یک ماشین تورینگ در یک جهت تا بی نهایت ادامه می یابد. مکانهای نوار با اعداد طبیعی از چپ به راست شماره گذاری می شوند. ‎a ۵ ۳۰۲ ۲ 4 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 194:
WY ‏ماشین تورینگ استاندارد‎ ٩-۱ یک گذر شامل سه عمل است: ۱ یر حالت ۲- نوشتن یک عنصر روی مربع در حال پویش توسط هد نوار ۳- حرکت هد نوار. جهت حرکت توسط آخرین جزء گذر تعیین می شود. 

صفحه 195:
‎٩-۱‏ ماشین تورینگ استاندارد ‎ ‏این کدر علت بای زااری به و نف داده عبر عد نوار را ااي جایگزین نموده و هد نوار را یک مکان به چپ حرکت می دهد. ‏یک ماشین تورینگ هنگامی متوقف می شود که برای زوج مرتب حللت جاری و عنصر ورودی. هیچ گذری تعریف نشده باشد. یک گذر میکن است بخواهد از مکان صفر نوار یک حرکت به چپ محدوده نوار انجام دهد که در لین صورت متوقف می شود وبه اين نوع توقف. توقف غیر عادی گوییم. هرگاه می گوییم یک محاسبه متوقف می شود. منظور توقف در شرایط عادی است. ‏گروه کامپیوتر اس نظربه زیانها و ماشینها | صفحه: 196 ‎ ‎ ‎ ‎ 

صفحه 196:
‎٩-۱‏ ماشین تورینگ استاندارد ‎ ‏ماشین تورینگ 006۳ با الفبای ورودی |طرت! یک کپی از رشته ورودی را تولید می کند. به عبارتی. محاسبه ای که با نوار شامل 20) شروع می شود با نوار ‎BUDD‏ متوقف می گردد. ‎8 ‏همم‎ ‎8 bee ‎ 

صفحه 197:
‎٩-۲‏ ماشین تورینگ به عنوان پذیرنده زبان ‏فرض کنید که (),2,0, آ,3,2)) یک ماشین تورینگ باشد. یک رشته 2:06 توسط حالت پایلنی پذیرفته می شود اگر محاسبه 0 با ورودی به در یک حالت پایانی متوقف شود. محاسبه ای که به طور غیر عادی متوقف می شود رشته ورودی را بدون توجه به حللت پایلنی ماشین رد می کند. زبان 60, که با (0)),ا نشان داده می شود. مجموعه تمامی رشته های پذیرفته شده توسط () است. ‎ 

صفحه 198:
‎٩-۲‏ ماشین تورینگ به عنوان پذیرنده زبان ‎ ‏یک زبان پذیرفته شده توسط یک ماشین تورینگ به :بان باز کشت شمارشس بذیر موسوم است. ‏ماشین تورینگی که برای تمامی رشته های ورودی متوقف می شود زبانی را می پذیرد که به آن باز "نی گویند. ‏باز گشتی بودن از ویژگیهای یک زبان است نه از خصوصیات ماشین تورینگ پذیرنده آن. ‎ ‎ 

صفحه 199:
‎٩-۲‏ ماشین تورینگ به عنوان پذیرنده زبان ‏مثال: ‏ماشین تورینگ © با اب © له © © هله © ‎fo".‏ 4< ‎bh R‏ ‏زبان (طالام۱00(۶) ۵8 را می پذیرد. ‎ ‎ 

صفحه 200:
‎٩-۳‏ انواع پذیرش در ماشینهای تورینگ ‏در ماشین تورینگی که برای پذیرش توسط توقف طراحی شده است. یک رشته ورودی پذیرفته می شود اگر محاسبه رشته موجب توقف ماشین شود. ‏فرض كنيد که (,0,0, ا,0,2) یک ماشین تورینگ با پذیرش توسط توقف باشد. یک رشته 2606:: توسط توقف پذیرفته می شود اگر محاسبه () با ورودی ‏ به طور عادی متوقف شود. ‎ ‎201 ‏صفحه:‎ | su leas alk ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 201:
‎٩-۳‏ انواع پذیرش در ماشینهای تورینگ ‎ ‎#aa(aub)s(aUb) ob; ‏مثال:‎ ‎ 

صفحه 202:
‎٩-۳‏ انواع پذیرش در ماشینهای تورینگ ‎ ‏نوعی از پذیرش موسوم به پذیرش توسط ورود که از حللت پایانی استفاده کرده و هیچ نیازی به محاسبات پذیرس جهت توقف ندارد. ‏یک رشته پذیرفته می شود اگر محاسبه وارد یک حالت پایانی شده باشد. ‎ ‎ ‎ ‎ 

صفحه 203:
‎٩-۴‏ ماشینهای چند شیاره ‏یک نوار چند شیاره نواری است که به شیارهای متععدی تقسیم شده باشد. يى مكان در يك نوار > شیاره شاما « عنصر از الفبای نوار است. دیاگرام زیر یک نوار دو شیاره با هد نوار در حالت پویش دو مکان معین را نشان می دهد. ‎ ‎ ‎ ‎ 

صفحه 204:
‎٩-۴‏ ماشینهای چند شیاره ‏قضیه: ‏یک زبان با توسط یک ماشین تورینگ دو شیاره پذیرفته می شود اگر و تنها اگر آن توسط یک ماشین تورینگ استاندارد پذیرفته شود. ‎ 

صفحه 205:
‎٩-۵‏ ماشین تورینگ با نوار دو طرفه ‎ ‏ماشین تورینگ با نوار دو طرفه: یک ماشین تورینگ با یک نوار دو طرفه مشابه ماشین تورینگ استاندارد است با این تفاوت که نوار آن از هر دو طرف تا بینهایت ادامه می یابد. ‏یک ماشین با نوار دو طرفه می تولند با قراردادن یک عنصر ویئه روی نوار جهت نمایش محدوده چپ نوار یک طرفه, عملیات یک ماشین استاندارد را شبیه سازی کند. ‎ ‎ 

صفحه 206:
‎٩-۵‏ ماشین تورینگ با نوار دو طرفه ‎ ‏مثال ‏ماشین تورینگ استاندارد) رشته هایی را روی ‎oe tub}‏ پذیرد که در آن قبل از هر ۶ در صورت وجود. حداقل سه " وجود داشته باشد. ‎ 

صفحه 207:
‎٩-۵‏ ماشین تورینگ با نوار دو طرفه ‎ ‎tack’ ‏یک زبان ما توسط یک ماشین تورینگ با یک نوار ‏دوطرفه پذیرفته می شود اگر و تنها اگر آن توسط یک ماشین تورینگ استاندارد پذیرفته می شود. ‎ ‎ 

صفحه 208:
‎٩-۶‏ ماشینهای چند نواره ‏يى ماش ار شامل کانوار و جاهد مجزا است.حالات و الفباهای یک ماشین چند نواره مشلبه ماشین تورینگ استاندارد است. ماشین به طور همزمان نوارها را می خواند.این کار با اتصال هر یک از هدها به یک بات کنترلی مجزا که حاوی حالت جاری است انجام می شود. ‎ ‏= نوار ۳ \ نوار ۲ ‏۲ ‏\ نوار ۱ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 209:
‎٩-۶‏ ماشینهای چند نواره ‏یک گذر در یک ماشین چند نواره ممکن است: ‎ ‎t)‏ حالت را تغییر دهد. (8 یک عنصر روی هر یک از نوارها بنویسد. (#ا هر یک از هدها را به صورت مجزا جابجا کند. ‏قضیه ‏یک زبان را توسط یک ماشین تورینگ چند نواره پذیرفته می شود اگر و تنها اگر آن توسط یک ماشین تورینگ استاندارد پذیرفته می شود. ‎ 

صفحه 210:
‎٩-۶‏ ماشینهای چند نواره ‏مثال: ‎ ‏ماشین تورینگ دونواره ای که دیاگرام حالت آن درزیرآمده است,زبان |(طارع)ص ‎tly (ier‏ 223 وین وید 

صفحه 211:
‎٩-۶‏ ماشینهای تورینگ غیر قطعی ‎ ‏يك ماشين تورينك غير قطعی ممکن است یک تعداد متناهی از گذرها را برای یک وضعیت مشخص تعین کند. اجزا یک ماشین غیر قطعی , به جز تلبع گذر عیناً مشلبه اجزا ماشین تورینگ استاندارد است. گذرها در یک ماشین غیر قطعی یه وسیله یک تابع جزئی از 0 به زیر مجموعه هایی از (,,ا)* 0*1 تعریف می شود. ‎ ‎ 

صفحه 212:
‎٩-۶‏ ماشینهای تورینگ غیر مثال ‏يا بعد از جه آن يك و قبل يا ب شته هايى را مى يذيرد كه در آن ب غیر قطعی زیر ره ماشين غير وجود داشته باشد. ‎ 

صفحه 213:
/ فصل دهم طبقه بددی شومسکی 1 اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: © گرامرهای بدون محدودیت " گرامرهای وابسته به متن " آتاماتای خطی محدود طبقه بندی شومسکی 

صفحه 214:
فصل دهم ۰ طبقه بندی شومسکی گرامرهای بدون محدودیت بزرگترین گروه از گرامرهای عبارت می باشند. یک قانون ««-- به مشخص می کند که یک رخداد از زیررشته ب در یک رشته ممکن است با رشته ۶ جایگزین شود. یک اشتقاق دنباله ای از جایگزینی ها مجاز است. تنها محدودیتی که روی یک قانون از یک گرامر اعمال می شود لین است که سمت چپ آن نبایستی تهی باشد. به اين سیستمهای بازنویسی رشته ها گرامرهای نوع صفر نیز گفته می شود. 

صفحه 215:
۱۰-۱ گرامرهای بدون محدودیت ر بدون محدودیت یک گرامر چهارتایی(),۳), 2,)) است یک گرا که () یک مجموعه متناهی از متغیرهاء _2 (الفبا)ایک مجموعه متناهی از عناصر پایانی.۳) یک مجموعه از قوانین و 5) یک عنصر مشخص در 6۵ می باشد. یک قانون از یک گرامر بدون محدودی به . شكل بدح است که در آن ( 0۷2ص و (06)6002: می باشد.فرض می شود که مجموعه های د) و 2 غیر الحاقی هستند. 

صفحه 216:
۱۰-۱ گرامرهای بدون محدودیت كرامرهاى باقاعده و مستتل از متن زیر مجموعه هایی از گرامرهای بدون محدودیت هستند. یک گرامر مستقل ازمتن یک گرامر عبارت است که در سمتچپ هر قانون آن تنها یک متغیر وجود دارد. قوانین یک گرامر باقاعده به یکی از اشکال i A— aB) iiA a) —iii A) می باشد که ۸,۳6۷ و 2 2 6 است. 

صفحه 217:
WY ‏گرامرهای بدون محدودیت‎ ۱۰-۱ مثال: گرامر بدون محدودیت زیر با عنصر ابتدایی 2زبان ( ۱1200 )را تولید می کند. O={G,®,0} fabio} => G— bla ۵-73 ‏ناسون‎ ‏وو ون‎ 

صفحه 218:
۱۰-۱ گرامرهای بدون محدودیت قضیه: فرض کنید که (2,)۳,2,)) <9) یک گرامر بدون محدودیت باشد. در اين صورت (),ا یک زبان باز گشتی شمارش پذیر است. قضیه: فرض کنید که با یک زبان باز گشتی شمارش پذیر باشد. در این صورت یک گرامر بدون محدودیت 8 با ‎D(B)Eb‏ وجود دارد. قضیه: مجموعه زبانهای باز گشتی شمارش پذیرنسبت به عمل اجتماع. الحاق و عملگر ستاره (0< محط) بسته است. 

صفحه 219:
۱۰-۲ گرامرهای وابسته به متن کرامرهای وایسته به متن یک مرحله میلنی بین گرامرهای مستقل از متن و گرامرهای بدون محدودیت می باشند. در این گرامرهاء هیچ محدودیتی برای سمت چپ یک قانون وجود ندارد. اما طول سمت راست آن بایستی حداقل به اندازه طول سمت چپ باشد. 

صفحه 220:
۱۰-۲ گرامرهای وابسته به متن اگر هر قانون به شکل ‎Nov‏ ‏باشد که ([ )من و ([ ۱02 ))6نهد و( بجهاگ(ن) اجه است. به قانینی که در شرایط فوق صدق کند یکنواخت(ع) گنته می شود. هر زبان وابسته به متن باز گشتی است. 

صفحه 221:
۱۰-۳ آتاماتای خطی محدود يك اتاماتای خی ‎UBB) ww‏ یک ساختار ‎O‏ (,<,>,2,0,], 0,2(است که در آن 6 ,,۵, 6,2,۲ مشابه ماشین تورینگ غیر قطعی می باشند. عناصر >,< عناصری مشخص از ۶ هستند. 

صفحه 222:
۱۰-۳ آتاماتای خطی محدود قضه: فرض كنيد ‎Sab as‏ زبان وابسته به متن است. در اين صورت. يك آتاماتاى خطى محدود (0) با بات(00)را وجود دارد. قضيه: فرض کنید که با یک زبان پذیرفته شده توسط یک آتاماتای خطی محدود باشد. در لين صورت 3۲ با- [ یک زبان وابسته به متن است. 

صفحه 223:
۱۰-۴ طبقه بندی شومسکی طبقه بندی شومسکی شامل چهار گروه از گرامرها(زبانها) است ۱- گرامرهای بدون محدودیت ۴۲- گرامرهای وابسته به متن ۳- گرامرهای مستقل از متن عد گرامرهای باقاعده که به ترتیب به گرامرهای نوع ۰.نوع ۱.نوع ۲و نوع ۲معروفند. 

صفحه 224:
۱۰-۴ طبقه بندی شومسکی گرامرها گرامرهای نوع ۰. گرامرهای عبارات. گرامرهای بدون محدودیت گرامرهای نوع ۱. زبانهای وابسته به متن آتامانای خطی محدود گرامرهای وابسته به متن, گرامرهای یگنواخت گرامرهای نوع ۲ زبانهای مستقل از متن آتاماتای مسج گرامرهای مستقل از متن گرامرهای نوع ‎gla pl SY‏ باقاعده. زبانهای باقاعده آتاماتای متناهی قطعی, رامرهای < 0 خطی راست ‎ce slat‏