نظریه زیان ها و اتوماتا

صفحه 1:
الله الرحمن الرحيم سم 

صفحه 2:
= 46 — دانشگاه بيام نور نظریه زبانها و ماشینها تهیه کننده: سید محمد حسین سلیم بهرامی 1 گروه: کامپیوتر ١ 

صفحه 3:
؟ عنوان منیع. نظریه زپانها و ماشینها * اتتشارایي< Peat گروه کامپیوتر مترجم: مهندس سید حجت الله جليلى نظریه زبانها وماشینها eT) نظریه زبانها و ماشینها صفحه: 

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

صفحه 5:
wk ‏مقد‎ ‏ضیات‎ ‏ل: رياضي‎ : ‏فصل او‎ شد: انشجو فصل با مفا هد خوا آشنا زیر ‎wali‏ ‏با ‏۱ ‏0 ۱ ۳ اين هیم ۱ از مطالعه ۱ پس شجو ٍ دانشح منهوم تابع 9 دگذاری نما عه ‎a‏ ‎ee‏ ‏3 ۱ لاع أن یت ‎w‏ 

صفحه 6:
۱-۱ نماد گذاری ۴ نماد «7: اشاره به کوچکترین عدد صحیح بزرگتر یا مساوی عدد حقیقی »« دارد. ۲ -۲۰۷ [--۲ مع دده ‎Ib pp oles‏ جزء صحيح بالاى > مى ناميم. ‏* نماد »1 اشاره به بزرگترین عدد صحیح کوچکتر يا مساوى عدد حقیقی > دارد. -۳۷ ‎f-=‏ ‎۴ fe ‏ود اپرل‎ ‏را جزء صحیح پایین >« می نامیم. ‎ ‎ 

صفحه 7:
۱-۲ توابع تلبع “4 تشکیل شده از یک متغیر با قاعده و قانون می باشد که به آزاء یک مقدار «. مقدار منحصر به فردی را به ( نسبت می دهد. نمودار یک تابع: مجموعه ای است از کلیه زوجهای مرتب که بوسیله تابع تعیین می شوند. دامنه یک تلبع: مجموعه مقادیری است که تابع به ازاء آنها تعریف می شود نظريه زبانها و ماشينها ‏ ]| صفحه: 7 

صفحه 8:
۱-۲ توابع تابع جامع: تابعى كه از لابه یک رابطه دودویی روی ‎VION‏ داراست. تابع جزني: رابطه بين 7*است وقتى كه €F [x,va] s€F [xe] ‎wl‏ تابعی که در آن هر عنصر «به یک عنصر مجزا در برد تصویر شود. ‎wb‏ 6( برشاست اگر که برد ۴ کل مجموعه 7باشد. ‎ ‎ 

صفحه 9:
۱-۳ نظربه مجموعه ها نمادهای مجموعه نماد 6 به معنای عضویت است. بطوریکه 2 6 «مشخص می کند که یک عضو يا عنصر مجموعه است. از دو براکت [ ] برای تعریف یک مجموعه استفاده می شود. ( ,4,9) 2« مجموعه هایی که تعداد زیاد یا تعداد نامتناهی عضو دارند بایستی به صورت ضمنی تعریف شوند. ‎{al c=? Por sowe octurd cucber w}‏ 

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

صفحه 11:
۱-۳ نظریه مجموعه ها اجتماع دو مجموعه به صورت زير تعریف می شود: 6 2 0۲ 2 6 72 721 ) -< 209۷ ‎Y}‏ ‏اختلاف دو مجموعه به صورت زیر تعریف می شود: ‎X-Y = {jzlzeXand ze Y}‏ مكمل #8 نسبت به 1] مجموعه عناصرى در ل] است که در 26 نمی باشد. 

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

صفحه 13:
WY ‏استقراء ریاضی‎ ۱-۴ ‏مثال:‎ ‏برای کلیه اعداد صحیح مثبت نشان می دهیم که‎ بايه استتراء: براى )>هداريم: فرض استةرا:فرض كنيد كه براى یک عدد صحیح مثبت دلخواه » داریم: گام "ترا لازم است که نشان دهیم: 

صفحه 14:
UY ‏قضایا و پیش قضایا‎ ۱-۵ ۶ در لغت به معنای گفتاری است که صحت آن باید اثبات شود. مثال:برای هر عدد صحیح ‎Ou‏ داریم: بیس تشه به عنوان یک قضیه کمکی برای اثبات قضایای دیگر به کار می رود. 

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

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

صفحه 17:
۱-۶ گراف ها جر ۸2(: به مسیری که از یک گره شروع شده و به خودش باز می گردد گفته می شود. ‎IS She) = OLS‏ شامل یک چرخه باشد به آن گراف چرخه ای گفته می شود. ‏سیر ساده: مسیری که از از یک گره دو بار عبور نکند. ‏طول( ایک مسیر در یک گراف وزن دار برابر مجموع وزنهای ‏مسير السلت: ‎ ‎ 

صفحه 18:
۱-۶ گراف ها ترا بدرن رت گرافی که لبه های آن هیچ جهتی نداشته باشند. ‎ALS: Jods OLS‏ بدون جهت که بین هر دو گره دلخواه از آن یک مسیر مشخص وجود داشته باشد. در :یک گراف بدون جهت. پیوسته و بدون چرخه است. ‏درشست ربشه دار درختی که در آن یک گره به عنوان ريشه درخت رحتی به عنوا انتخاب می شود. ‏درخت شا برای 8): یک زیر گراف متصل است که اولاً شامل همه گره های ) بوده و انیا یک درخت باشد. ‎ ‎ 

صفحه 19:
فصل دوم: زبان ها 7 اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: " مفاهیم رشته و زبان * مشخصات زبان ها " مجموعه های با قاعده 

صفحه 20:
WY ‏رشته ها و زبانها‎ ۲-۱ زبان: یک زبان یک مجموعه از رشته ها روی یک الفبا است. رشنه: يى رشته روى يك مجموعه 6( یک دنباله متناهی از عناصر ۲۷ است. النباى زبان: به مجموعه عناصرى كه رشته ها از آن ساخته می شوند الفبای زبان گوئیم. ‎atid)‏ فاقد عنصر را رشته تهی می نامیم که با نشان می دهیم. ‎ 

صفحه 21:
۲-۱ رشته ها و زبانها 2 فرض کنید که (عرطره! - 2باشد.عنصر * 3 شامل: ۸ طول» ‎abo‏ طول۱ ‎be va vb oe‏ و دجا جف جك كت : طول ‎Usb woo web wor who ubb obo wo wh wo‏ ‎boa bab bar boa bbb bbe boo bob boo‏ ‎obb obo oon oc cor‏ مان سوه بل ون 

صفحه 22:
WY ‏رشته ها و زبانها‎ ۲-۱ یک زبان روی یک الفبای 2 یک زیر مجموعه از #.2 است. : الحاق یک عمل دودویی است که دو رشته را به عنوان ورودی گرفته وبا چسباندن آنها در کنار هم یک رشته جدید ایجاد می کند. الحاق عمل اصلی در تولید رشته هاست. گروه کامپیوتر نظریه زبانها و ماشینها ‏ أ صفحه؛ 22 | 

صفحه 23:
۲-۱ رشته ها و زبانها فرض كنيد كه6بد8* باشد الحاق, :::: كه به صورت ,فى نوشته می شودف یک عمل دودویی روی #2 است كه به صورت زير تعريف مى شود: (۰,۱:۸: اگر 200( باشد. آنگاه#رد و حبف خواهد بود. (8 تام باز 7 فرض کنید که میک رشته با طول ‎fearythk(V)=WO‏ باشد. در اینصورت . به ازای برخی رشته ‎TE De oer gb Lgl‏ مرو در نتیجه م(سی)<رف خواهد بود. 

صفحه 24:
۲-۱ رشته ها و زبانها مثال فرض کنید که تک , وحن و عاماکب باشد. در اين صورت: ‎w dou w= wubb‏ ‎w=uboubb (vw) =ebvacre(w)‏ 

صفحه 25:
1 = -\ 

صفحه 26:
۲-۱ رشته ها و زبانها معکوس رشته فرض کنید که میک رشته در باشد. معکوس »به صورت زیر تعریف می شود: )1 پایه:2() اب . در اين صورت ۷2۸ و خواهد بود. ( گام باز گشت: اگر (200(یجا باشد. در اینصورت برای برخی رشته های سب به طول 4 و برخی 6 , تسبکیه2 معکوس رشته برابرخواهد بود: 

صفحه 27:
2-1 رشته ها و زبانها قضيه: فرض كنيد كدرب 62۳ باشد. در اين صورت 

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

صفحه 29:
۲-۲ مشخصات متناهی زبانها الحاق دو زبان 2۷۲ الحاق زبانهای او ۷ که به صورت 2۷ نشان می دهیم. زبان ‎ve}‏ هراتس۱ است." مرتبه الحاق ابا خودش را به صورت 2 نشان می دهیم. 26 به صورت ۸) [ تعریف می شود. 

صفحه 30:
۲-۲ مشخصات متناهی زبانها نال :فرض كنيد كه (صرطارك) )2 و (تتارحاتك) 72 است. در اينصورت ‎ICY = wabb, bubb,cobb,wbu,bba.cba‏ =X jaf XC=X= {a,b,c} X06 {a0,ub,u,bu,bb,br,ca,cb,c7} وه امه هه سوه موه هط رن ,وله رممم) 2262 جدحا, جادطا ,تتا ججادار جاتاتا, وجانار مر ‎ooo, oo‏ جاح ططاه رهاط ]1 

