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

صفحه 1:


صفحه 2:
عبارات منظم(بافاعده): - ار 2 القبای مورد نظر باشد؛ هر عضو 2 يكك عبارت منظم است - اگر ع عبارت متظم باشد ه هم منظم است - اگر » و #عبارت های منظم باشند8ه هم منظم است ‎a‏ اگر ‏ و معبارت های منظم باشند (2۱8) هم منظم است د اكر : زبان منظمى باشد آنكاه 7 يعنى متمم زبان 4 هم منظم است 

صفحه 3:
مثال ا:عبارت روبرو منظم است یا نه؟ قاط( (|ع) م عم ترضیح: » عضو الفباء است پس منظم است به توجه به بند ۲»» هم منظم است بنا به بند ۳ (۱۵)) هم منظم است پس ‎IB‏ هم منظم است و (ط|ه) ‎a sla‏ ملحق شده است يس عبارت '(6|2"» منظم است يس بستار ستاره آن هم كه همان عبارت 1 است منظم است. زبان منظم:زبانی را منظم گویند اگر بتوان برای آن عبارت منظمی پیدا کرد. مثال ا:ثابت كنيد كه زبان هاى زير منظم اند(با بيدا کردن عبارات منظم) 4, )101:001/0001, ۰. ‏-ظ,‎ 0 ‏یز‎ - «> 2 [lengih(w) = 2k e203 = {a,2) عبارت منظم (0*1) تولید كتنده زبان ,1 است عبارت منظم " ((8+ع)(۵+ )) ترلید کننده زبان وا است 