صفحه 31:
2-2 مش مشخصات متناهی زبانها فرض كنيد كه یک مجموعه باشد. در ‎١‏ ‏. در ‎Oi‏ = صورت: ‎ds OC‏ شاملت ما ‎a‏ د شت امی‌یشته ها ی ‎c‏ ‏بی‌لستکه می‌تولنند از عناصر 2 ساخته شوند مجموعه يشته جموعة رش ‎adele‏ 5 ای‌غیر تهیلیجاد شدها داز كا لست لست 

صفحه 32:
2-2 مشخصات متناهی زبانها مثال زبان (طاره)(طط)"(طاره)2 با شامل تمامی رشته های روی (عاره ) است که دارای زیر رشته عط می باشد. الحاق مجموعه ‎{bb}‏ ما را وجود علط در هر رشته از با مطمتن می سازد. مجموعه های (طارج! # مشخص می کند که هر تعدادی بو هر دز نمی می نولاد اعد با فبل ‎la SN‏ قرار 

صفحه 33:
۲-۳ عبارات و مجموعه های با قاعده مجموعه باقاعده: مجموعه اى با قاعده است كه بتواند با استفاده از عملیات اجتماع. الحاق و 2غ ودطاط از مجموعه تهی. مجموعه شامل رشته تهی و اعضای مجموعه الفبا توليد شود. 

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

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

صفحه 36:
۲-۳ عبارات و مجموعه های با قاعده عبارت با قاعده فرض کنید که 2 یک الفبا است. عبارات باقاعده روی 2 به صورت باز گشتی زیر تعریف می شوند: ۰:۲۱( .0 و (ه).به ازاء هر 26 عباراتی باقاعده روی 2 هستند. (8 كام باز تشت: فرض كنيد كه برت عباراتی باقاعده روی ۶ باشند.در این صورت عبارات لاد ,معدو ‎ae‏ نیز عباراتی باقاعده روی 2 هستند. ‎Kau 9(‏ عبارت باقاعده روی 2 است اگر آن بتولند با تکرار متناهی از مرحله گام باز گشت از عناصر پایه ای بدست آید. ‎ 

صفحه 37:
۲-۳ عبارات و مجموعه های با قاعده ((طنات)ط “ماه ود (دط*ما*(طاناه) زد ‎sat (aUb)*b(aUb)*b(aUb))‏ یک عبارت با قاعده برای مجموعه رشته هایی که شامل زیر رشته >5 نمی باشند.عبارت با قاعده *( طح) الا"( قه)*ه .ممکن است شامل هیچ پیشوندی از «اها نباشد. تمامی "ها بایستی حداقل به یک ۲ ختم شده و یا عنصر پایانی رشته باشند. 

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

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

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

صفحه 41:
۲-۱ گرامرها و زبانهای مستقل | ز متن قانون: یک قانون انون كه ‎aT‏ ‏010 1 سس ایس ‎igs au‏ ی وت عضوى از معمولا به ات به صورت نوشته مى شود. 

صفحه 42:
۳-۱ گرامرها و زبانهای مستقل از متن نکته: از آنجائیکه رشته تهی در(لا()2):؛ وجود دارد. لذا ۸ نیز ممکن است در سمت راست یک قانون قرار گیرد. قانونی به شکل به قانون تهی یا قانون لامبدا موسوم است. 

صفحه 43:
WY ‏گرامرها و زبانهای مستقل از متن‎ ۳-۱ مرحله اصلی در ثرایند ترلید, قبدیل یک رشته با استفاده از یک قانون است. ۰ بکار گیری قانون مها ‎sly PB‏ متغیر )در 2۶ رشته ‎Lewy‏ ‏تولید مى کند که آن را به صورت نشان می دهیم. 

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

صفحه 45:
UY ‏گرامرها و زبانهای مستقل از متن‎ ۳-۱ ‏مجموعه رشته های قابل اشتقاق از مه‎ ‏فرض كنيد که (),۳), 6,2)<) یک گرامر مستقل از متن و‎ ‏باشد. مجموعه رشته های قابل اشتقاق از مه به‎ 0 6)0105( ‏صورت باز گشتی زیر تعریف می شود:‎ ‏با ,»مه از مه قابل اشتقاق است.‎ ( (8 تام باز ۰.7 اگر بج)کن از مه قابل اشتقاق بوده و ‎B, WER‏ باشد. آنگاه مهد از مد قابل اشتقاق خواهد بود. ‎tt)‏ 0 | تمامی رشته های ایجاد شده از م« با بکار گیری تعداد متناهی گام باز گشت از مه قابل اشتقاقند. ‎ 

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

صفحه 47:
۳-۱ گرامرها و زبانهای مستقل از متن فرض کنید که (9<00,2,6۳,۵) یک گرامر مستقل از متن باشد. فرم جمله اى:يى رشته ((6)0108 به يى فرم جمله اى از 8) است اگر یک اشتقاق رمث ظ) وجود داشته باشد. ».یک رشته 26 یک جمله از 8) است اگر یک اشتقاق* ‎Mas‏ ‏۶ در) وجود داشته باشد. ‎OL‏ که آنرا با (8))رانشان می دهند.مجموعه زیرات. ‎ ‎ 

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

صفحه 49:
۳-۱ گرامرها و زبانهای مستقل از متن یک قانون ) به شکل را بازكشت مستقيم مى ناميم. به یک اشتقاق که 0 در ما نیست: باز گشت غیر مستقیم می گوییم. 

صفحه 50:
۳-۱ گرامرها و زبانهای مستقل از متن ۰ .. گرامر 6 که یک زبان شامل رشته هایی با تعداد مثبت و زوجی از ها را تولید می کند. )6,€,),0(=®@ ‎O={6,0}‏ ‎fab}->‏ ‏© 0 .68 :6 ۰.0۱۲۰ 48 

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

صفحه 52:
۳-۱ گرامرها و زبانهای مستقل از متن درخت اشتقاق فرض کنید که (,), 60,2)<)یک گرامر مستقل از متن بوده و84) w — یک اشتقاق باشد.درخت اشتقاق بم * © يى درخت مرتب شده است كه به صورت زیر ساخته می شود: 

صفحه 53:
۳-۱ گرامرها و زبانهای مستقل از متن ‎١‏ درخت اشتقاق (0)را با ريشه 0)مقداردهی کنید. ‎Sit)‏ با قانونی در اشتقاق بکار رفته برای رشته ,9 باشد. آنگاه را به عنوان فرزندان © به درخت اضافه کنید. ‏(#اگر قانونی در اشتقاق بکار رغته برای رشته ۷۶ باشد. آنگاه را به عنوان تنها فرزند9) به درخت اضافه کنید. ‎ ‎ ‎ 

صفحه 54:
UY ‏اكراميرنها و زبانهای مستقل از متن‎ 15: ۱ => & ١ ‏و‎ So ‏جم‎ 2۵ حم د موه 5« ]| = 000 >= aS 1 ‏س‎ بط جف ‎qh‏ — ۰ جر مس © اه ‎ae‏ سیر مجح © ورطردرطيه + حق ‎FR‏ ~ هت هه ‎ap 58‏ = — 3 سه جد ‎we 1 

صفحه 55:
۳-۱ گرامرها و زبانهای مستقل از متن فرض كنيد كه 8) يى كرامر مستقل از متن بوده ورددمق ا یک اشتقاق در 08 باشد که 2) می تواند به صورت با مها نوشته شود.در این صورت رشته های (#۳6)206ای وجود دارند که در شرایط زیر صدق می کنند: ) 

صفحه 56:
مثالهایی‌از گرلمرها و زبان‌ه9-60 ۳ فرض کنید ‎B aS‏ گرامری با قوانین زیر باشد: ۰ -) - 6-۱ در این صورت (< ۰ , < ۰ اي سا ۰)<()) با خواهد بود. گروه کامپیوتر نظریه زبانها و ماشینها ۱ صفحه: 56 

صفحه 57:
مثالهلیی‌از گرلمرها و زبان‌ها3-2 زبان ‎val SF‏ (0< و , 20 و گت ۲ 1 © ب @—+bO@rt bo یک رشته بم متقارن است اگر کته باشد. ‎obs‏ گرامر مجموعه متقارن روی رها ‎G—. Wal bb‏ ‎ ‎ ‎ 

صفحه 58:
مثالهلیی‌از گرلمرها و زبان‌ها3-2 eh Sh __ ©: G+ ObiwObbia iwbt OSuSaSCu} pol 5 obs 6 0 7 3 {In2",m™. ( cb) (b}) OD ‏طاهط‎ 

صفحه 59:
۳-۳ گرامرهای باقاعده كرامر باتاعده: یک گرامر مستقل از متن است که هر قانون آن دارای یکی از حالات زیر است: (- هم ‎_t, A®)‏ ‎wW)‏ هه كه در آن 0 6 6,6 و 206 می باشد. یک زبان با قاعده است اگر بتواند توسط یک كرامر با قاعده توليد شود. 

صفحه 60:
۳-۳ گرامرهای باقاعده مثال: گرامر بی قاعده گرامر با قاعده 0 6:9 د۵۱ ۵ . © C= _ ‏وه‎ oi! a © ‏ام‎ — 

صفحه 61:
WY ‏۲-۴مروری بر گرامرها و زبان ها‎ زبان گرامر ‎Dae Peo}‏ 0- 6:6 ۰ 6 جد ‎bbb‏ 4 قانون به كار رفته اشتقاق ‎ot) Gb 9-06‏ به ‎C— G08‏ ۴ " (0هده ‎Oui) "5 * Os‏ ‎(bbb) (wa) = @_, bbb‏ موه و و 

صفحه 62:
۳-۴مروری بر گرامرها و زبان ها مثالا زيان 5 مهو 9- 0 #(®)F0"(c'bo'ba*) C—wWta ‎obs‏ گرامر ‎owe 15 ۶ 2۰2 <0( ‎ ‎ ‎ 

صفحه 63:
فصل چهارم: مقدمه ای بر پارسر ها اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: ۴ اشتقاق چپ و ابهام ‎BLS ©‏ يى كرامر © يارسر ها 

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

صفحه 65:
۴-۱ اشتقاقهای چپ و ابهام زبان یک گرامر: مجموعه ای از رشته های پایانی است که می توانند به هر روشی از عنصر ابتدائی مشتق شوند. قضیه: فرض کنید(),۴), 6,2)<) یک گرامر مستقل از متن باشد. یک رشته ما در (0))ىا است اگر و تنها اگر یک اشتقاق چپ سمااز 8) وجود داشته باشد. 

صفحه 66:
۴-۱ اشتقاقهای چپ و ابهام یک گرامر مستقل از متن 2) مبهم (صسمضاسه) است. اگر یک رشته (0)را مم وجود داشته باشد بطوریکه با دو اشتقاق چپ مجزا تولید شود. مثال گرامر ‎iGula‏ قد 6 :6 ۶ یکگرلمر مبهملستیرا يشته هه دارلی‌دو لشتقاق‌چمجزا لست =o © = Ga 

صفحه 67:
۴-۱ اشتقاقهای چپ و ابهام ابهام از ویژگیهای گرامر است ‏ نه از ویژگیهای زبان. مثال: گرامر ۱6۵9۱۰ 96 مق :86 زبان عله*ط #6 است.اشتقاقهای چپ زیر ابهام 68 را نشان می دهند. © © = ها ۵ بت ‎lb — b&b‏ — ‎bw = bb‏ _ 

صفحه 68:
۴-۱ اشتقاقهای چپ و ابهام :یک گرامر غیر مبهم است اگر در هر مرحله از یک اشتقاق چپ تنها یک قانون وجود داشته باشد که ما را به اشتقاق یک رشته کامل هدایت کند. ‎A‏ اهبومه و ‎ 

صفحه 69:
۴-۲ گراف یک گرامر اشتقاقهای چپ یک گرامر مستقل از متن 2) می تواند به وسیله یک گراف جهت دار ‎AB)‏ )15 = راسر 7 )نشان داده شود. گره های كراف » فرم جمله ای های چپ گرامر هستند. یک فرم جمله ای جب. رشته ای است که می تواند بوسیله یک اشتقاق چپ از عنصر ابتدایی نتیجه شود. 

صفحه 70:
۴-۲ گراف یک گرامر فرض ‎sus‏ که (9),(), 6(,2)<)یک گرامر مستقل از متن باشد. كراف جب رام (60)و»گراف جهت دار(00,)۳,2) است که گره ها و کمانهای آن به صورت زیر تعریف می شوند: 1) : © ‏[رسرر])-‎ 600) byw by wploatoa oP rue r}) ‏ا‎ 

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

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

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

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

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

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

صفحه 77:
WY ‏پارسر بالا به پایین عمقی‎ ۴-۳ یک اشتقاق از (طاجوا) ۳ (6,0) 0 :66 - (ط+(0] © 9 :6 ب ۲۷۲ 86 سب بجر و ن ,۵ (6) م 

صفحه 78:
۴-۳ پارسر بالا به پایین اشتقاق هبو — ‎Q.‏ ‎(QLD)‏ ‏ينه ‎oD)‏ كم (b+b) = عمقی پشته ‎Gq‏ ‏[©,8] ‏[,۲۲ ‏((۳,۵] ‏[(۲,۵۵۲۲] ‏[(۴,۳۳۲] ‎[F.G+T)]‏ 

صفحه 79:
UY ‏تجزیه پایین به بالا‎ ۴-۵ هنگامی که ساختار جستجو با رشته ۲ آغاز می شود. الگوریتم حاصل یک پارسر پایین به بالا خواهد بود. مثال: ‎“sails‏ كاهث bib) bu) Dob اه )@© TH ( On ‏یه‎ or Tb 9 O_o هيه © 

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

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

صفحه 82:
فصل پنجم: فرمهای نرمال یک فرم نرمال یا اعمال محدودیتهلیی روی شکل قوانين موجود در گرامر تعریف می شود. گرامرها در یک فرم نرمال. مجموعه کاملی از زبانهای مستقل از متن را تولید می کنند. فرم های نرمال برای گرامرهای مستقل از متن: ۱- فرم های نرمال شومسکی ۷- فرم های نرمال گریباش ۲ کروه کامپیوتر ‏ ]| نظریه زبانهاو ماشینها ۰ ۷ صفحه: 82 

صفحه 83:
۵-۱ حذف قوانین لامبداء فرض کنید که (,), 9<)60,2) یک گرامر مستقل از متن باشد.یک گرامر (۳,)۵), 2"2))",۶) وجود دارد به طوریکه 1 L()=V()) (8 قوانين ‎'P‏ به شكل ‎w‏ -(2) می باشند که 0 ۵ و (۵46((۷02))) 6 ‎ee‏ است. 

صفحه 84:
UY ‏حذف قوانین لامبداء‎ ۵-۱ ‎pate: ۰‏ ابتدایی گرامر 9 باز گشتی است. ‏6 وج 0 :۵ ‏۵0 ك د اهب و اه کل مهد ۵ 6د © امم © ‎O Qi 5‏ ‎ 

صفحه 85:
WY ‏حذف قوانین لامبداء‎ ۵-۱ به متغفیری که بتواند رشته تهی را مشتق کند. ‎(Cpl) | ype‏ گفته می شود. یک گرامر بدون متغیرهای لامبداء به گرامر غیر انقباضی ‎(azarputrarta)‏ موسوم است. گروه کامپیوتر نظریه زبانها و ماشینها شخ تن | 

صفحه 86:
۵-۱ حذف قوانین لامبداء فرض کنید که (),۴), 2,())<) یک گرامر مستقل از متن باشد. الگوریتم زیر مجموعه ای از متغیرهای میرای9) را تولید می کند. الگوریتم ورودی: یک گرامر مستقل از متن (92)0:2,,۵ ۰( 6۱5۵ 2 : بانا06 ۲ ی ۰۱ 00 <: ۳860 7 صل ‎Por cack vortcble ® € O‏ ‘Ptere te wi ® nie ® word w € PREO* tea WOLL : = DOW ufo} 

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

صفحه 88:
۵-۱ حذف قوانین لامبداء فرض كنيد كه (),۳), 6(,2)<) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن (۰,.), 92)60.,2) وجود دارد بطوریکه tL(G .)=L()) ‏یک متغیر بازگشتی نیست.‎ 1G.) ‏باشد.‎ B=Giy EL(B) ‏از ,_ در :) وجود دارد اگر و فقط اگر‎ )9( 

صفحه 89:
۵-۳ حذف قوانین زنجیره ای بکار گیری یک قانون خه تنها طول رشته مشتق شده را افزلیش نمی دهد. بلکه عناصر پایلنی اضافی نیز تولید می کند. در واقع. این قانون یک متغیر رامجدداً نامگذاری می کند. قوانینی به این شکل به قوانین زنجیره ای موسومند. 

صفحه 90:
۵-۲ حذف قوانین زنجیره ای قوانین زیر را در نظر بگیرید: ,2 ۷۵ قانون زنجیره ای مشخص می کند که هر رشته قابل اشتقاق از 4۵ از9) نیز قلبل اشتقاق است. بکار گیری یک قانون زنجیره ای. یک مرحلهاضافی است که می تولند با افزودن قوانین ۶) حذف شود. قانون زنجیره ای را می توان با سه قانون 9)به صورت زیر جایگزین نمود: ۱ +۷۵ 

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

صفحه 92:
۵-۲ حذف قوانین زنجیره ای ايجاد مجموعه (0141:067100)0 ورودی: یک گرامر مستقل از متن غیر انقباضی حقیقی (62)0:26,0 ‎OUP) : = {0} 4‏ ‎PREO := 8.98‏ کاس ‎O1LO10(0)-PRCO 0‏ = : 00 ‎PREO : = CLO) 0.0‏ ‎wb 0.8‏ 06000 تاه بخ ‎Porewknie® Ody‏ ‎OWO10@) : = OLO10)U{O}‏ ‎rl OLG10(0) = PROO‏ 

صفحه 93:
۵-۲ حذف قوانین زنجیره ای قصيه فرض كنيد كه (02)60,2,60,)9) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن 690 وجود دارد بطوریکه tL(G 0)=L(B)) ‏هیچ قانون زنجیره ای نداشته باشد.‎ t Bo) 

صفحه 94:
۵-۳ عناصر غیر مفید عناصر مفید و عناصر ‎pat‏ مفيد فرض کنید 60 یک گرامر مستقل از متن است. در اين صورت یک عنصر (0)) » مفید(لاص) است اگر یک اشتقاق با "مسب کح وجود داشته باشد بطوری 45 ‎Div » seu,vE(OUD)‏ &% باشد. به عنصری که مفید نیست. غیر مفید(حصطهص) گفته می شود. 

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

صفحه 96:
۵-۳ عناصر غیر مفید قصیه فرض كنيد که (2),), 9<)6,۶) یک گرامر مستقل از متن است. الگوریتمی برای ایجاد یک گرامر مستقل از متن 4S yobs 2412 9929 Br=(Or, 57,0 7,6) ‎»)=L(6))‏ )با ‏(9 هر متغیر در )یک رشته پایانی در )را مشتق کند. ‎ 

صفحه 97:
۵-۳ عناصر غیر مفید مثال 0, - 8 © 0,8,6 +2 0 ,8 ۳۶ عبنم © 6 ۲ 1060© © طلهط © : 8 BO1GG1G DIP OF Ib 9۱0 ۰ 0 20۱۲ ۵ ۵ ۵ و و 5 

صفحه 98:
۵-۳ عناصر غیر مفید فرض کنید که (,۴), 2,())<) یک گرامر مستقل از متن است. الگوریتم زیر مجموعه ای کامل از متغیرهای قابل دسترس از ۵) را تولید می کند. 

صفحه 99:
۵-۳ عناصر غیر مفید یجاد متغیرهای قابل دسترس ورودی: یک گرامر مستقل از متن (6<)0,2,)۳,۵) ۰ (6) <: 686601 ۳0:9۲ م 060 :- 6604 - 0۲۰ REO = REGO ۲ Por ewh varkble BEOEO we ts Poreukinde ® 0 do oh dl vortbes nw REGOW wl REBOL =PROO 7 

صفحه 100:
۵-۳ عناصر غیر مفید قضیه فرض کنید که (),۴), 2)60,2) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن 690 وجود دارد بطوریکه ((۵) راح(ه ‎1L(®‏ ‏(00) 8 هیچ عنصر غیر مفیدی ندارد. 

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

صفحه 102:
WY ‏عناصر غیر مفید‎ ۵-۳ ۱- حذف عناصر غیر قابل دسترس: ۱-حذف متغیرهایی که رشته پایانی را ‎OD‏ 6۰ تولید نمی کنند: ‎Gs Ob‏ ‎b‏ ® — ۲-حذف متفیرهایی که رشته پایانی ۲- حذف عناصر غیر قابل دسترس: را تولید نمی کنند: ‎a‏ © 6 © متغیر 8) و عنصر پایانی 8) غیر مفید هستند. 

صفحه 103:
۵-۴ فرم نرمال شومسکی فرم نرمال شومسکی یک گرامر مستقل از متن (0<))0,2,)۳,)9)در فرم نرمال شومسکی است اگر هر قانون دارای یکی از حالتهای زیر باشد: +@, @O) ۱) a) _.#6) cl B,CCO-{G} a5 | کرو ‎sani‏ تظريه زيته وماشينيا.. |[ صفحه 203[ 

صفحه 104:
۵-۴ فرم نرمال شومسکی درخت اشتقاق در یک گرامر به فرم شومسکی یک درخت دودویی است. as فرض كنيد كه (,۲), 0,2))<) یک گرامر ‎eas‏ ‏الگوریتمی وجود دارد که یک گرامر (۳,۵), 6",2)<) در فرم نرمال شومسکی و معادل با 8) ایجاد کند. نظريه زبانها وماشينها 

صفحه 105:
UY ‏فرم نرمال شومسکی‎ ۵-۴ مثال : 82 tu 8:60 ‏و‎ ‎Wie © ‏له‎ ‎buf Vo 2۰ ‏مه‎ ‎Qle T 9 © ©© ۰ ‏ه'‎ BT. OO T O® ‏ك‎ ۰ 0 ۵ ۵ © 

صفحه 106:
۵-۴ فرم نرمال شومسکی مثال ی Ls OR OY IbILT تا ا سيلتكر+ “الست ۷ + cual ® Kil T ماب یانگر( لست ‎bal‏ بیانگرا لست ‎‘Ss‏ ‏بسیانگره لست © G+ bt) 6- 60۷۱۲۱ (®) P+ b1() i 

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

صفحه 108:
WY ‏حذف باز گشت چپ مستقیم‎ ۵-۵ مثال: 4 ای بش۳ جا واه مه بو 9 Ov eT tbic 2 —_—_ @—Oul Obi bic ‏ارس‎ bath 

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

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

صفحه 111:
۵-۶ فرم نرماله گریباش فرم نرمال گریباش یک گرامر مستقل از متن (92))0,2,۳,)9)در فرم نرمال گریباش است اگر هر قانون دارای یکی از حالتهای زیر باشد: -.(۱6( )4 که ۱) ۰... که۳6 و برای هر (6060-6, .. ,۴,6 است. 

صفحه 112:
WY ‏فرم نرماله گریباش‎ ۵-۶ موی ذا ها جو مثال: ۵۱ و 1 ۵۱۵۵۱۵۵۱۰ و ۱۹۵۵۱۹۵۱۸۵۱۰ ۱۵۲۵۵۱۲۵۵ ۱۱۲۲۱۹۵۲۱۲ ره مق ‎COTW Iisa‏ سب تس ا -ي© 4811181 نب 

صفحه 113:
۵-۶ فرم نرماله گریباش مثال: ‎il ee‏ اش فرم ترما بياش مال شومسكى 0 هر انسح = 0 ل مس بر ‎sore =‏ مطح => 

صفحه 114:
5 ششم: آتاماتای متنا فصل ششم: آتاماتای متناهی اهداف رفتاری: 7 ف فاهیم زیر آشنا خواهد شد: دانشجو يس از مطالعه اين فصل با مفاهيم زير ۳ آتاماتای قطعی ۴ دیاگرام ات "آتاماتای غیر قطعی 

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

صفحه 116:
۶-۲ آتاماتای متناهی قطعی(0) 6 یک آتامانای متناهی قطعی (06) 

صفحه 117:
۶-۲ آتاماتای متناهی قطعی(:20) ۳ ۳ حالات یک 0008 بيانكر وضعيت داخلی ماشین هستند. ورودی. یک دنباله متناهی از الفبای 2 است. یک محاسبه آتاماتا شامل اجرای مجموعه ای از دستورالعملها است. اجرای یک دستورالعمل حالت ماشین را تغییر می دهد. هدف از محاسبه یک آتاماتا تعیین قابلیت پذیرش یک رشته ورودی است. 

صفحه 118:
WY \ ۳ ‏آتاماتای متناهی قطعی(:20)‎ ۶-۲ فرض کنید که (,,0, 0<)0,2) یک 0069) باشد. زبان 40 که با (0))ما نشان داده می شود. مجموعه ای از رشته ها در * 2 است که توسط () يذيرفته مى شود. گروه کامپیوتر نظریه زبانها و ماشینها تسف تن 

صفحه 119:
۶-۲ آتاماتای متناهی قطعی(سداه) -۳) مثال 0 06*0) یکمجموعه از يشته هایی‌را ریی([0,۳] می‌پذیرد که شاملزیر يشته ما هستند بدینصویتکه (طناك)طاط*(طاناه)>-(00) را لست ©: 9) ( ‏علطم‎ ‎P={} 

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

صفحه 121:
۶-۲ آتاماتای متناهی قطعی(2) ۳ ۳ تابع گذر توسعه یافته و از یک 0600 با تابع گذر 2 تابعی است از 260 به 6 که به صورت باز گشتی زیر روى طول رشته ورودی تعریف می شود: ( پایه: 0-(س)بسط . در این صورت 3 برد و 8( )جه اسث. 0 ت(س)كابدط . در اين صورت رن ه>(براى برخى 6-:5) و 9ب )< 2 (هرج) شت. (: مرحله بازگشت: فرض کنید 0<(ر)ایجه] باشد.آنگاممی‌صی و 2 (0(رو), (سرو)ء 6 خواهد بود. 

صفحه 122:
۶-۳ دیاگرامهای حالت و مثالها دبا کرام حاات بت 7( یک گراف جهت دار بر چسب شده است که گره های آن مبین حالات ماشین بوده و کمانهایش از تابع گذر بدست آمده است. 

صفحه 123:
۶-۳ دیاگرامهای حالت دیاگرام حالت یک 06۳ (),0,۷0, 2)0,2() یک گراف بر چسب دار 9 با شرایط زیر است: ( گره های 9) عناصر ) هستند. (9 برچسب کمانهای 0 عناصر 2 هستند. =O) ‏گره ابتدایی با فرم نمایشی‎ WD) (0) به مجموعه گره های پذیرش است که هرگره پذیرش با )مشخص می شود. ‎Sv)‏ کمان از گره به‌چ با برچسب » وجود دارد اگر ۵(,ج)-زل) باشد. (ان براى هر گره‌چوعنصر 620دقيقاً یکی کمان با برچسب 0 از و خارج می شود. 

صفحه 124:
WY ‏دیاگرامهای حالت و مثالها‎ ۶-۳ محاسبه 06۳0) با ورودی عطه و مسیر متناظر آن در دیاگرام به صورت زیر است: مسیر محاسبه 575 [ ,مج [ططدارم] | = (طج] | | و ‎El‏ ‏0 لو اعم رشته‌عاطح‌قابل پذیرش است زیرا در حالت پایانی چمتوقف شده است. 

صفحه 125:
ت و مثالها ۶-۳ دیاگرامهای حالت و مثال شته حاط نمی باشند. 1 : زیر ر هایی روى إطرك! كه شامل شته هاي 2 ْ 

صفحه 126:
ت و مثالها ۶-۳ دیاگرامهای حالت و مثال تعداد زوجىكو يبلنىوشامزيشته هاروى[ط,ك) باتعنادز كلاد فردیط را می‌بذیرد. 

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

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

صفحه 129:
WY ‏آتاماتای متناهی غیر قطعی‎ ۶-۴ زبان ‎OD‏ 0*69() که با (0))انشان داده می شود. مجموعه ای از رشته های پذیرفته شده به وسیله 0) است. بدین صورت که LO) =v bikers is 0 powutaiva [gow] *[y, Hohage®} 

صفحه 130:
۶-۴ آتاماتای متناهی غیر قطعی دیاگرام حالت یک ‎DPB‏ (0,۷0,6, 2)0,2() یک گراف جهت دار 08 با شرايط زیر است: (۱ گره های ظ) عناصر ) هستند. ‎٩(‏ برچسب کمانهای ظ) عناصر 2 هستند. ‎go)‏ #ا گره ابتدایی است. ‏( ,9 مجموعه گره های پذیش است. ‎Sv)‏ کمان از گره و به با برچسب ت وجود دارداگر (,ج6)-ز0 ‎ ‎ 

صفحه 131:
۶-۴ آتاماتای متناهی غیر قطعی مثال دیاگرامهای حالت 20)و26) آتاماتای متناهی را تعریف می کنند که ‎#bb(aub)s#(aub)‏ را می پذيرند. 

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

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

صفحه 134:
WY ‏گذرهای لامبدا‎ ۶-۵ مثال: می خواهیم از گذرهای لامبدا برای ایجاد یک 06۴622- که رشته هایی به طول زوج را بروی (طره! می پذیرد. استفاده کنیم. ابتدا دیاگرام حللت را برای ماشینی که رشته های به طول دو را می پذیرد تشکیل می دهیم. < @ wb @) sb © 

صفحه 135:
۶-۵ گذرهای لامبدا برای پذیرش رشته تهی . یک کمان لامبدا از «به م اضافه می شود. رشته هایی به طول زوج مثبت با استفاده از کمان لامبدای‌م :4 ‎qo‏ برای تکرار دنباله ,رم پذیرفته می شوند. 

صفحه 136:
۶-۶ حذف غیر قطعیت همبستکی لامبدای یک حالت ب: که با -(ب)حعحم( نشان داده می شود. به صورت باز گشتی زیر تعریف می شود. ( پایه: -()حسحوطم< و 6 (8 مرحله بازگشت: فرض کنید که ب یک عنصر از (و)صعحاعد باشد.گر ( ,)6ب باشد. آنگاه (و)عسمحطم( ب 6 است. (8 همبستكى: و در -(و)صمحطه3 است اگر بتواند با یک تکرار متناهی ازمرحله باز گشت بدست آید. 

صفحه 137:
WY ‏حذف غیر قطعیت‎ ۶-۶ ‏مثال‎ جدولهای گذر برای تابع گذر8 و تابع گذر ورودی !یک 606*692- به همراه دیاگرام 0 ارائه شده است. زبان ط*س+:(: می باشد. 

صفحه 138:
{ea} 0 (و مدرو 8 8 

صفحه 139:
۶-۶ حذف غیر قطعیت مثال ماشینهای 0()و09) به تر تیب (0)#ود را می پذیرند. 

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

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

صفحه 142:
WY ‏فصل هفتم : زبانها و مجموعه های با قاعده‎ اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: " آتاماتای متناهی و مجموعه های با قاعده ؟ گراف عبارت آزبان بی قاعده [ee eet ees | ‏كدده كاسيوتر‎ 1 

صفحه 143:
26 كرامرها به عنوان تولید کننده های زبان, و آتاماتای متناهی به عنوان پذیرنده های زبان معرفی شده اند. ‎rod‏ هفتم : زبانها و مجموعه های با قاعده ‏هر آتاماتای متناهی با الفبای 2 یک زبان روی ۶ را می پذیرد. خانواده زبانهای پذیرفته شده توسط آتاماتا دقیقاً شامل مجموعه های باقاعده روی ‏ است. ‎ ‎ ‎ ‎ 

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

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

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

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

صفحه 148:
۷-۲ گراف عبارات همع این گراف ‎ab rob Syke‏ را می پذیرد. مثال: 

صفحه 149:
UY ‏گراف عبارات‎ ۷-۲ Herat ‏قضيه‎ یک زبان با توسط یک *000 با لفبای ۲ يذيرفته مى شود اكر و تنها اگر ریک مجموعه با قاده روی 2 باشد. 

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

صفحه 151:
۷-۲ گرامرهای باقاعده و آتاماتای متناهی مثال گرامر زیر زبان ( ظالاه)*ه را تولید نموده و ‎OD‏ 000200 آن را مى يذيرد. 6: 6008۱09 ۰ 86 ‏لها‎ a 

صفحه 152:


صفحه 153:
WY ‏ویژگیهای همبستگی زبانهای باقاعده‎ ۷-۴ یک زبان روی الفبای با قاعده است . اگر آن: (۱ یک مجموعه (عبارت) باقاعده روی 2 (8 پذیرفته شده توسط ‎-DEO ab OPB,DEO@‏ (90 تولید شده توسط یک گرامر با قاعده باشد. 

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

صفحه 155:
۷-۴ ویژگیهای همبستگی زبانهای باقاعده قصیبه اگر ‎Kb‏ زبان با قاعده باشد. آنگاه بنیز باقاعده است. قضیه اگر»با وبا زبانهایی باقاعده باشند. آنگاه ۲سا نیز باقاعده است. 

صفحه 156:
۷-۵ یک زبان بی قاعده زبانهای بی قاعده زبان (۲۱۵200 0 با قاعده نیست. فرض كنيد که با یک زبان روی 2 باشد. اگر رشته های ب 62 و(()۷:62 2+ با را6‌بعو باع‌رف برای 19 وجود داشته باشد. آنگاه با یک زبان باقاعده نیست. مثلا مجموعه با شامل رشته های متقارن روی (عرت"] ,باقاعده نیست. 

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

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

صفحه 159:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده قضیه فرض کنید که با یک زبان با قاعده است که توسط یک 0 ‎DEB‏ ‏با حالت پذیرفته می شود و فرض کنید که < هر رشته موجود در بابا اک(ج)ابجط باشد.در این صورت 2 می تواند به صورت عم نوشته شود بطوریکه زب ۰ اک(مم) اج و به ازای هر بعد. 2 با 6 تب باشد. پیش قضیه فشار ابزار قدر تمندی برای اثبات بی قاعدگی زبانها است. 

صفحه 160:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده براى اينكه نشان دهیم (20 |اطاج) با قاعده نیست بایستی رشته ای را با طول مناسب در با پیدا کنیم که هیچ رشته فشردنی برای آن وجود نداشته باشد.فرض می کنیم که با باقاعده است. ‏ را تعداد مشخص شده توسط پیش قضیه فشار در نظر می گيریم. با فرض اینکه < رشته » 6 است . هر تجزیه برمی از < که در شرلیط پیش قضیه فشار صدق می کند بایستی به شکل زیر باشد که ۸+۲ و 00< است. 

صفحه 161:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده u uv w a a! uMb* فشار هر زير رشته به اين شكل.8 5ك ‎wwWEiba bb‏ را توليد مى كند كه در زبان ما وجود ندارد. از آنجائيكه ‎ZED‏ هيج تجزيه ای ندارد که در شرایط پیش قضیه صدق کند. لذا نتيجه مى كيريم كه زبان با با قاعده نیست. 

صفحه 162:
۷-۶ پیش قضیه فشار برای زبانهای باقاعده فرض كنيد كه () يى 000209 با ؟! حالت باشد. ((00)ما ذاكر وتنها اكر 0) يى رشته ‏ با ءا<(2)ابكمرا بيذيرد. ((0))با » به تعداد نا متناهی عضو دارد اگر وتنها اگر 0) یک رشته با >(2)ابط را بپذیرد. فرض کنید که ‎SL DPD 95 Do 9 Da‏ يى روال تصمیم گیری براى تعيين هم ارزى ‎De 9 Da‏ وجود دارد. 

صفحه 163:
فصل هشتم: آتاماتای ۳۱5060۲۴ اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: © آتاماتای طایح ‎POO gli!"‏ "آتاماتای دو پشته ای "بهینه سازی ‎DE®‏ 

صفحه 164:
Se زبانهای باقاعده به عنوان زبانهایی تولید شده توسط گرامرهای باقاعده و پذیرفته شده توسط آتاماتای متناهی شناخته می شود. یک آتاماتای سط(صم . یک ماشین با حالات متناهی همراه با یک حافظه پشته ای خارجی است . افزودن یک پشته به آتاماتا قابلیت مدیریت حافظه 10رارا فراهم می کند. LIPO : ‏وا‎ , PrstOu نظریه زبانها و ماشینها ۰ [| صفحه: 165 

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

صفحه 166:
WY 121151201011713 ‏آتاماتاى‎ 6-١ يى 60008 داراى دو الفباست: ۱-الفبای ورودی که رشته های ورودی را شکل می دهد. ۲- الفبای ] که عناصر آن ممکن است روی پشته ذخیره شوند. 

صفحه 167:
121151201011713 ‏آتاماتاى‎ 6-١ نكته عناصر الفباى يشته اى را با حروف بزرك نشان مى دهيم. رشته هاى عناصر يشته اى را با استفاده از حروف يونانى نشان مى دهيم. یک ‎b POD‏ استفاده از حالت جاری . عنصر ورودی و عنصر بالایی پشته رفتار ماشین را تعیین می کند. 

صفحه 168:
121151201011713 ‏آتاماتاى‎ 6-١ كذر زير سبب مى شود: عنصر جاری ورودی مسر عدي كه اند ‎a(m,4,@)‏ 8 عنصر جاری پشته حالت جاری حالت جدید الف) حالت ماشین را از و به و تغییر می دهد. ب) عنصر ه را پردازش کند( هد نوار را به جلو براند). ج) 0 را از بالای پشته حذف کند( عمل ۳۳۳). د) 0 را در پشته قرار دهد ( عمل ۳۳۳). 

صفحه 169:
121151201011713 ‏آتاماتاى‎ 6-١ یک آتاماتای مطلاصح می تواند توسط یک دیاگرام حالت نیز توصیف شود. برچسب روی کمانهاء عنصر ورودی و عمل پشته را مشخص می کند. 

صفحه 170:
121151201011713 ‏آتاماتاى‎ 6-١ ‎cle POO OG pals ge de‏ يذيرش زبان [9200 ط ) ایجاد ‏(«رجعه :0 ‏2 اطعا ‎۲ <)0( ‏رمع ‏قسرمج - .]1 ‏و 19-0 ۳,۵8 - [1]:0 ‎ ‎a ‎ ‎ 

صفحه 171:
WY 121151201011713 ‏آتاماتاى‎ 6-١ فرض کنید که (),2,0, آر (,0) یک ۳600 باشد. یک رشته Gi] [shoe] dea ‏توسط () تابل بذیرش است اگر یک‎ Pie ‏وجود داشته باشد بطوریکه ) 6 چ باشد. زبان (0) مجموعه تمامی ر‎ ] ‏های پذیرفته شده توسط () است.‎ 

صفحه 172:
WY pushdown ‏آتاماتای‎ ۸-۱ به محاسبه ای که یک رشته ورودی را می پذیرد. محاسبه موفق گفته می شود و به محاسبه ای که تمام رشته ورودی را پذیرفته و در یک حالت غیر پذیرش متوقف می شود. محاسبه ناموفق گفته می شود. كروه كامبيوتر انظد يف زءافها رد رماشيتها صفحه؛ 173 

صفحه 173:
WY 121151201011713 ‏آتاماتاى‎ 6-١ مثال ‎chy twef{ab}olLs 00009 O‏ س5ة] را مئيذيرد. ([0,])ع ,م2 ا(وره)9 :0 fabio} = ‏,م2‎ 3), 0[( T={®,0} Amr, {le 1 © ,درج - به ]1 ‎=a}‏ 2( © ,طرب)- ([:64. ]1 

صفحه 174:
121151201011713 ‏آتاماتاى‎ 6-١ ‎Col 2b5 POD‏ 51 حداکثر یک گذر برای هر ترکیبی از حالت؛ عنصر ورودی و عنصر بالای پشته وجود داشته باشد. ‏دو گذر [سرج](۸ 60000 و [0),ج]( ,60001۷ ساز گار هستند اگر یکی از شرایط زیر را دارا باشند ‎=O 91 u=v) ‏مص وو هق يا 28 . ‏(9200) 8 و رکب یا رب ‏(ن تلد یایب و 38 یا 20 . ‎ ‎ 

صفحه 175:
121151201011713 ‏آتاماتاى‎ 6-١ ‏قطعى است اكر آن شامل كذرهاى سازكار مجزا نباشد.‎ POO ‏یک‎ زبان (412<200 ۲ 0) (۱۸20 0)<را شامل ه ها یا تعداد یکسانی از "ها و ها است. پشته ‎D‏ 000209 كه زبان بارا مى يذيرد. د حر 20 

صفحه 176:
۸-۲ انواع ۳10۸ هر گذر در ‎foc dw L POD‏ همراه است! ۲۳۲-۱ کردن پشته ۲-اصح‌کردن یک عنصر پشته ای ۳-پردازش یک عنصر ورودی اگر هر گذر تنها موجب وقوع یکی از این عملیات شود. گروه کامپیوتر نظریه زبانها و ماشینها م 1 

صفحه 177:
PDA ‏انواع‎ ۸-۲ گذر ها در یک ۳)062) ساده به اشکال زیر می باشند: ‎iAP]‏ ( , 696 ‎As, ) [asl]‏ € ‎Ohl si]‏ ,9( یک گذر توسعه یافته. یک عمل روی ‎POD‏ است كه يى رشته از عناصر را در پشته ‎pus‏ می کند. گذر[68)0:,0,۵(],)000 رشته 0 را در پشته اصح می کند. 

صفحه 178:
۸-۲ انواع ۳۸ مثال فرض کنید که (۱۸20 نا 2)۵را است. COB COB ‏(1)تسوسعه‎ ‏:یرجه (مربرجعه‎ GR} gal, ‏قعص املزهيو])‎ {Lara ‏قعص )ملهو ودس‎ 1]0.9-) ۰ )9 {[qAB=(, 8 1] [۱-۵ ۱۳ ۱ 1۱9-۵ AL GTi (u,b, Og ۱] 9-۰ ۱] ‏اه )و9‎ ! ‏,له‎ Oyo [A= bi, 

صفحه 179:
۸-۲ انواع ۳۸ پیش قضیه فرض کنید ایک زبان پذیرفته شده توسط (,6:۶,۳,۵,۷۵) 8۵۸ 1 با پذیرش تعریف شده توسط حالت پایلنی باشد. در این صورت یک ‎POD‏ وجود دارد که زبان بأرا توسط حللت پایلنی و پشته خالی بپذیرد. 

صفحه 180:
۸-۲ انواع ۳۸ بيس قصيه فرض كنيد ايك زبان يذيرفته شده توسط (0,0؟,9,5,]:,2) ۱ ۳0۸ با يذيرش تعريف شده توسط يشته خالى باشد. در اين صورت يىف 08 وجود دارد که زبان با را توسط حالت پایانی و پشته خالی بپذيرد. 

صفحه 181:
WY ۳10۸ ‏انواع‎ ۸-۲ شرایط زیر با هم معادلند: ( زبان را توسط برخی ‎LPO‏ پذیرفته می شود. )# یک ۳09620 با ,<(0()),ا وجود دارد. (# يى 60008006 با بات(006)هنا وجود دارد. 

صفحه 182:
۸۳ آتاماتای 115100۲۷10 و زبانهای مستقل از ‎VY‏ ‎Gl‏ ‏قضیه: فرض کنید که با یک زبان مستقل از متن باشد. در این صورت ی وجود دارد که زبان بارا بپذ یرد 

صفحه 183:
۸۳ آتاماتای ‎pushdown‏ و زبانهای مستقل از متن" فرض کنید که (,0,۶,۲,۵,۷0) -1 یک ۳0) باشد. یک 6۲0۵۵ 0 توسعه يافته با تابع گذر2" بوسیله گذرهای 2 از ‎D‏ ایجاد می شود: [3,8] ‏آنگاه برای هر 96۲) داریم‎ wd E—(Gi.U, )[ a9] 511) . €0'(qi,U,A) (اگر [9,و]( ,60)0:,00 باشد. آنگاه برای هر 96۲) داریم [00),و] (۵,ا:0) 60 . 

صفحه 184:
۸۳ آتاماتای ‎pushdown‏ و زبانهای مستقل از متن" مثال یک گرامر از 0 ۳006 ایجاد می کنیم. زبان (مجموعه (10-9۱۰20 است. (هما(سمه هه 8 ,م2 2 ها 3 سااع(ه مه ‎T={0}‏ P={5} 

صفحه 185:
۸۳ آتاماتای ‎pushdown‏ و زبانهای مستقل از متن" قضیه: فرض كنيد كه © يك 0000 باشد. در اين صورت يى كرامر مستقل از متن © با (0)),را<()) با وجود دارد. 

صفحه 186:
۸-۴ پیش قضیه فشار برای زبانهای مستقل از متن پیش قضیه فرض كنيد كه 8) يى گرامر مستقل از متن در فرم نرمال شومسکی و مبیث) یک اشتقاق از 6 بر ۲2 با درخت اشتقاق ۳ باشد. اگر عمق برابره باشد. آنگاه "6 ک(سم اجه خواهد بود. 

صفحه 187:
۸-۴ پیش قضیه فشار برای زبانهای مستقل از متن فرض کنید (,۳), 6,2)<) یک گرامر مستقل از متن در فرم نرمال شومسکی و مه * 2) یک اشتقاق از (0))ىا سس است. اگر 9ک(س۲# باشد. آنگاه عمق درخت اشتقاق حداقل برابر 4 خواهد بود. 

صفحه 188:
۸-۴ پیش قضیه فشار برای زبانهای مستقل از متن قضیه (پیش قضیه فشار برای زبانهای مستقل از متن) فرض کنید که بایک زبان مستقل از متن باشد.یک عدد ‏ وابسته به با وجود داردبطوریکه هر رشته ‎Deb‏ ((۲/)2 می تولند به صورت بوصسمى> نوشته شود كه دارای شرایط زير باشد. (۲ ک(مس بسا ‎t heaghk(v) Heacgs(x)>O)‏ ‎2O.w wxyp €b sly tt)‏ زبان ( (س)به اول است | 60۳ بب)<رامستقل از متن نیست 

صفحه 189:
۸-۵ خصوصیات همبستگی زبانهای مستقل از متن قضیه: مجموعه زبانهای مستقل از متن نسبت به عملیات اجتماع. الحاق و عملگر ‎dius (ep star) yliw‏ هستند. قضیه: مجموعه زبانهای مستقل از متن نسبت به عملیات اشتراک و مکمل بسته فرض كنيد که ‎)٩‏ یک زبان با قاعده و میک زبان مستقل از متن باشد. در این صورت ب!۲٩)‏ مستقل از متن است. 

صفحه 190:
۸-۶ آتاماتای دو پشته ای آتاماتای دو پشته ای 08 دو پشته لىئدارلىساختار (*0,0ه,8, ,لا ©) لست “3,40,0, أ, ,© مشلبه 000008 تكيشته لىمىياشند تلبع ‎O55‏ تفعىاز (( ]نا 1)**(( )۲۱۵)*(( )2*)21) به زیر مجموهه هاییاز (ژ )۷۵ ۲)*(( )لا 1)* © لست حالت عناصر ورودی و عناصر بالای هر دو پشته تعیین می کنند که کدام گذر بایستی انتخاب شود 

صفحه 191:
WY ‏آتاماتای دو پشته ای‎ ۸-۶ مثال 08 دو پسشته لیّت-عریفشده زیر زبان[0 ۷2 ۶ ۲ 2)0بارا می بذيرد. | (سممه :۵ fabio} =D ‏,م2‎ (۲۳,۵, 3 (ه ,ب]) (د ,م2 ۲-0 ‎P]}‏ ,تق ,2۳,۵ (ج)ع ‎Aur, ®)={fe, , } ‏صمة‎ y®)= fle, » J} ‎ 

صفحه 192:
۰ ۰ ۱ فصل نهم:ماشینهای تورینگ 7 اهداف رفتاری: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد: " ماشین تورینگ انواع پذیرش "ماشین های چند شیاره ‎Gla get”‏ تورینگ غیر قطعی [ee eet ee sees 1 

صفحه 193:
فصل نهم : ماشینهای تورینگ ۳ ماشین تورینگ یک ماشین با حالات متناهی است که هر گذر آن عنصری را روی نوار چاپ می کند. ماشین تورینگ یک پنچ تلیی (2,۷0, .6,۶ است که در آن 0 مجموعه متناهی از حالات . یک مجموعه ساب موسوم به الفبای نوارشامل یک عنصر ویژه 0) که نماینگر فاصله خللی است. یک مجموعه از (0)-] موسوم به الفبای ورودی: قیک تابع جزتی از 0 * ۲ به () | © موسوم به تلبع گذر و 0663 یک حللت مشخص به نام حللت ابتدایی مى باشد. صفحه: 194 | 

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

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

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

صفحه 197:
‎٩-۱‏ ماشین تورینگ استاندارد ‎ ‏ماشین تورینگ 200۳۲ با الفبای ورودی ‎fab}‏ یک کپی از رشته ورودی را تولید مى كند. به عبارتی محاسبه ای که با نوار شامل 699 شروع می شود با نوار 948:40) متوقف مى كردد. ‎ 

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

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

صفحه 200:
‎٩-۲‏ ماشین تورینگ به عنوان پذیرنده زبان ‎ ‏مثال: ‏ماشین تورینگ ‏هط ‎39 ‏ره‎ © Aas © ‏سب‎ ‎whe ‏زبان (طالام#(۱00) ۵8 را می پذیرد. ‎ ‎ 

صفحه 201:
‎٩-۳‏ انواع پذیرش در ماشینهای تورینگ ‎ ‎5 ‏در ماشين تورينكى كه براى يذيرش توسط توقف طراعی شده استء يك رشته ورودى يذيرفته مى ,شود اكر محاسبه رشته موجب توقف ماشين شود. ‏فرض کنید که (0,0,)۴, آ,2,) یک ماشین تورینگ با پذیرش توسط توقف باشد. یک رشته 2606*: توسط توقف پذیرفته می شود اگر محاسبه () با ورودی ‏ به طور عادی متوقف شود. ‏گروه کامپیوتر | نظریه زبانها و ماشینها أ صفحهه 202 ‎ ‎ ‎ ‎ ‎ ‎ 

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

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

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

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

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

صفحه 207:
‎٩-۵‏ ماشین تورینگ با نوار دو طرفه ‎ ‏مثال ‏ماشین تورینگ استاندارد) رشته هایی را روی (۲,) می پذیرد که در آن قبل از هر ۶ در صورت وجود. حداقل سه هت وجود داشته باشد. ‎ ‎ 

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

صفحه 209:
‎٩-۶‏ ماشینهای چند نواره ‎ ‏يك ماشين :۷ ه شامل انوار و جلهد مجزا است.حالات و الفباهای یک ماشین چند نواره مشلبه ماشین تورینگ استاندارد است. ماشین به طور همزمان نوارها را می خواند.این کار با اتصال هر یک از هدها به یک ثبّات کنترلی مجزا که حاوی حالت جاری است انجام می شود. ‎ ‎\ ‎i ‎1 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎a ‎ ‎ ‎ ‏نوار ۲ نوار ۲ نوار ۱ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

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

صفحه 211:
‎٩-۶‏ ماشینهای چند نواره ‏مثال: ‎ ‏ماشین تورینگ دونواره ای که دیاگرام حالت آن درزیرآمده ‏است,زبان ((طرعاص انم دا می ‎ee og D2‏ 

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

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

صفحه 214:
فصل دهم طبقه بندی شومسکی ‎oes‏ آشنا خواهد شد: دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خوا ‏* گرامرهای بدون محدودیت " گرامرهای وابسته به متن "آتاماتای خطی محدود "طبقه بندی شومسکی ‎ ‎ 

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

صفحه 216:
۱۰-۱ گرامرهای بدون محدودیت بك كرامر بدون محدوديت يى كرامر جهارتايى(0,3:,6,08) است كه 0 يى مجموعه متناهى از متغيرهاء 3 (الفباايك مجموعه متناهى از عناصر يايانى.) يك مجموعه از قوانين و © يى عنصر مشخص در © می باشد. یک قانون از یک گرامر بدون محدودی به شكل بحب است که در آن (6)0105: و ((6)0108/: مى باشد.فرض می شود که مجموعه های د) و 2 غیر الحاقی هستند. 

صفحه 217:
۱۰-۱ گرامرهای بدون محدودیت كرامرهاى باقاعده و مستئل از مت زیر مجموعه هایی از گرامرهای بدون محدودیت هستند. یک گرامر مستقل ازمتن یک گرامر عبارت است که در سمتچپ هر قانون آن تنها یک متغیر وجود دارد. قوانین یک گرامر باقاعده به یکی از اشکال iA_, aB) iiA, a) iji A) می باشد که ۸,۸6۷ و 82 6 است. 

صفحه 218:
WY ‏گرامرهای بدون محدودیت‎ ۱۰-۱ مثال: گرامر بدون محدودیت زیر با عنصر ابتدایی ظ)زبان ( ۸0" ك1 را توليد مى كند O={©,®,0} fabo}=> G_. Wbria 6-0۱5 ‏م09‎ 

صفحه 219:
۱۰-۱ گرامرهای بدون محدودیت قضیه: فرض کنید که (2,*,)9,)) <9) یک گرامر بدون محدودیت باشد. در اين صورت ())ما یک زبان باز گشتی شمارش پذیر است. قضبه: فرض کنید که با یک زبان باز گشتی شمارش پذیر باشد. در این صورت یک گرامر بدون محدودیت )با رات()) را وجود دارد. قضیه: مجموعه زبانهای بازگشتی شمارش پذیرنسبت به عمل اجتماع. الحاق و عملگر ستاره (20 معط) بسته است. | 220 ‏صفحه؛‎ Meo 

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

صفحه 221:
WY 6 ‏گرامرهای وابسته به متن‎ ۱۰-۲ اگر هر قانون به شکل ‎Nv‏ ‏باشد که ([ )ی و (02ا)6)6نهد و( وجهاگ(ن) اجه است. به قانینی که در شرایط فوق صدق کند یکنواخت() گفته می شود. هر زبان وابسته به متن باز گشتی است. گروه کامپیوتر نظريه.زبانها و ماشینها صفحه, 222 

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

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

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

صفحه 225:
۱۰-۴ طبقه بندی شومسکی گرامرها گرامرهای نوع ». گرامرهای عبارات. گرامرهای بدون محدودیت گرامرهای نوع ۱. زبانهای وابسته به متن آتاماتای خطی محدود گرامرهای وابسته به متنء گرامرهاییگنواخت ae ‏گرامرهای مستقل از متن‎ گرامرهای نوع ۳.گرامرهای باقاعد: گرامرهای خطی چپ گرامرهای خطی راست. آناماتای متناهی غیر قطعی 

صفحه 226:
www.jozve.orgos > دانلود رایگان جزوه و نمونه سوالات امتحانی 9 ‎Oly‏ نامه و مقالات دانشجویی کارشناسی. کارشناسی ارشد و د نمونه سوالات استخدامی پکیج های کامل دانشجویی با تفکیک رشته ها با قیمت های باورنکردنی