صفحه 4:
ظرم) عط0 < 2 = ‎|length(w)‏ عم عز حل: ابن زبان رشته هائى رأ از '2 شامل مى شود كه طولشان مضربى از سه باشد ‎ath)’‏ جه( + م) - '(23) - '(مؤضد فطف+ فوط موذ + ذ5و+ وذه + ذهه + 2وو) ‏مثال ۴: یک عبارت منظم برای زبان 3 2«مر1< دم < :| "0”ه) -! بنويسيد * جيه "د + " اطمدم "د +" طاااه ”3 - 1 ‏مثال ۵: یک عبارت منظم برای مجم عه (زوج - :«+م| *6'8) بتويسيد. ‏حلء '(اط) مج ماه هم با "إططا(ة دهم)'(هما 

صفحه 5:
آتاماتی متناهی ‎(Dfa)‏ : يكك ماشين متناهی معین یکک 5 تائی به صورت زیر است (22:8.5,.8) ۸۸2 که در آن 9: مجموعه متناهي از وضیعت ه(1۵18٩‏ ها) 3 تابع تغیر حالت به شکل وج و .و م :عضوى از است و 51816 شروع می باشد. : زیر مجموعه ای از 8 است (2 2 8) که مجمو عه وضيعت هاى نهائى مى باشد. مثال۶: 98 زیان زیر رارسم کنید. (لهاءووية , (ل0ا.(ووروىوو)) - ا و - هه رو - طلوواه :3 % - 60 وو -طرة ‎a= 99‏ 31 - (اريق)ة ‎ 

صفحه 6:
مثال ۷ 2۲۸ زیر چه زبانی مي پذيرد. (Os) me © هر زبانی که بتوان آن را با یکک 18۸۵ نشان داد یک زیان منظم است ( به آزای هر زبان منم حداقل ‎DFA LK,‏ موجود است و بالعکس؛ پس نتیجه می گیریم به ازای هر ‎ER DFA‏ عبارت منظم وجود دارد. به ازاى هر زبان یا تمی تران 28۸ پیدا کرد و با می توان بی تهایت 10۸ رسم کرد که آن زبان را بیذیر د. 

صفحه 7:
‎as ols A Ilo‏ زبان 4 »,0 < «: "م) -/ منظم است. ‎ ‎:DFA yl ‏خاصیت‎ ‏9 در 254 از يكك وضيعت با يكك حرف نمى توان به بيش از يكك 9/816 رفت. + در ۳۸ به ازای تمامی حرف الفبء از یک وضیعت بايد خروجى داشته باشيم. ‏+ برچسب یک يال نمی ‎MALE AIS‏ 

صفحه 8:
آتاماتای متناهی نامعین(۳۵): تعریف ما در مورد ۱۳۸ در اکثر موارد شبیه 12۳۸ است با اين تفاوت که 8ج ره لامج :5 تعریف تابع 5 برای 20۳۸ به صورت زیر است. ‎-١‏ برجسب ها در 1۷۳۸ می توانند شامل ۸ هم باشند ‏۲-خروجی تابع در 21۳۸ عضوی از *2 است.می دانیم هر عضوی از 2 یک ‏مجموعه است پس طرف درم ثابع ما می نواند بیش از یکی باشد یعنی ثابع ما می ‏تواند از یک ‎٩0816‏ با مشاهده یک حرف به یش از یکک 90216 برود. ‏۲ چون 2 شامل مجموعه تهی نیز هست» طرف دوم تابع می تواند تهی هم باشد یعنی اينکه ما در یکث 50816 با يكث يا جند از حروف القباء» هیچ خروجی نداریم ‎ 

صفحه 9:
قضيه: (به ازای هر ۱۷۳۸ که یکک زبان را می پذبرده مى توان يكك ‎DFA‏ معادل آن و هم قدرت با آن ساخت که همان زبان را بپذیرد. ‎٩‏ به ازای هر زبان منظم می توان ۱۳۸ رسم کرد و هر 2۳۸ تولید کننده يكك زبان منظم است. ‎0 ‏را با ۱۵ رسم کنید‎ »۱۵( Obj Abo 

صفحه 10:
تبدیل ۱۲۳۸ به ‎DFA‏ مثال: ا: ۱0۴۸ زیر را به 0۴۸ تبدیل کنید. 

صفحه 11:
مثال ۱۱: 1107۸ زیر را به 74 تبدیل کند. 

صفحه 12:


صفحه 13:
‎DEA 4,1, 23 NDFA.NY Jlrs‏ تبدیل كنيد ‎ 

صفحه 14:
لم تزريق: می خواهیم ثابت كتيم زيان ‎cael lite WoL‏ مثل يكك يازى ذو طرقه عمل مى كنيمء ۳ روالی را پیش بگيريم که به ازای هر حرکتمان از طرف حريف به بيروزى برسیم. ثابت کرد ‎aS Seer Obj‏ روال لم تزریق - حریق یک عدد دلخواه از اعداد طیعی مانند « را اتتخاب می کند ما رشته ای دلخواه از ند انتخاب می کنیم که طولش بزرگتر مساوی هه است - حریف رشته انتخایی ما را به سه قسمت 2,۶ تقیم می کند به شرطی که اولن حرکت از طرف حریف» حرکت بعدی اژ طرف ما و الی ... در ن زبان غير منظم است؛ در غیر این صورت نمی توان در مورد منظم یا غیر منظم بود | ‏رد ابا‎ Km ‏اگر بتوانيم ثبت کنیم به ازای ؛ دلخواه دربازه > :> #در اعداد حسابی» رشته وود‎ - در زيان مورد نظر نیست؛ ثابت شده که زیان غیر 

صفحه 15:
مثال ۱۲. ثابت کند زبان (0 <۸ 1-4089 غیر منظم است. حل: با فوض 0< و "۳ه <۷ داریم ۳ حال با درنظر گرفتن عود- با شرایط مسئله داریم . *9-عره- و۵۳۳ -د ‎Vir Gales a gh*§ ogg = ab el‏ Canad plata wa (atte! [nem <i ‏مثال ۱۳. ثابت کنید زبان‎ حل: با فرض 0<برو دعوم حال با در نظر گرفتن عود-۷با شرایط سئله داریم ,یرم رام عبر 4 -«داریم ۳ زور0 < و 

صفحه 16:
‎is jus‏ ثابت كنيد زبان (2 - م +م| “*0*م) -م منظم نيست حل: با فرض 0ح ير و “تامهم -مرداريم ‏ مدز ‎[erect‏ ‏حال با در نظر گرفتن عود -«با شرایط مسئله داریم ‏توس چرس بر ری سور | وی اي اي تس وی مور ,0 مدز ‏مثال۱۶. ثابت کنید ‎ ‏ن (0 <:۱ 07 ) < 2منظم نیست؟ حل,. با فرض ۲<0 و ۷-0۳ داریم مرح ۳ ‏© يا توجه به اين كه طول ,د مربع كامل نيست بس 2 ميد ‎ 

صفحه 17:
مثال ۱۷. ثابت کنید زبان ("(۰,۵) > ۱۳ * ۷«) - ۶منظم نیست؟ حل. با فرض 7<0 و ۷-۰۳۵۳۵۳۵۳ داریم ‎Ja™b™b"a” |>m‏ حال با در نظر گرفتن 2«د-«با شرایط مسئله داریم هچره ره بر مثال۱۸. ثابت کنید زبان (« ۶ »| ”0”8) - 2 منظم نيست؟ حل. با فرض 7-0 و ۰-۰۳۲ داریم صرح هم حال با در نظر گرفتن ##ه -”: با شرايط مستله داريم آل الدع رسيو رمد کافی است/ را به اندازه کافی بزرگ بگیریم تا معادله 1 -*:+جا + © جواب داشته باشد(یک مقدار / وجود دارد که معادله پاسخ داشته باشد به عنوان مثال :+ :2+:-) که در این صورت :۱-7 خواهد شد. 

صفحه 18:
مثال٩۱.‏ آیا زبان (و۷ رس (ضرت)ء و | هرس -2 منظم است؟ ی حل. با فرض 0< ۰ وا”*”مه”م دمر داریم ‎[bm‏ 0۳۵۵۳۳[ حال با در نظر گرفتن عود-« با شایط مسئله داریم not aml ‏و رس بر سای‎ مثال۲۰. بآ زبانی شامل رشته هائی از 2 و 9 است که دارای ‎hud‏ ‏فردی از کاراکتر ط می باشد. عباوت منظم مربوط به اين زبان كدام است(مهندسی کامپیوتر-۷۶) x (alba’by'ba” 4 a'b(ala’ba'by' GB ab"(ab"ab"Y (2 ba" (e|ba"bY 4 @ جواب. گزینه 4 درست است 

صفحه 19:
مثال ۱ ۲. فرض کنید که » و 8 عبارت منظم هستند کدام یک از روابط زیر ممکن است درست نباشند(مهندسی کامپیوتر- 78). ] C@+ B= + ‏"0م‎ 0 le +P =C@ Ba ‏که ۵ 8 جع‎ 0 جواب: گزینه 2 درست است. مثال ۲۲ بستار کدام یک از زبان های زیر مساوی خود زبان است(آزاد-۸۰) ۵ 0 -43ممه| | «ه 0- 42مص| مر (طمت «|ممع 2 1212| ودا, صود-سى, “(طم)اء س ]| مم دم 0 2د نود مود د سر لإطم)ء سم د1 4 در ود مر “إطماء سدسم - 1 © جواب: گزینه 2 درست است. 

صفحه 20:
به نام خدا 

صفحه 21:
مثال ۲۲. کدام یک از گزاره های زیر دست است الف. اگر بل( با و رامنظم باشند, ,ة هم منظم است ب. اگر راد ورامنظم باشند , هم منظم است جواب هیچ کدام. مثال نقض برای الف. ("ثه << , ((فرماع»|)-و1 مثال نقض برای ب. "0 -م«[س)- رط , ‎Ly=faabh}‏ 

صفحه 22:
مثال ۲۴. کدام حالت ماشین مقایل را حالت نهائی قرار دهیم تا این ماشين زبان نآ را بيذيرد. (2 ‎L=f00|n,(w) = 2 +1, n,(w)‏ جواب. رو 

صفحه 23:
مثال ۲۵. یک 774 رسم کنید که ‎2e , N,v) = 2k +1} 463‏ = («) رکف (۵| 0) > 2-0۳۱۳ را بپذیرد. حل : ابتدا 72۸ مربوط به (26 - ۱۷,۵۵ (0|۵) 2-0۱۳6 را رسم می کنیم ۰ 1 ‎NF AN‏ ‎ays‏ سپس 7754 مربوط به (26+1-(6 2 | ‎Lo= Gul we (ad)‏ را رسم می کنیم 

صفحه 24:
مثال26 ماشین متناهی زیر چه زبانی رامی پذیرد. 1 95۳ 0001 ‏جواب:‎ 90 ne 

صفحه 25:
بهینه سازی ۳0۳۸۵: الگور 1- تمامی وضیعت هاقی که در 0۳۸از وضیعت شروع مسیری یرای رسیدن یه آتها ییست» 2-به ازای هر ,و و ره که در 0۴۵ هست زوج مرتب هاى (ر4,,) را ليست مى كنيم تعداد اين غربال برای پیدا کردن وضیعت های ادغام پذیر را شتاسائی کرده و حذف می کنیم. مثل وضیعت وو در ایر وج‌ها 2۶ می باشد 3- از این وضیعت های لیست شده آنهاتی را که یکی از ژوج ها متعلق به وضیعت نهائی و دیگری غير لهائى استء را به عنوان زوج ادغام ناپذیر عط می زد اگر هر دو وضیعت نهاتی باشند Ce gt 4-به ازاى هر ‎ie 5 ee 92 oS) ng)‏ نشده) و به ازاى تمامى حروف القباء: خروجی على ,ب وروا را بروسى مى كنيمء اككر وضيعت رب وره يا يكك حرض الفباء مثلا يه وضيعك هلى 2.4 بروند و اما قبلا تشخيص داده ايم كه وضيعت هاى 25.4 ادغام نابذيرندءتتيجه مى كيريم كه +4 و رك نيز ادغام نايقيرنك]. 6-مرحله 4 را آنقدر تکرا می کلیم تا هیچ زوجی برای تست كردن باقى نماندء و در نهايت زوج مائی که به عنوان ادغام ناپذیر بودن خط نخوده اند" ادغام پذیرند(با توجه یه خاصیت تعدی اد: می شوند). 

صفحه 26:
مثال 28 ۳۸ زیر را بهینه کنید. ۱- در این مرحله چون از وضیعت شروع به تمامی وضیعت ها دسترسی داریم: هيج وضیحی حذف نمی شود. 6 ۲-به تعداد ل وج مرتب داریم که در زیر لیست شده اند. ‎A oy‏ ‎Gos) “Gam Gos ¥‏ 000 فى دوه ۲ مور ور ۷ ‎۷ ‏مور‎ Gnas) ¥ ‏ووه ۷ ‎82 ‎ ‏و ‏و ‏)%.@ ‏وج ‏9 ‏۳- در اين مرحله بایستی زوج مرتب هانی| که یکی از وضیعت های آنها نپائی است؛ به عنوان ‏زج ادغام نا پذیر خط بزیم: که اين کار در مرحله ۲ انجام شده است (آنهاثی که علامت تيكك ‎ ‏خورده اند ‎poe We Ga) EHS‏ دوحالت نهائی هستند) 

صفحه 27:
۴-در این مرحله زوج های باقی مانده‌رابهازای تمامی حروف القباء تست می کنیم (آنهانی که علامت تیک نخورده اند ادغام می شوند) ‎v‏ و ها تهج لس ‎as‏ (ه وال | هچ (ه. و مدر 52538 | * ‎ma ga.)‏ وح قروو ) ‎Maia) Sia)‏ 4 ی ‎aie.‏ 9 2 0-0 )41.8( عه ۳ أرووج (طرب] دود (ه وه ۳ | وج فیم| ,وج یه ۳ كفم دوم ‎|(@a.2) P49‏ \45 > هبو ‎e378 poe) Gt) Naa sa len oa)‏ ‏۵- در این مرحله پا ترجه به اينکه ‎ ‏مرحله ۴ وضیعت های ادغام پذیر مشخص شده اتد(آتهاتی که علامت تیکك تخورده اند) واضح است که وضیست ره با یه و وه با مه ادخام ‏پذیرند و تبدیل به یک وضیمت( گره) می شوند. حال 0۳۸ بهینه را رسم می کنیم ‎ 

صفحه 28:
گرامر ها: گرامر 0 را به صورت 0۲.7.5.۴ تعریف می کنیم که در آن 7 :مجموعه ای متتامی از متفیر ها می باشد 2 ترمینال ها (مجموعه ای متناهی از الفیای زیان) متخيرى از 1 که نشانه شروع می باشد. ۶ : تعدادی ‎alee‏ از قواعد. اتينى كه يدنه اصلى كرامر وا تشكيل مى دهند به صورت برج + نشان داده مى شوتد. كه +دء بر را توليد مى كند. و داريم “0 تت ع سس خم | اع م مثال29. كرامر 0 جه زبانى را توليد می کند. حل: زيان توليدى ه*ه مى ياشد 

صفحه 29:
3 به سیر طی شاده رای تولید یکك رشته در زبان را يكك اث گونیم در حالت کلی اگر ‎wet‏ عبارت زیر را یکت اشتقاق برا ‎Sw‏ برجب ...وميا جب ربلا جب ربلا جد هر ‏مثال30. كرامرى بنويسيد كه زبان 0<م| "6*8 -2 را توليد كند. ‏ع ۳ ‎S> Ab‏ حل: رنه + ور دوش دوم رب ‏مثال 31 براى زبان (ظ,2) 2 ,(7۳ 2-۱00۴۱۱۸6 یک گرامر بنویسید ‎ ‏۲- برای زبان (2 :0 *م*م) -۸ یکك گرامر بنویسید. ‎۳ ‎ ‏ی زبان (()۵(2۵)) - 1 يكك گرامر بنویسید. ‏۴- برای زبان ("(00101)-/ یکت گرامر بتویسید ‎6 ‎ ‎s Sasa S 3 bSb ‏اجب و ‎SS AB‏ ‎Asa |b‏ عاق حدم ‎AdB‏ > & ‎Asabala‏ ‎BaaBlaa‏ ‏4 ج و ‎A BOB0B‏ 14ج و 

صفحه 30:
۸ امه | کج و .مثال 32 برای گرامر ‏ ط|۵8<-4 یکت ماشین متناهی طراحی کنید. ‎BBD‏ .مثال 33 گرا مری بنویسید که زبان تولیدی آن )2.0 ‎BRM |x‏ -( ياشلد .مثال 34 گرامر مربوط یه زیان (0 < :| *0*9**۵) <1 راینویسید. 

صفحه 31:
داشته باشیم. دقت شود محدودیتی برای مکان متفیر در طرف راست وجود ندارد S>aaBea ‎pl Se‏ 4358ر ج28 خخطى مى باشد. ‎A> ceabal A‏ ‏گرامر خطی واست؛ ‎Zi‏ گرا ‏ها رابه توی محدود کشیم که تتها متفیر استفاده ‎ ‏گر در تعریف گرامر طی. ‎oh gio ‏تدای زیت‎ a Page ‎ 

صفحه 32:
کرامر های منظم: كرامرى منظم است كه همه قواعد آن خطلى جب و ياهمه قواعد آن ای راز تراظن نکته: گرامری که تعدادی قانون خطی راست و تعدادی دیگر قانون خحطی چپ داشته باشدء نمی تواند گرامر منظم ‎Cale Jy EU‏ این گرامر یکت گرامر خطی است. نکته: گرامر های منظم تولید کندء زبان های منظم اند. و به ازای هر زبان منظم می توان گرامر منظمی نوشت که آن را تولید کند. متال 35. برای گرامر نظم ‎cS: FEA‏ 10۳۸ رسم کنید. با توجه به سه نکته زیر می توانیم 101۸ معادل را رسم ‎(eS‏ 

صفحه 33:
خواص زبان های منظم: ۱-اگر زیان و ور منظم باشند آنگاه ولا 0:,۸ با « ]14 همگی منظم اند ۲- خانواده زبان های منظم نسبت به تفاضل و معکوس بسته اند. فیسم(هم ریختی) بسته اند انواده زبان های منظم نسبت به عملیات همو مور هم ربختی: Ras ‏قرض‎ ول دو الفباى مختلف باشند تایع ‎Sly Wz;‏ تابع هم فى نامتد. يغنى ‏ تابغى است كه عر رف در ,2 را به یکک رشته در :2 می برد. مثلا به 21 =(a,b},2, = (2.9.7), h(a) = page ,h(d)= p Se داته تایع ۸ رامسی توان بسه 2 نیسز تعسیم داد متظسور بسه ای h(a a.) = Aa h(a). haa € Dy a های یک زبان مانند ,1 تاثیر گا زشته از با زرا یه رت تتی تابع ۷ به جدیدی (با الفبای ,2) تیدیل می کند.به مجموعه رشته های جدید تولید شده؛ هم ریختی ! تحت تابع ۸ گویند. B= (a,b) E. = Cp. ghed = (aah ‏لال لقره‎ > pe ‏وود رف‎ => (aad ) = pepagg (ab) = pogg .W(b) = 99 = 1 = (pag, p09 99) 

صفحه 34:
مثال36. ثابت كنيد (ع,۵.») <ظ ,(**۳۵*0۳ه) ‎ -‏ نامنظم است. برهان خلف: فرض می کنیم / یکک زبان منظم باشد؛ پس تحت هر نوع هم ریختی باید منظم باشد:هم ریختی ۸ را به صورت مقابل تعریف می کنیم ‎h(a) = a,h(b) = a, R(c) = ¢ = 1 = (a"ato™*) = (a%o™}‏ ‎Pumping +25 Gb 1G‏ ثابت شده است که نا منظم است؛ يس فرض غلط بوده است (در امتحان اثبات ۳۳108 نیز لازم است ) ‏مثال 37. ثابت کنید زبان (/*:|/279) -/ یک زبان نامنظم است. ‏پرهان خلف: فرض می کنیم ایک زبان متظم است؛ پس بتا به خواص زبان های متظم 1- 7-2 هم منظم است: از طرفی اه ‏هم منظم استء يس زبيان 79 -6'2001 - اهم بايستى بنايه خواص زبان هاى منظم: مسنظم باشد. که ایسن طور یسست(طبسق قضیه ۳۷۳001۳8) پس خلاف فرض ابت می شود 

صفحه 35:
مثال 38 گرامر های حطی راست و خطی چپ برای بان (22 برد :9۳ - ل Ss Abbb Saad A— Ab| Baa A-aA|bbbB :تسار ‏حطى‎ ‏هب و 2 مج جر‎ | ۸ مثال39. یسک گرامر مستظم برای بان (20 28 - و + ور وم بت و یسید. ‎S —- Ab |D‏ ‎Abb | Ba‏ جا ‎A‏ ‎B - Baa ۱‏ 24 | ها طفص حا ص ‎kaa |‏ = جر مثال۲.40یا اتبات زیر صحیح است؟ چرا؟ زبان های (0۳) - یت و (۳ظ) و2 هر دو باقاعده اند. (8”+) - مطوط نيز باقاعده است. ویرا زبان های باقاعده تحت اتصال بسته اتد. است که (0۳2۳) -وترة ته "ط۳ه زیرا «ها در حوزه 

صفحه 36:
مثال ۴۱. زبان (200> :| "2-0۳9 زبانی است )- منظم ۲ مستقل از متن و نه منظم ۳ _ وابسته به متن و نه مستقل از متن ‎-F‏ بدون محدودیت و نه حساس به متن جواب. گزینه 1 درست استه زبان هاثى كه تعدادى محدود © كراكتر دزن منظم ‎wl‏ 

صفحه 37:
مثال ۴۲. با فرض (۶۱:| ا۵"م) < راو (0< ۱,۱ ۳9ه) - یا کدام گزینه درست است(مهندسی کامپیوترآزاه-۷۹). ‎LU Lob )۱‏ یک زبان منظم نیست. ‏۲ زبان ,1ب یک زبان منظم است. ‏۳ زبان 1 0 ,1 یک زبان منظم نیست. ‏؟) زبان,2 یک زبان منظم نیست. ‏جواب. گزینه 4 درست است. ‏بامستقل از متن و یا منظم است. گزینه یک منظم است. گزینه گزینه دو و سه مستقل از متن است 

صفحه 38:
مثال ۴۳. فرض کنید بة زبان عبارت منظم"» ورآزبان عبارت منظم و و(0< ”| ”05) - و باشد و زبان ۶ از الحاق سه زبان فوق بدست می آید ‎LE55,)‏ - ) کدام گزینه درست است(مهندسی کامپیوتر-۷۹. 2 یک زبان منظم است. ۲ بر یک زبان مستقل از متن است ۳ 2 یک زبان حساس به متن است و مستقل از متن نیست ‎(F‏ هر سه مورذ درست است ‏جواب. گزینه 1 درست است ‏از الحاق (متیتت - ) داریم (0< )2-۳۵۳9 که به صورت **هاست لذا 7 یک زبان منظم است 

صفحه 39:
به نام خدا 

صفحه 40:
آتاماتای پشته ای نامعین (۵00 : ‎FY pax‏ 2 ,6 ,۲,2,۵ 2۳۵ نمایش مي دهند که 0 مجموعه اي متناهی از 9۳ ها 22 الفباي زبان * وضيعت شروع (عضوي از ©) 117 الفباي پشته 2 * متعلق است به و پایین پشته را نشان مي دهد 16 تابع تفیر حالت ‎Qx(T UA)‏ + 0۵06۱2۲ : 4028 .مرتتقعة 6‏ -01,)) + واه ‎ ‎ ‎0 | — © 2 2 ‎ ‎ ‎ ‎ ‎ 

صفحه 41:
مثال 43.آتاماتاي پشته اي طراحي کنید که زبان: ‎1={a’P’ | n> O}‏ زا بیشیود ‏جواب : ‎ ‎ ‎ ‏»را از ورودی‌سی‌خولنيم ‏در ته پشته < قرار دارد ‏12,)ي) مب هرور۵:)6 ‎6:(g, al) )6,11‏ ‎6:(g,b) > (qa)‏ ‎6:(q, b> (q,A)‏ ‎61(GAD— (GB‏ ‎ ‎ ‎ ‎ ‎ 

صفحه 42:
مثال 43.آتاماتاي پشته اي طراحي کنید که زبان: ‎1={a’P’ | n> O}‏ زا بیشیود ‎ ‎ ‎1:(G,.a.9> (GldwIshou sees 7 wiles 2:(g, al) (qd 1 3:(q,B0 > (4,2) = 4:(q,b))— (q,A) 1 B(GAB (G2) * ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 43:
مثال 43:آتاماتاي پشته اي طراحي کنید که زبان: ‎1={a"b’ | n> O}‏ را بپذیرد ‎ ‎ ‎1:(G,.4.3> (Glas cans ] ٠ ‏جواب‎ ‎2:(g,,al)> (gl) Seg = 3:(g,,b1)> (g,A) ۱ 4:(q,b))> (q,A) 51(GA39> (G2 1 ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 44:
مثال 45: 1={wew | we (a|D'} 1:(g% aI (G1 2:1(G BA ( cog Pmt et ‏بالای پشته 0با‎ 3:)6,۵( « )11 با خواندن »بالای پشته 1 قرار می دهیم. ‎4:(q,a0)—> (G10‏ ‎5:(g,b)— (q@,0)‏ با خواندن ع بالای پشته 0 قرار می د: هب 00 ‎6:(g,B0)>‏ ‎71(@c)- (GD) |‏ با خواندن < تغییر وضيعت مى دشي | ‎8:(q,G0) > (go)‏ ‎9:(q, al (q,A)‏ 10:(gq,B0)> (q,A) 11: (G,A,3> (G2 © 

صفحه 45:
متال 46: (1<وور و | رز نج)ع [ a, )6.12 2:(g,al)> (g.1) 3:(g,b1) > (g.19 4:(q,bI)> (q.1) 5:(g, 6) (g,.A) 6:(g,¢1)> (g,A) 7(G,4,2> (G2) 

صفحه 46:
مثال 47: 1:(g,a 3 (q,2 I={a Bc |n=1} 2: )© 3,2 ),2 3: ‏,ه)‎ 8, 2 (G2) ‏جا,»):4‎ 2- (g,12) ‏(لط,):5‎ « ),11 6:(g,cl)> (q,4) 7:(q, Gl) > (q,A) 8:(GA,3> (G2) 

صفحه 47:
مثال 48: 1={n,(W =1,(1) | we (a| BD" 1:(g,a 32> (G12) ‏ط,2:)6‎ 2 (g,02) 3:(g, al) (G19 4:(g,b0)— (q,,00 5:),۵0( ۰ ),( 6:(g,b1) > (q,A) 7(QAID> (Ged 

صفحه 48:
مثال 49: 1={a°b” | m=n, m=2n, m=3n} 1:(g,a2> (q12 2:(qal) (q1) 3:(GaQ> (G11 4:(g,a)> (G11) 5:(g@a3- (g11B 6:(g,al)> (@ 1111 7:(q, BY (q,A) 8:(g,b) > (GA) 9:(G, BD (GA) 10:(q, bY) > (GA) 11: (G,4,9> (G2) © 

صفحه 49:
مثال 50: 1={wwW}> ={a 1:(@,a2— (G12) 2:(G,B2— (q,02) 3:(g,al)> (G1) 4:(q,2a0)—> (G19 5:(@,B0) > (q@,00 6:(q@, BI) (g,0D 73(GAD— (GD 8:(q,A,0) > (g,0) 9:(q.al)— (q,A) 10: ‏(2,ي) + (0 بط ك)‎ 11: ‏ر2رق)‎ 2 (q,2 

صفحه 50:
مثال ا5: «,)۲( + n,(W =n,(W),= =(a| bl 0° 1:(G,a 2 (G12) 2:(G, b> (q12) 3:(G,G2— (q,02) 4:(q,60)> (q,00 5:(q, Gl) > (q,,A) 6:(g,al> (G1) 7:(q,b) > (G1D 8:),۵0( ),2( 9:(q,B0)— (q,A) 10:(G,4,3> (G2 

صفحه 51:
مثال 52: l={a’p""c" |n=1, m=} 1: )©, ‏يه‎ (G12 2:(q,al)> (q19 3:(q, b> (GA) 4:(g,bl)> (q,A) 02,)) +2 باري):5 00,ي) -(0طري):6 ‎7:(q,60)> (GA)‏ ‎8:(g,c0)> (G,A)‏ ‎9:(G,4,2)> (G2)‏ 

صفحه 52:
مثال 53: 1={a™ 7 | ‏0<و‎ 1:(G4aI> (G2 ‏-22رهة,)©):2‎ )©),112 3: )6,۵( « ) 1 4:(q, bl) > (GA) 5:(G, BI) > (G,A) 6:(G, 2,3 (G2) 

صفحه 53:
مثال 54: 1={a'b"c" |n, m=} 1:(@,.a 34> (G12) 2:(g, al) (G1) 3:(g, b) > (g,) 4:(q,b))> (gq) 5:(q,Gl)> (q,A) 6:(g, cl) > (q,A4) 7(@AD> (G2 

صفحه 54:
به نام خدا نظریه زبان ها و ماشین ها 

صفحه 55:
ساده سازي گرامر هاي منظم ‎٩‏ حذف متغیر بازگشتي آغازین 0 حذف از زبان © حذف قوانین بی فایده ‎٩‏ حذف قوانین یکه(واحد) ‏و با زگشتی چپ 

صفحه 56:
حذف متغیر بازگشتی آغازین مثال 55: گرامر زیر را در نظر بگیرید با توجه به قانون اولي متغیر 5 بازگشتي آغازین مي باشد که به شکل زیر حل مي شود. 

صفحه 57:
مثال۵۶: در گرامر زیر متغیر :2 را حذف کنید. S— ABb| AB S~ ABb|Bb|Ab|b|AB|B|A |) Cyaan) 11 0 ۳ B- bBlb تمام شبه جمله هائی که حداقل یکی از اعضای آن جزء متفیر ۸ باشد را داخل جدول قرار می دهیم 

صفحه 58:
حذف قوانین بکه(واحد): ‎ok‏ ی مه را هر قانونی به شکل مر بر یک قالون يكه است ‎S— Aa[B ‏را حذف کنید.‎ BoAlbb ‏مثال ۸۵۷ قوانين يكه كرامر‎ ‏ظاعن مم4‎ ‏باتوجه يه كراف وابستكى تاريم ‎ ‎ 

صفحه 59:
8 | شاه ‎S$‏ ‏مثال۵۸: در گرامر ‏ ۵8| هه د :6 قواعد یکه(واحد/را حذف کنید. ‎B>S|Aa|bB‏ قوالین واحد قوانین غیر واحد ‎BR nee ‏9 گراف وابستگی را برای متفیر هائی که در قواعد واحد ظاهر شده اند رسم می کنیم . ‎ ‏اثرات قواعد واحد از روی مسیر های موجود در گراف وابستگی به دست می آید. ‏۳ج 

صفحه 60:
حذف بازكشتى جب: هر قانونى به شكل هه 4 را قانون باز كشتى حب كويند. كه در أن ۵۷,۸21 برای حذف قانون باز گشتی چپ که معمولا به شکل ۵۵۱۲ ۸ دید ه می شود از ایده زیر استفاده می کنیم : با توجه به عبارت ...0000 ...۵000 + همه > مد ده ملاحظه می شود که گرامر ط|مهج ۵ رشته هائی را تولید می کند که یک « اولشان هست و به دنبال آن به تعداد نامشخص ۸ هست پس کافی است که گرامری پیدا کنیم که همان رشته ها را اجه تولید کند و بازگشتی چپ نباشد. گرامر ‎DUT‏ نتیچه مطلوب را به ما می دهد. 

صفحه 61:
حذف قوانین بی فایده: ر یک اژ این دو خالت.با حذف قالون مربوطه گزامر مثال. در گرامر رشته ای تولید نخواهد شد يعنى بودن و نبودن متفیر ۵ و قانون مربوطه اش هیچ تاثیری روی زیان ندارد و میتوان آنهارا حذف کرد. ‎SoA‏ مثل‌در گرامر,2| ۵ه ۵ هیچ مسیری از وضیعت شروع به متغیر 2 وجود ندارده لذا بودن و ‎B>bA‏ نبودن فانون مربوطه اش هیچ تاثیری بر روی زبان ندارد و می توان آن را حذف كرد شاه حون کت از 5 به طرف هو با استفاده از قانون ۸ه ج- ۵ هیچ اع يا حرفت ازه یه طرف و » * ار ‎Ors‏ & 

صفحه 62:
گرامر های نرمال لففرم نرمال چاسسکی گرامری در این فرم است که همه قواعد آن به یکی از دو صورت (۸,5۰0) 80 لد يا (221 ,۷۲ ع ش) ه «- هباشد(یا ترکیبی از هر دو) ب.فرم نرمال گریباخ گرامری در اين فرم است که همه قواعد آن به شکل 9 ۸ باشد. S— ABa تال ۵8 گرامر 888 <- ۸ را بهفرمنمال چامسکی يبريد ‎BoAc‏ 

صفحه 63:
8 abAB ‎yal SPs fis‏ 2 |93 ج- ۵ را به فرم نرمال چامسکی ببرید. 2 4 8 ‏جواب: ابتدا قاعده ,2و قاعده يکه را حذف می کنیم . ‎ ‏مثالاع. كرامر 88 | داؤداة ج 5 را به فرم نرمال گریباخ ببرید 

صفحه 64:
مثال ۶۲ فرم نرمال گریباخ گرامر 2| تاکن | 850 <- 8 را بنویسید. BE tee Senta ‏كام دوم : حنف لین‎ گام سوم : نوشتن به فرم نهائی گریباخ ‎ee‏ 

صفحه 65:
كام اول : حذف قانون ‎A‏ 1 5 ۱ سر گام سوم :_فرم نهاتی نرمال چامسکی 

صفحه 66:
به نام خدا نظریه زبان ها و ماشین ها 

صفحه 67:
ماشین تورینگ: نوعی آناماتا است که دارای حافظه ای است به شکل نوار که از دو طرف نا محدود است ع هر سلول حافظه می تواند یک علامت را در خود ذخیره کند. ‎guile cyl be‏ دارای یک هد خواندن و نوشتن است ‎ ‏ع بعد از عمل خواندن و یا نوشتن در هر مرحله می تواند یک خانه به طرف را حرکت کند. ‏توار نامتناهى ‏|~ 17771 فمعظ ‎head ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 68:
ماشین تورینک 11 با یک هفت تائی نشان داده می شود به این شکل 9 مجموعه حالات ماشین : الفبای زبان 0 حالت اولیه ماشین ‎pie‏ فیای تور(علامت محدود کردن نار ۶ مجموعه حالات نهانی(زیر مجموعه ای )03( 

صفحه 69:
6 منلا وقتی می نویسیم(10 -د.,0)<- (ه.,8)6منظور مان اين است که اگر در وضیعت 40 هد خواندن و نوشتن بر روی سلولی از نوار قرار كيرد که علامت 4 را مشاهده کند باید به وضیعت 4 تغییر حالت دهد و از همان سلول 4 را حذف کرده و به جای آن را بنویسد و یک خانه به سمت راست حرکت کند. LP ‏مثال.ماشین‎ می پذیرد. جواب. *ظه 

صفحه 70:
مثال. ماشین تورینگی طراحی کنید که زبان 0010 را بپذیرد. 

صفحه 71:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎.]6 ۱6 6 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 72:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎. 6 ۱2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 73:
مثال. ماشین تورینگی طراحی کنید که زبان (1< .7-6 را بپذیرد. 0 ۱ . 6 ۱2 

صفحه 74:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎aa ‎oT ‎. 6 ۱2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 75:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏نو سل ليم ‎ ‎ ‎ 

صفحه 76:


صفحه 77:


صفحه 78:
عبارات منظم(بافاعده): - ار 2 القبای مورد نظر باشد؛ هر عضو 2 يكك عبارت منظم است - اگر ع عبارت متظم باشد ه هم منظم است - اگر » و #عبارت های منظم باشند8ه هم منظم است ‎a‏ اگر ‏ و معبارت های منظم باشند (2۱8) هم منظم است د اكر : زبان منظمى باشد آنكاه 7 يعنى متمم زبان 4 هم منظم است 

صفحه 79:
مثال ا:عبارت روبرو منظم است یا نه؟ قاط( (|ع) م عم ترضیح: » عضو الفباء است پس منظم است به توجه به بند ۲»» هم منظم است بنا به بند ۳ (۱۵)) هم منظم است پس ‎IB‏ هم منظم است و (ط|ه) ‎a sla‏ ملحق شده است يس عبارت '(6|2"» منظم است يس بستار ستاره آن هم كه همان عبارت 1 است منظم است. زبان منظم:زبانی را منظم گویند اگر بتوان برای آن عبارت منظمی پیدا کرد. مثال ا:ثابت كنيد كه زبان هاى زير منظم اند(با بيدا کردن عبارات منظم) 4, )101:001/0001, ۰. ‏-ظ,‎ 0 ‏یز‎ - «> 2 [lengih(w) = 2k e203 = {a,2) عبارت منظم (0*1) تولید كتنده زبان ,1 است عبارت منظم " ((8+ع)(۵+ )) ترلید کننده زبان وا است 

صفحه 80:
ظرم) عط0 < 2 = ‎|length(w)‏ عم عز حل: ابن زبان رشته هائى رأ از '2 شامل مى شود كه طولشان مضربى از سه باشد ‎ath)’‏ جه( + م) - '(23) - '(مؤضد فطف+ فوط موذ + ذ5و+ وذه + ذهه + 2وو) ‏مثال ۴: یک عبارت منظم برای زبان 3 2«مر1< دم < :| "0”ه) -! بنويسيد * جيه "د + " اطمدم "د +" طاااه ”3 - 1 ‏مثال ۵: یک عبارت منظم برای مجم عه (زوج - :«+م| *6'8) بتويسيد. ‏حلء '(اط) مج ماه هم با "إططا(ة دهم)'(هما 

صفحه 81:
آتاماتی متناهی ‎(Dfa)‏ : يكك ماشين متناهی معین یکک 5 تائی به صورت زیر است (22:8.5,.8) ۸۸2 که در آن 9: مجموعه متناهي از وضیعت ه(1۵18٩‏ ها) 3 تابع تغیر حالت به شکل وج و .و م :عضوى از است و 51816 شروع می باشد. : زیر مجموعه ای از 8 است (2 2 8) که مجمو عه وضيعت هاى نهائى مى باشد. مثال۶: 98 زیان زیر رارسم کنید. (لهاءووية , (ل0ا.(ووروىوو)) - ا و - هه رو - طلوواه :3 % - 60 وو -طرة ‎a= 99‏ 31 - (اريق)ة ‎ 

صفحه 82:
مثال ۷ 2۲۸ زیر چه زبانی مي پذيرد. (Os) me © هر زبانی که بتوان آن را با یکک 18۸۵ نشان داد یک زیان منظم است ( به آزای هر زبان منم حداقل ‎DFA LK,‏ موجود است و بالعکس؛ پس نتیجه می گیریم به ازای هر ‎ER DFA‏ عبارت منظم وجود دارد. به ازاى هر زبان یا تمی تران 28۸ پیدا کرد و با می توان بی تهایت 10۸ رسم کرد که آن زبان را بیذیر د. 

صفحه 83:
‎as ols A Ilo‏ زبان 4 »,0 < «: "م) -/ منظم است. ‎ ‎:DFA yl ‏خاصیت‎ ‏9 در 254 از يكك وضيعت با يكك حرف نمى توان به بيش از يكك 9/816 رفت. + در ۳۸ به ازای تمامی حرف الفبء از یک وضیعت بايد خروجى داشته باشيم. ‏+ برچسب یک يال نمی ‎MALE AIS‏ 

صفحه 84:
آتاماتای متناهی نامعین(۳۵): تعریف ما در مورد ۱۳۸ در اکثر موارد شبیه 12۳۸ است با اين تفاوت که 8ج ره لامج :5 تعریف تابع 5 برای 20۳۸ به صورت زیر است. ‎-١‏ برجسب ها در 1۷۳۸ می توانند شامل ۸ هم باشند ‏۲-خروجی تابع در 21۳۸ عضوی از *2 است.می دانیم هر عضوی از 2 یک ‏مجموعه است پس طرف درم ثابع ما می نواند بیش از یکی باشد یعنی ثابع ما می ‏تواند از یک ‎٩0816‏ با مشاهده یک حرف به یش از یکک 90216 برود. ‏۲ چون 2 شامل مجموعه تهی نیز هست» طرف دوم تابع می تواند تهی هم باشد یعنی اينکه ما در یکث 50816 با يكث يا جند از حروف القباء» هیچ خروجی نداریم ‎ 

صفحه 85:
قضيه: (به ازای هر ۱۷۳۸ که یکک زبان را می پذبرده مى توان يكك ‎DFA‏ معادل آن و هم قدرت با آن ساخت که همان زبان را بپذیرد. ‎٩‏ به ازای هر زبان منظم می توان ۱۳۸ رسم کرد و هر 2۳۸ تولید کننده يكك زبان منظم است. ‎0 ‏را با ۱۵ رسم کنید‎ »۱۵( Obj Abo 

صفحه 86:
تبدیل ۱۲۳۸ به ‎DFA‏ مثال: ا: ۱0۴۸ زیر را به 0۴۸ تبدیل کنید. 

صفحه 87:
مثال ۱۱: 1107۸ زیر را به 74 تبدیل کند. 

صفحه 88:


صفحه 89:
‎DEA 4,1, 23 NDFA.NY Jlrs‏ تبدیل كنيد ‎ 

صفحه 90:
لم تزريق: می خواهیم ثابت كتيم زيان ‎cael lite WoL‏ مثل يكك يازى ذو طرقه عمل مى كنيمء ۳ روالی را پیش بگيريم که به ازای هر حرکتمان از طرف حريف به بيروزى برسیم. ثابت کرد ‎aS Seer Obj‏ روال لم تزریق - حریق یک عدد دلخواه از اعداد طیعی مانند « را اتتخاب می کند ما رشته ای دلخواه از ند انتخاب می کنیم که طولش بزرگتر مساوی هه است - حریف رشته انتخایی ما را به سه قسمت 2,۶ تقیم می کند به شرطی که اولن حرکت از طرف حریف» حرکت بعدی اژ طرف ما و الی ... در ن زبان غير منظم است؛ در غیر این صورت نمی توان در مورد منظم یا غیر منظم بود | ‏رد ابا‎ Km ‏اگر بتوانيم ثبت کنیم به ازای ؛ دلخواه دربازه > :> #در اعداد حسابی» رشته وود‎ - در زيان مورد نظر نیست؛ ثابت شده که زیان غیر 

صفحه 91:
مثال ۱۲. ثابت کند زبان (0 <۸ 1-4089 غیر منظم است. حل: با فوض 0< و "۳ه <۷ داریم ۳ حال با درنظر گرفتن عود- با شرایط مسئله داریم . *9-عره- و۵۳۳ -د ‎Vir Gales a gh*§ ogg = ab el‏ Canad plata wa (atte! [nem <i ‏مثال ۱۳. ثابت کنید زبان‎ حل: با فرض 0<برو دعوم حال با در نظر گرفتن عود-۷با شرایط سئله داریم ,یرم رام عبر 4 -«داریم ۳ زور0 < و 

صفحه 92:
‎is jus‏ ثابت كنيد زبان (2 - م +م| “*0*م) -م منظم نيست حل: با فرض 0ح ير و “تامهم -مرداريم ‏ مدز ‎[erect‏ ‏حال با در نظر گرفتن عود -«با شرایط مسئله داریم ‏توس چرس بر ری سور | وی اي اي تس وی مور ,0 مدز ‏مثال۱۶. ثابت کنید ‎ ‏ن (0 <:۱ 07 ) < 2منظم نیست؟ حل,. با فرض ۲<0 و ۷-0۳ داریم مرح ۳ ‏© يا توجه به اين كه طول ,د مربع كامل نيست بس 2 ميد ‎ 

صفحه 93:
مثال ۱۷. ثابت کنید زبان ("(۰,۵) > ۱۳ * ۷«) - ۶منظم نیست؟ حل. با فرض 7<0 و ۷-۰۳۵۳۵۳۵۳ داریم ‎Ja™b™b"a” |>m‏ حال با در نظر گرفتن 2«د-«با شرایط مسئله داریم هچره ره بر مثال۱۸. ثابت کنید زبان (« ۶ »| ”0”8) - 2 منظم نيست؟ حل. با فرض 7-0 و ۰-۰۳۲ داریم صرح هم حال با در نظر گرفتن ##ه -”: با شرايط مستله داريم آل الدع رسيو رمد کافی است/ را به اندازه کافی بزرگ بگیریم تا معادله 1 -*:+جا + © جواب داشته باشد(یک مقدار / وجود دارد که معادله پاسخ داشته باشد به عنوان مثال :+ :2+:-) که در این صورت :۱-7 خواهد شد. 

صفحه 94:
مثال٩۱.‏ آیا زبان (و۷ رس (ضرت)ء و | هرس -2 منظم است؟ ی حل. با فرض 0< ۰ وا”*”مه”م دمر داریم ‎[bm‏ 0۳۵۵۳۳[ حال با در نظر گرفتن عود-« با شایط مسئله داریم not aml ‏و رس بر سای‎ مثال۲۰. بآ زبانی شامل رشته هائی از 2 و 9 است که دارای ‎hud‏ ‏فردی از کاراکتر ط می باشد. عباوت منظم مربوط به اين زبان كدام است(مهندسی کامپیوتر-۷۶) x (alba’by'ba” 4 a'b(ala’ba'by' GB ab"(ab"ab"Y (2 ba" (e|ba"bY 4 @ جواب. گزینه 4 درست است 

صفحه 95:
مثال ۱ ۲. فرض کنید که » و 8 عبارت منظم هستند کدام یک از روابط زیر ممکن است درست نباشند(مهندسی کامپیوتر- 78). ] C@+ B= + ‏"0م‎ 0 le +P =C@ Ba ‏که ۵ 8 جع‎ 0 جواب: گزینه 2 درست است. مثال ۲۲ بستار کدام یک از زبان های زیر مساوی خود زبان است(آزاد-۸۰) ۵ 0 -43ممه| | «ه 0- 42مص| مر (طمت «|ممع 2 1212| ودا, صود-سى, “(طم)اء س ]| مم دم 0 2د نود مود د سر لإطم)ء سم د1 4 در ود مر “إطماء سدسم - 1 © جواب: گزینه 2 درست است. 

صفحه 96:
به نام خدا 

صفحه 97:
مثال ۲۲. کدام یک از گزاره های زیر دست است الف. اگر بل( با و رامنظم باشند, ,ة هم منظم است ب. اگر راد ورامنظم باشند , هم منظم است جواب هیچ کدام. مثال نقض برای الف. ("ثه << , ((فرماع»|)-و1 مثال نقض برای ب. "0 -م«[س)- رط , ‎Ly=faabh}‏ 

صفحه 98:
مثال ۲۴. کدام حالت ماشین مقایل را حالت نهائی قرار دهیم تا این ماشين زبان نآ را بيذيرد. (2 ‎L=f00|n,(w) = 2 +1, n,(w)‏ جواب. رو 

صفحه 99:
مثال ۲۵. یک 774 رسم کنید که ‎2e , N,v) = 2k +1} 463‏ = («) رکف (۵| 0) > 2-0۳۱۳ را بپذیرد. حل : ابتدا 72۸ مربوط به (26 - ۱۷,۵۵ (0|۵) 2-0۱۳6 را رسم می کنیم ۰ 1 ‎NF AN‏ ‎ays‏ سپس 7754 مربوط به (26+1-(6 2 | ‎Lo= Gul we (ad)‏ را رسم می کنیم 

صفحه 100:
مثال26 ماشین متناهی زیر چه زبانی رامی پذیرد. 1 95۳ 0001 ‏جواب:‎ 90 ne 

صفحه 101:
بهینه سازی ۳0۳۸۵: الگور 1- تمامی وضیعت هاقی که در 0۳۸از وضیعت شروع مسیری یرای رسیدن یه آتها ییست» 2-به ازای هر ,و و ره که در 0۴۵ هست زوج مرتب هاى (ر4,,) را ليست مى كنيم تعداد اين غربال برای پیدا کردن وضیعت های ادغام پذیر را شتاسائی کرده و حذف می کنیم. مثل وضیعت وو در ایر وج‌ها 2۶ می باشد 3- از این وضیعت های لیست شده آنهاتی را که یکی از ژوج ها متعلق به وضیعت نهائی و دیگری غير لهائى استء را به عنوان زوج ادغام ناپذیر عط می زد اگر هر دو وضیعت نهاتی باشند Ce gt 4-به ازاى هر ‎ie 5 ee 92 oS) ng)‏ نشده) و به ازاى تمامى حروف القباء: خروجی على ,ب وروا را بروسى مى كنيمء اككر وضيعت رب وره يا يكك حرض الفباء مثلا يه وضيعك هلى 2.4 بروند و اما قبلا تشخيص داده ايم كه وضيعت هاى 25.4 ادغام نابذيرندءتتيجه مى كيريم كه +4 و رك نيز ادغام نايقيرنك]. 6-مرحله 4 را آنقدر تکرا می کلیم تا هیچ زوجی برای تست كردن باقى نماندء و در نهايت زوج مائی که به عنوان ادغام ناپذیر بودن خط نخوده اند" ادغام پذیرند(با توجه یه خاصیت تعدی اد: می شوند). 

صفحه 102:
مثال 28 ۳۸ زیر را بهینه کنید. ۱- در این مرحله چون از وضیعت شروع به تمامی وضیعت ها دسترسی داریم: هيج وضیحی حذف نمی شود. 6 ۲-به تعداد ل وج مرتب داریم که در زیر لیست شده اند. ‎A oy‏ ‎Gos) “Gam Gos ¥‏ 000 فى دوه ۲ مور ور ۷ ‎۷ ‏مور‎ Gnas) ¥ ‏ووه ۷ ‎82 ‎ ‏و ‏و ‏)%.@ ‏وج ‏9 ‏۳- در اين مرحله بایستی زوج مرتب هانی| که یکی از وضیعت های آنها نپائی است؛ به عنوان ‏زج ادغام نا پذیر خط بزیم: که اين کار در مرحله ۲ انجام شده است (آنهاثی که علامت تيكك ‎ ‏خورده اند ‎poe We Ga) EHS‏ دوحالت نهائی هستند) 

صفحه 103:
۴-در این مرحله زوج های باقی مانده‌رابهازای تمامی حروف القباء تست می کنیم (آنهانی که علامت تیک نخورده اند ادغام می شوند) ‎v‏ و ها تهج لس ‎as‏ (ه وال | هچ (ه. و مدر 52538 | * ‎ma ga.)‏ وح قروو ) ‎Maia) Sia)‏ 4 ی ‎aie.‏ 9 2 0-0 )41.8( عه ۳ أرووج (طرب] دود (ه وه ۳ | وج فیم| ,وج یه ۳ كفم دوم ‎|(@a.2) P49‏ \45 > هبو ‎e378 poe) Gt) Naa sa len oa)‏ ‏۵- در این مرحله پا ترجه به اينکه ‎ ‏مرحله ۴ وضیعت های ادغام پذیر مشخص شده اتد(آتهاتی که علامت تیکك تخورده اند) واضح است که وضیست ره با یه و وه با مه ادخام ‏پذیرند و تبدیل به یک وضیمت( گره) می شوند. حال 0۳۸ بهینه را رسم می کنیم ‎ 

صفحه 104:
گرامر ها: گرامر 0 را به صورت 0۲.7.5.۴ تعریف می کنیم که در آن 7 :مجموعه ای متتامی از متفیر ها می باشد 2 ترمینال ها (مجموعه ای متناهی از الفیای زیان) متخيرى از 1 که نشانه شروع می باشد. ۶ : تعدادی ‎alee‏ از قواعد. اتينى كه يدنه اصلى كرامر وا تشكيل مى دهند به صورت برج + نشان داده مى شوتد. كه +دء بر را توليد مى كند. و داريم “0 تت ع سس خم | اع م مثال29. كرامر 0 جه زبانى را توليد می کند. حل: زيان توليدى ه*ه مى ياشد 

صفحه 105:
3 به سیر طی شاده رای تولید یکك رشته در زبان را يكك اث گونیم در حالت کلی اگر ‎wet‏ عبارت زیر را یکت اشتقاق برا ‎Sw‏ برجب ...وميا جب ربلا جب ربلا جد هر ‏مثال30. كرامرى بنويسيد كه زبان 0<م| "6*8 -2 را توليد كند. ‏ع ۳ ‎S> Ab‏ حل: رنه + ور دوش دوم رب ‏مثال 31 براى زبان (ظ,2) 2 ,(7۳ 2-۱00۴۱۱۸6 یک گرامر بنویسید ‎ ‏۲- برای زبان (2 :0 *م*م) -۸ یکك گرامر بنویسید. ‎۳ ‎ ‏ی زبان (()۵(2۵)) - 1 يكك گرامر بنویسید. ‏۴- برای زبان ("(00101)-/ یکت گرامر بتویسید ‎6 ‎ ‎s Sasa S 3 bSb ‏اجب و ‎SS AB‏ ‎Asa |b‏ عاق حدم ‎AdB‏ > & ‎Asabala‏ ‎BaaBlaa‏ ‏4 ج و ‎A BOB0B‏ 14ج و 

صفحه 106:
۸ امه | کج و .مثال 32 برای گرامر ‏ ط|۵8<-4 یکت ماشین متناهی طراحی کنید. ‎BBD‏ .مثال 33 گرا مری بنویسید که زبان تولیدی آن )2.0 ‎BRM |x‏ -( ياشلد .مثال 34 گرامر مربوط یه زیان (0 < :| *0*9**۵) <1 راینویسید. 

صفحه 107:
داشته باشیم. دقت شود محدودیتی برای مکان متفیر در طرف راست وجود ندارد S>aaBea ‎pl Se‏ 4358ر ج28 خخطى مى باشد. ‎A> ceabal A‏ ‏گرامر خطی واست؛ ‎Zi‏ گرا ‏ها رابه توی محدود کشیم که تتها متفیر استفاده ‎ ‏گر در تعریف گرامر طی. ‎oh gio ‏تدای زیت‎ a Page ‎ 

صفحه 108:
کرامر های منظم: كرامرى منظم است كه همه قواعد آن خطلى جب و ياهمه قواعد آن ای راز تراظن نکته: گرامری که تعدادی قانون خطی راست و تعدادی دیگر قانون خحطی چپ داشته باشدء نمی تواند گرامر منظم ‎Cale Jy EU‏ این گرامر یکت گرامر خطی است. نکته: گرامر های منظم تولید کندء زبان های منظم اند. و به ازای هر زبان منظم می توان گرامر منظمی نوشت که آن را تولید کند. متال 35. برای گرامر نظم ‎cS: FEA‏ 10۳۸ رسم کنید. با توجه به سه نکته زیر می توانیم 101۸ معادل را رسم ‎(eS‏ 

صفحه 109:
خواص زبان های منظم: ۱-اگر زیان و ور منظم باشند آنگاه ولا 0:,۸ با « ]14 همگی منظم اند ۲- خانواده زبان های منظم نسبت به تفاضل و معکوس بسته اند. فیسم(هم ریختی) بسته اند انواده زبان های منظم نسبت به عملیات همو مور هم ربختی: Ras ‏قرض‎ ول دو الفباى مختلف باشند تایع ‎Sly Wz;‏ تابع هم فى نامتد. يغنى ‏ تابغى است كه عر رف در ,2 را به یکک رشته در :2 می برد. مثلا به 21 =(a,b},2, = (2.9.7), h(a) = page ,h(d)= p Se داته تایع ۸ رامسی توان بسه 2 نیسز تعسیم داد متظسور بسه ای h(a a.) = Aa h(a). haa € Dy a های یک زبان مانند ,1 تاثیر گا زشته از با زرا یه رت تتی تابع ۷ به جدیدی (با الفبای ,2) تیدیل می کند.به مجموعه رشته های جدید تولید شده؛ هم ریختی ! تحت تابع ۸ گویند. B= (a,b) E. = Cp. ghed = (aah ‏لال لقره‎ > pe ‏وود رف‎ => (aad ) = pepagg (ab) = pogg .W(b) = 99 = 1 = (pag, p09 99) 

صفحه 110:
مثال36. ثابت كنيد (ع,۵.») <ظ ,(**۳۵*0۳ه) ‎ -‏ نامنظم است. برهان خلف: فرض می کنیم / یکک زبان منظم باشد؛ پس تحت هر نوع هم ریختی باید منظم باشد:هم ریختی ۸ را به صورت مقابل تعریف می کنیم ‎h(a) = a,h(b) = a, R(c) = ¢ = 1 = (a"ato™*) = (a%o™}‏ ‎Pumping +25 Gb 1G‏ ثابت شده است که نا منظم است؛ يس فرض غلط بوده است (در امتحان اثبات ۳۳108 نیز لازم است ) ‏مثال 37. ثابت کنید زبان (/*:|/279) -/ یک زبان نامنظم است. ‏پرهان خلف: فرض می کنیم ایک زبان متظم است؛ پس بتا به خواص زبان های متظم 1- 7-2 هم منظم است: از طرفی اه ‏هم منظم استء يس زبيان 79 -6'2001 - اهم بايستى بنايه خواص زبان هاى منظم: مسنظم باشد. که ایسن طور یسست(طبسق قضیه ۳۷۳001۳8) پس خلاف فرض ابت می شود 

صفحه 111:
مثال 38 گرامر های حطی راست و خطی چپ برای بان (22 برد :9۳ - ل Ss Abbb Saad A— Ab| Baa A-aA|bbbB :تسار ‏حطى‎ ‏هب و 2 مج جر‎ | ۸ مثال39. یسک گرامر مستظم برای بان (20 28 - و + ور وم بت و یسید. ‎S —- Ab |D‏ ‎Abb | Ba‏ جا ‎A‏ ‎B - Baa ۱‏ 24 | ها طفص حا ص ‎kaa |‏ = جر مثال۲.40یا اتبات زیر صحیح است؟ چرا؟ زبان های (0۳) - یت و (۳ظ) و2 هر دو باقاعده اند. (8”+) - مطوط نيز باقاعده است. ویرا زبان های باقاعده تحت اتصال بسته اتد. است که (0۳2۳) -وترة ته "ط۳ه زیرا «ها در حوزه 

صفحه 112:
مثال ۴۱. زبان (200> :| "2-0۳9 زبانی است )- منظم ۲ مستقل از متن و نه منظم ۳ _ وابسته به متن و نه مستقل از متن ‎-F‏ بدون محدودیت و نه حساس به متن جواب. گزینه 1 درست استه زبان هاثى كه تعدادى محدود © كراكتر دزن منظم ‎wl‏ 

صفحه 113:
مثال ۴۲. با فرض (۶۱:| ا۵"م) < راو (0< ۱,۱ ۳9ه) - یا کدام گزینه درست است(مهندسی کامپیوترآزاه-۷۹). ‎LU Lob )۱‏ یک زبان منظم نیست. ‏۲ زبان ,1ب یک زبان منظم است. ‏۳ زبان 1 0 ,1 یک زبان منظم نیست. ‏؟) زبان,2 یک زبان منظم نیست. ‏جواب. گزینه 4 درست است. ‏بامستقل از متن و یا منظم است. گزینه یک منظم است. گزینه گزینه دو و سه مستقل از متن است 

صفحه 114:
مثال ۴۳. فرض کنید بة زبان عبارت منظم"» ورآزبان عبارت منظم و و(0< ”| ”05) - و باشد و زبان ۶ از الحاق سه زبان فوق بدست می آید ‎LE55,)‏ - ) کدام گزینه درست است(مهندسی کامپیوتر-۷۹. 2 یک زبان منظم است. ۲ بر یک زبان مستقل از متن است ۳ 2 یک زبان حساس به متن است و مستقل از متن نیست ‎(F‏ هر سه مورذ درست است ‏جواب. گزینه 1 درست است ‏از الحاق (متیتت - ) داریم (0< )2-۳۵۳9 که به صورت **هاست لذا 7 یک زبان منظم است 

صفحه 115:
به نام خدا 

صفحه 116:
آتاماتای پشته ای نامعین (000 : به فرم ( 6,2 ,۵۲,2۵ نمایش مي دهند که © مجموعه اي متناهی از 0 ها 2:_الفباي زیان 8 * وضيعت شروع (عضوي از ©) 1 القباي يشته * متعلق است به و بايين يشته را نشان مي دهد 6: تابع تغير حالت ‎Qx(T UA)‏ .2ن 0»)8 : 1618 ‎examp.‏ -01,)) + واه ‎ ‎ ‎2 | ‏كت‎ © 2 Zz ‎ ‎ ‎ ‎ ‎ 

صفحه 117:
مثال 43.آتاماتاي پشته اي طراحي کنید که زبان: ‎1={a’P’ | n> O}‏ زا بیشیود ‏جواب : ‎ ‎ ‎ ‏»را از ورودی‌سی‌خولنيم ‏در ته پشته < قرار دارد ‏12,)ي) مب هرور۵:)6 ‎6:(g, al) )6,11‏ ‎6:(g,b) > (qa)‏ ‎6:(q, b> (q,A)‏ ‎61(GAD— (GB‏ ‎ ‎ ‎ ‎ ‎ 

صفحه 118:
مثال 43.آتاماتاي پشته اي طراحي کنید که زبان: ‎1={a’P’ | n> O}‏ زا بیشیود ‎ ‎ ‎1:(G,.a.9> (GldwIshou sees 7 wiles 2:(g, al) (qd 1 3:(q,B0 > (4,2) = 4:(q,b))— (q,A) 1 B(GAB (G2) * ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 119:
مثال 43:آتاماتاي پشته اي طراحي کنید که زبان: ‎1={a"b’ | n> O}‏ را بپذیرد ‎ ‎ ‎1:(G,.4.3> (Glas cans ] ٠ ‏جواب‎ ‎2:(g,,al)> (gl) Seg = 3:(g,,b1)> (g,A) ۱ 4:(q,b))> (q,A) 51(GA39> (G2 1 ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 120:
مثال 45: 1={wew | we (a|D'} 1:(g% aI (G1 2:1(G BA ( cog Pmt et ‏بالای پشته 0با‎ 3:)6,۵( « )11 با خواندن »بالای پشته 1 قرار می دهیم. ‎4:(q,a0)—> (G10‏ ‎5:(g,b)— (q@,0)‏ با خواندن ع بالای پشته 0 قرار می د: هب 00 ‎6:(g,B0)>‏ ‎71(@c)- (GD) |‏ با خواندن < تغییر وضيعت مى دشي | ‎8:(q,G0) > (go)‏ ‎9:(q, al (q,A)‏ 10:(gq,B0)> (q,A) 11: (G,A,3> (G2 © 

صفحه 121:
متال 46: (1<وور و | رز نج)ع [ a, )6.12 2:(g,al)> (g.1) 3:(g,b1) > (g.19 4:(q,bI)> (q.1) 5:(g, 6) (g,.A) 6:(g,¢1)> (g,A) 7(G,4,2> (G2) 

صفحه 122:
مثال 47: 1:(g,a 3 (q,2 I={a Bc |n=1} 2: )© 3,2 ),2 3: ‏,ه)‎ 8, 2 (G2) ‏جا,»):4‎ 2- (g,12) ‏(لط,):5‎ « ),11 6:(g,cl)> (q,4) 7:(q, Gl) > (q,A) 8:(GA,3> (G2) 

صفحه 123:
مثال 48: 1={n,(W =1,(1) | we (a| BD" 1:(g,a 32> (G12) ‏ط,2:)6‎ 2 (g,02) 3:(g, al) (G19 4:(g,b0)— (q,,00 5:),۵0( ۰ ),( 6:(g,b1) > (q,A) 7(QAID> (Ged 

صفحه 124:
مثال 49: 1={a°b” | m=n, m=2n, m=3n} 1:(g,a2> (q12 2:(qal) (q1) 3:(GaQ> (G11 4:(g,a)> (G11) 5:(g@a3- (g11B 6:(g,al)> (@ 1111 7:(q, BY (q,A) 8:(g,b) > (GA) 9:(G, BD (GA) 10:(q, bY) > (GA) 11: (G,4,9> (G2) © 

صفحه 125:
مثال 50: 1={wwW}> ={a 1:(@,a2— (G12) 2:(G,B2— (q,02) 3:(g,al)> (G1) 4:(q,2a0)—> (G19 5:(@,B0) > (q@,00 6:(q@, BI) (g,0D 73(GAD— (GD 8:(q,A,0) > (g,0) 9:(q.al)— (q,A) 10: ‏(2,ي) + (0 بط ك)‎ 11: ‏ر2رق)‎ 2 (q,2 

صفحه 126:
مثال ا5: «,)۲( + n,(W =n,(W),= =(a| bl 0° 1:(G,a 2 (G12) 2:(G, b> (q12) 3:(G,G2— (q,02) 4:(q,60)> (q,00 5:(q, Gl) > (q,,A) 6:(g,al> (G1) 7:(q,b) > (G1D 8:),۵0( ),2( 9:(q,B0)— (q,A) 10:(G,4,3> (G2 

صفحه 127:
مثال 52: l={a’p""c" |n=1, m=} 1: )©, ‏يه‎ (G12 2:(q,al)> (q19 3:(q, b> (GA) 4:(g,bl)> (q,A) 02,)) +2 باري):5 00,ي) -(0طري):6 ‎7:(q,60)> (GA)‏ ‎8:(g,c0)> (G,A)‏ ‎9:(G,4,2)> (G2)‏ 

صفحه 128:
مثال 53: 1={a™ 7 | ‏0<و‎ 1:(G4aI> (G2 ‏-22رهة,)©):2‎ )©),112 3: )6,۵( « ) 1 4:(q, bl) > (GA) 5:(G, BI) > (G,A) 6:(G, 2,3 (G2) 

صفحه 129:
مثال 54: 1={a'b"c" |n, m=} 1:(@,.a 34> (G12) 2:(g, al) (G1) 3:(g, b) > (g,) 4:(q,b))> (gq) 5:(q,Gl)> (q,A) 6:(g, cl) > (q,A4) 7(@AD> (G2 

صفحه 130:
به نام خدا نظریه زبان ها و ماشین ها 

صفحه 131:
ساده سازي گرامر هاي منظم ‎٩‏ حذف متغیر بازگشتي آغازین 0 حذف از زبان © حذف قوانین بی فایده ‎٩‏ حذف قوانین یکه(واحد) ‏و با زگشتی چپ 

صفحه 132:
حذف متغیر بازگشتی آغازین مثال 55: گرامر زیر را در نظر بگیرید با توجه به قانون اولي متغیر 5 بازگشتي آغازین مي باشد که به شکل زیر حل مي شود. 

صفحه 133:
مثال۵۶: در گرامر زیر متغیر :2 را حذف کنید. S— ABb| AB S~ ABb|Bb|Ab|b|AB|B|A |) Cyaan) 11 0 ۳ B- bBlb تمام شبه جمله هائی که حداقل یکی از اعضای آن جزء متفیر ۸ باشد را داخل جدول قرار می دهیم 

صفحه 134:
حذف قوانین بکه(واحد): ‎ok‏ ی مه را هر قانونی به شکل مر بر یک قالون يكه است ‎S— Aa[B ‏را حذف کنید.‎ BoAlbb ‏مثال ۸۵۷ قوانين يكه كرامر‎ ‏ظاعن مم4‎ ‏باتوجه يه كراف وابستكى تاريم ‎ ‎ 

صفحه 135:
8 | شاه ‎S$‏ ‏مثال۵۸: در گرامر ‏ ۵8| هه د :6 قواعد یکه(واحد/را حذف کنید. ‎B>S|Aa|bB‏ قوالین واحد قوانین غیر واحد ‎BR nee ‏9 گراف وابستگی را برای متفیر هائی که در قواعد واحد ظاهر شده اند رسم می کنیم . ‎ ‏اثرات قواعد واحد از روی مسیر های موجود در گراف وابستگی به دست می آید. ‏۳ج 

صفحه 136:
حذف بازكشتى جب: هر قانونى به شكل هه 4 را قانون باز كشتى حب كويند. كه در أن ۵۷,۸21 برای حذف قانون باز گشتی چپ که معمولا به شکل ۵۵۱۲ ۸ دید ه می شود از ایده زیر استفاده می کنیم : با توجه به عبارت ...0000 ...۵000 + همه > مد ده ملاحظه می شود که گرامر ط|مهج ۵ رشته هائی را تولید می کند که یک « اولشان هست و به دنبال آن به تعداد نامشخص ۸ هست پس کافی است که گرامری پیدا کنیم که همان رشته ها را اجه تولید کند و بازگشتی چپ نباشد. گرامر ‎DUT‏ نتیچه مطلوب را به ما می دهد. 

صفحه 137:
حذف قوانین بی فایده: ر یک اژ این دو خالت.با حذف قالون مربوطه گزامر مثال. در گرامر رشته ای تولید نخواهد شد يعنى بودن و نبودن متفیر ۵ و قانون مربوطه اش هیچ تاثیری روی زیان ندارد و میتوان آنهارا حذف کرد. ‎SoA‏ مثل‌در گرامر,2| ۵ه ۵ هیچ مسیری از وضیعت شروع به متغیر 2 وجود ندارده لذا بودن و ‎B>bA‏ نبودن فانون مربوطه اش هیچ تاثیری بر روی زبان ندارد و می توان آن را حذف كرد شاه حون کت از 5 به طرف هو با استفاده از قانون ۸ه ج- ۵ هیچ اع يا حرفت ازه یه طرف و » * ار ‎Ors‏ & 

صفحه 138:
گرامر های نرمال لففرم نرمال چاسسکی گرامری در این فرم است که همه قواعد آن به یکی از دو صورت (۸,5۰0) 80 لد يا (221 ,۷۲ ع ش) ه «- هباشد(یا ترکیبی از هر دو) ب.فرم نرمال گریباخ گرامری در اين فرم است که همه قواعد آن به شکل 9 ۸ باشد. S— ABa تال ۵8 گرامر 888 <- ۸ را بهفرمنمال چامسکی يبريد ‎BoAc‏ 

صفحه 139:
8 abAB ‎yal SPs fis‏ 2 |93 ج- ۵ را به فرم نرمال چامسکی ببرید. 2 4 8 ‏جواب: ابتدا قاعده ,2و قاعده يکه را حذف می کنیم . ‎ ‏مثالاع. كرامر 88 | داؤداة ج 5 را به فرم نرمال گریباخ ببرید 

صفحه 140:
مثال ۶۲ فرم نرمال گریباخ گرامر 2| تاکن | 850 <- 8 را بنویسید. BE tee Senta ‏كام دوم : حنف لین‎ گام سوم : نوشتن به فرم نهائی گریباخ ‎ee‏ 

صفحه 141:
كام اول : حذف قانون ‎A‏ 1 5 ۱ سر گام سوم :_فرم نهاتی نرمال چامسکی 

صفحه 142:
به نام خدا نظریه زبان ها و ماشین ها 

صفحه 143:
ماشین تورینگ: نوعی آناماتا است که دارای حافظه ای است به شکل نوار که از دو طرف نا محدود است ع هر سلول حافظه می تواند یک علامت را در خود ذخیره کند. ‎guile cyl be‏ دارای یک هد خواندن و نوشتن است ‎ ‏ع بعد از عمل خواندن و یا نوشتن در هر مرحله می تواند یک خانه به طرف را حرکت کند. ‏توار نامتناهى ‏|~ 17771 فمعظ ‎head ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 144:
ماشین تورینک 11 با یک هفت تائی نشان داده می شود به این شکل 9 مجموعه حالات ماشین : الفبای زبان 0 حالت اولیه ماشین ‎pie‏ فیای تور(علامت محدود کردن نار ۶ مجموعه حالات نهانی(زیر مجموعه ای )03( 

صفحه 145:
6 منلا وقتی می نویسیم(10 -د.,0)<- (ه.,8)6منظور مان اين است که اگر در وضیعت 40 هد خواندن و نوشتن بر روی سلولی از نوار قرار كيرد که علامت 4 را مشاهده کند باید به وضیعت 4 تغییر حالت دهد و از همان سلول 4 را حذف کرده و به جای آن را بنویسد و یک خانه به سمت راست حرکت کند. LP ‏مثال.ماشین‎ می پذیرد. جواب. *ظه 

صفحه 146:
مثال. ماشین تورینگی طراحی کنید که زبان 0010 را بپذیرد. 

صفحه 147:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎.]6 ۱6 6 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 148:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎. 6 ۱2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 149:
مثال. ماشین تورینگی طراحی کنید که زبان (1< .7-6 را بپذیرد. 0 ۱ . 6 ۱2 

صفحه 150:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎aa ‎oT ‎. 6 ۱2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 151:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎99 ‎oT ‎. 6 ۱2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 152:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎Ph ‎oT ‎. 6 ۱2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 153:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎b .]2 2 ۵ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎0 ‎ ‎ ‎ ‎ ‎ 

صفحه 154:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎۳ ‎۱ ‎5 ‎aja|x ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 155:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎۴ ‎5 ‎aja|x ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 156:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎. 6 ۱2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 157:
مثال. ماشین تورینگی طراحی کنید که زبان (1< .")2 را بپذیرد. aa | . | 6 ۱۷ 

صفحه 158:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎۳ 1 ‎8 ‎. | 6 ۱۷ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 159:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‏ان ‎oT ‎. | 6 ۱۷ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 160:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 161:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎۱ ‎oT ‎. | 6 ۱۷ ‎ ‎ ‎ ‎ ‎ ‎ ‎“fp yiy ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 162:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎ad ‎oT ‎. | 6 ۱۷ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 163:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎. | 6 ۱۷ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 164:
مثال. ماشین تورینگی طراحی کنید که زبان (1< .")2 را بپذیرد. a 9 > هلاتق 

صفحه 165:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎oT ‎. ۲ ۷ 1X ‎ ‎ ‎ ‎ ‎ ‎ ‎“fp yiy ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 166:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎۱ ‎oT ‎ ‎ ‎ ‎ ‎ ‎۷۷ ۰ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 167:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 168:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎1 ‎oT ‎. ۲ ۷ 1X ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 169:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎۱ . ۲ ۷ 1X ۵ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎0 ‎ ‎ ‎ ‎ ‎ 

صفحه 170:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎1 ‎oT ‎. ۲ ۷ 1X ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 171:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎Peril ‎oT ‎. ۲ ۷ 1X ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 172:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎Peril ‎oT ‎. ۲ ۷ 1X ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 173:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎x ‎6 ‎oT ‏كو ‎ ‎ ‎ ‎ ‎ ‎۷۷۷ ۰ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 174:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 175:
ثال. ماشین تورینگی طراحی کنید که زبان (1< 2609.8 را بپذیرد. مثال. ماشین تورینگی طراحی Ph . |x |x [x ‘Ne < 

صفحه 176:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎۳ ‎0 ‎< ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 177:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 178:
‎lb Sug guile Ste‏ كنيد که زبان 20 ».*2<)0 را بيذيرد. ‎X |X ۷ ‏د‎ ‎< ‎ ‎ ‎ ‎ ‎ ‎۷۷۷ ۰ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 179:
مثال. دو عدد 1۰7 داده شده اند ماشین تورینگی برای محاسبه :+ طراحی کنید. 

صفحه 180:
متال. چه زبانی توسط ماشین ((:۲)9.ووق,(۲,ظ0:(ظ,0),(وو. و9 رو90)) 77 با توابع تغییر حالت پذیرفته می شود. زبان (1< ,"۱0/۵ (0<م: *فه) <2 را می پذیرد. مثال.یک ماشین تورینگ با حد اکثر سه وضیعت که زبان *(+1)0)0 را قبول می کند طراحی کنید. 

صفحه 181:
مثال. ماشين تورينكى طراحى كنيد كه زيان (06:2)! را بپذیرد. فرض ‎Da {a,b} AS‏ مثال. ماشین تورینگی طراحی کنید که زبان (۱< ۱۳۳2۵۸ 2-۱۵۳ را بيذيرد. فرض کنید (08)-2 

صفحه 182:
مثال. ماشین تورینگی طراحی کنید كه كليه رشته هائى را كه شامل زير رشته 001 باشند را بيذيرد. 

صفحه 183: