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

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

اسلاید 1: نظریه زبانها و ماشینهاتهيه کننده: سیده فاطمه نورانیگروه: کامپيوتردانشگاه پيام نور

اسلاید 2: شناسنامه منبععنوان منبع: نظریه زبانها و ماشینهامترجم: مهندس سید حجت الله جلیلیانتشارات: پژوهشهای فرهنگی(1380)منبع اصلي:Languages & machinesWritten By: Thomas A.Sudkamp

اسلاید 3: جايگاه درس در رشته کامپيوترضرورت اين درس:ضرورت نياز به زبانهای سطح بالاضرورت ترجمه برنامه های نوشته شده با زبان سطح بالا به برنامه به زبان ماشينتنوع زبانهای برنامه نويسی سطح بالادروس پيش نياز:نوع درس:تعدادکل ساعات تدريس:تعداد جلسات تدريس:

اسلاید 4: فصل اول: ریاضیات مقدماتیاهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: مفاهیم نمادگذاری و مفهوم تابع نظریه مجموعه ها مفهوم استقراء ریاضی گراف و انواع آن

اسلاید 5: 1-1 نمادگذارینماد ┌x┐: اشاره به کوچکترین عدد صحیح بزرگتر یا مساوی عدد حقیقی x دارد. ┌-3.7┐=-3 ┌4.5┐= 5 نماد ┌x┐ را جزء صحیح بالای x می نامیم. نماد └x┘: اشاره به بزرگترین عدد صحیح کوچکتر یا مساوی عدد حقیقی x دارد. └-3.7┘=-4 └4.5┘= 4 نماد └x┘ را جزء صحیح پایین x می نامیم.

اسلاید 6: 1-2 توابعتابع f: تشکیل شده از یک متغیر با قاعده و قانون می باشد که به ازاء یک مقدار x ، مقدار منحصر به فردی را به f(x) نسبت می دهد.نمودار یک تابع: مجموعه ای است از کلیه زوجهای مرتب که بوسیله تابع تعیین می شوند.دامنه یک تابع: مجموعه مقادیری است که تابع به ازاء آنها تعریف می شود

اسلاید 7: 1-2 توابعتابع جامع: تابعی که از XبهY یک رابطه دودویی روی X*Y را داراست.تابع جزئی: رابطه بین X*Yاست وقتی که єf [x,y2]و єf [x,y1]تابع یک به یک: تابعی که در آن هر عنصر xبه یک عنصر مجزا در برد تصویر شود.تابع f:X Y پوشاست اگر که برد f کل مجموعهYباشد.

اسلاید 8: 1-3 نظریه مجموعه هانمادهای مجموعه :نماد є به معنای عضویت است. بطوریکه x є X مشخص می کند که x یک عضو یا عنصر مجموعه Xاست.از دو براکت{ } برای تعریف یک مجموعه استفاده می شود. X= { 1,2,3 } مجموعه هایی که تعداد زیاد یا تعداد نامتناهی عضو دارند بایستی به صورت ضمنی تعریف شوند. {n l n=m² for some natural number m}

اسلاید 9: 1-3 نظریه مجموعه هایک مجموعه با اعضایش مشخص می شود.زیر مجموعه: مجموعه Yزیر مجموعهXاست به طوری که Y X اگر هر عضو Y عضوی از X نیز باشد.اگرY یک زیر مجموعه از Xباشد و X≠Yآنگاه به Yیک زیر مجموعه کامل X میگوئیم.

اسلاید 10: 1-3 نظریه مجموعه هااجتماع دو مجموعه به صورت زیر تعریف می شود: XυY = { z l z є X or z є Y}اختلاف دو مجموعه به صورت زیر تعریف می شود:X-Y = { z l z є X and z є Y} مکمل X نسبت به U مجموعه عناصری در U است که در X نمی باشد.

اسلاید 11: 1-4 استقراء ریاضیمفاهیم مورد استفاده در استقراء ریاضیپایه استقراء: عبارت به ازاء n=1(یا هر مقدار اولیه دیگر) درست است.فرض استقراء: عبارت برای هر عدد دلخواه n≥1(یا هر مقدار اولیه دیگر) درست است.گام استقراء: اگر عبارت به ازاء n درست است، آنگاه به ازاء n+1 نیز درست می باشد.

اسلاید 12: 1-4 استقراء ریاضیمثال:برای کلیه اعداد صحیح مثبت نشان می دهیم کهپایه استقراء: برای n=1داریم:فرض استقراء:فرض کنید که برای یک عدد صحیح مثبت دلخواه n داریم:گام استقراء:لازم است که نشان دهیم:

اسلاید 13: 1-5 قضایا و پیش قضایاقضیه در لغت به معنای گفتاری است که صحت آن باید اثبات شود.مثال:برای هر عدد صحیح 0n› داریم: پیش قضیه به عنوان یک قضیه کمکی برای اثبات قضایای دیگر به کار می رود.

اسلاید 14: 1-6 گراف هاv2v1v4v3123456نمایشی از یک گراف:اجزای یک گراف:دایره ها نشانگر گره ها(vertices)خطوط ارتباط گره ها نشانگر لبه (edge)

اسلاید 15: 1-6 گراف هاگراف جهت دار: اگر هر لبه گراف دارای جهت باشد به آن گراف جهت دار(digraph)می گویند.مسیر(path): در یک گراف جهت داربه دنباله ای از گره ها که بین هر گره و گره بعدی یک لبه وجود داشته باشد گفته می شود. گراف وزن دار: اگر به لبه ها مقادیری تخصیص یافته باشدبه آن مقادیر وزن و به آن گراف،گراف وزن دار می گوییم.

اسلاید 16: 1-6 گراف هاچرخه(cycle): به مسیری که از یک گره شروع شده و به خودش باز می گردد گفته می شود.گراف چرخه ای: اگر گرافی شامل یک چرخه باشد به آن گراف چرخه ای گفته می شود.مسیر ساده: مسیری که از از یک گره دو بار عبور نکند.طول(length)یک مسیر در یک گراف وزن دار برابر مجموع وزنهای مسیر است.

اسلاید 17: 1-6 گراف هاگراف بدون جهت: گرافی که لبه های ان هیچ جهتی نداشته باشند.گراف متصل:گرافی بدون جهت که بین هر دو گره دلخواه از آن یک مسیر مشخص وجود داشته باشد.درخت: یک گراف بدون جهت، پیوسته و بدون چرخه است.درخت ریشه دار:درختی که در آن یک گره به عنوان ریشه درخت انتخاب می شود.درخت پوشا برای G: یک زیر گراف متصل است که اولاً شامل همه گره های G بوده و ثانیاً یک درخت باشد.

اسلاید 18: فصل دوم: زبان هااهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: مفاهیم رشته و زبان مشخصات زبان ها مجموعه های با قاعده

اسلاید 19: زبان: یک زبان یک مجموعه از رشته ها روی یک الفبا است.رشته: یک رشته روی یک مجموعه X یک دنباله متناهی از عناصر Y است.الفبای زبان: به مجموعه عناصری که رشته ها از آن ساخته می شوند الفبای زبان گوئیم.رشته تهی: رشته فاقد عنصر را رشته تهی می نامیم که باλ نشان می دهیم.2-1 رشته ها و زبانها

اسلاید 20: 2-1 رشته ها و زبانها*∑ :فرض کنید که {a,b,c} = ∑باشد.عنصر *∑ شامل: λ : طول 0a b c : طول 1aa ab ac ba bb bc ca cb cc : طول 2aaa aab aac aba abb abc aca acb acc : طول3 baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc

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

اسلاید 22: 2-1 رشته ها و زبانهافرض کنید کهvє∑* باشد.الحاق uوv، که به صورت uv نوشته می شودف یک عمل دودویی روی ∑* است که به صورت زیر تعریف می شود: (iپایه: اگر length(v)=0 باشد. آنگاهגּv= و uv=u خواهد بود.(ii گام بازگشت: فرض کنید که v یک رشته با طول length(v)=n›0 باشد. در اینصورت ، به ازای برخی رشته هایw با طول n-1و a є ∑، v=waو در نتیجه uv=(uw)a خواهد بود.

اسلاید 23: 2-1 رشته ها و زبانهامثال:فرض کنید که v=ca , u=ab و w=bb باشد. در این صورت: uv= abca uw= cabb (uv)w=abcabb u(vw)=abcann

اسلاید 24: 2-1 رشته ها و زبانهاقضیه: فرض کنید که u,v,wє∑* باشد.در این صورت (uv)w= u(vw) خواهد بود.

اسلاید 25: 2-1 رشته ها و زبانهامعکوس رشته:فرض کنید که u یک رشته در باشد. معکوس u به صورت زیر تعریف می شود:(i پایه:length(u)=n0 . در این صورت u=λ و خواهد بود.(ii گام بازگشت: اگر length(u)=n›0 باشد، در اینصورت برای برخی رشته های w به طول n-1 و برخی u=wa , aє∑ معکوس رشته برابرخواهد بود:

اسلاید 26: 2-1 رشته ها و زبانهاقضیه: فرض کنید کهє∑* u,v باشد. در این صورت است

اسلاید 27: 2-2 مشخصات متناهی زبانهایک زبان به صورت یک مجموعه از رشته ها روی یک الفبا تعریف شده است.زبان L از رشته هایی روی a,b} { که با یک a شروع شده و طول زوج دارند به صورت زیر تعریف می شود:(i پایه:aa,abєL .(ii گام بازگشت:اگر uєL باشد،آنگاهuaa,uab,uba,ubbєLاست.(iii همبستگی:یک رشتهuєL است اگر آن بتواند با تکرار متناهی از مرحله گام بازگشت از عنصر پایه ای بدست آید.مثال:

اسلاید 28: 2-2 مشخصات متناهی زبانهاالحاق دو زبان X,Y:الحاق زبانهای XوY که به صورت XY نشان می دهیم، زبانXY={uv l uєX and vєY}است.n مرتبه الحاق X با خودش را به صورت X نشان می دهیم. X به صورت λ} { تعریف می شود.n0

اسلاید 29: 2-2 مشخصات متناهی زبانهامثال:فرض کنید که X={a,b,c} و Y= {abb,ba} است. در اینصورت XY= aabb,babb,cabb,aba,bba.cba}גּ{ X =X =X= {a,b,c}X =XX= {aa,ab,ac,ba,bb,bc,ca,cb,cc}X =X X= {aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc} 01223

اسلاید 30: 2-2 مشخصات متناهی زبانهافرض کنید که X یک مجموعه باشد. در این صورت:X* شامل تمامی رشته هایی است که می توانند از عناصر X ساخته شوند. X مجموعه رشته های غیر تهی ایجاد شده از X است.+

اسلاید 31: 2-2 مشخصات متناهی زبانهامثال:زبان L={a,b}*{bb}{a,b}* شامل تمامی رشته های روی {a,b } است که دارای زیر رشته bb می باشد. الحاق مجموعه {bb} ما را وجود bb در هر رشته از L مطمئن می سازد. مجموعه های {a,b} * مشخص می کنند که هر تعدادی aوb با هر ترتیبی می تواند بعد یا قبل از bb قرار بگیرند.

اسلاید 32: 2-3 عبارات و مجموعه های با قاعده مجموعه باقاعده: مجموعه ای با قاعده است که بتواند با استفاده از عملیات اجتماع، الحاق و kleen star از مجموعه تهی، مجموعه شامل رشته تهی و اعضای مجموعه الفبا تولید شود.

اسلاید 33: 2-3 عبارات و مجموعه های با قاعده فرض کنید که∑ یک الفبا باشد. مجموعه های باقاعده روی∑ به صورت بازگشتی زیر تعریف می شوند:(i پایه: Ø، λو {a}،به ازاء هر aє∑، مجموعه هایی باقاعده روی∑ هستند.(ii گام بازگشت: فرض کنید که Xو Y مجموعه هایی باقاعده روی∑ باشند. مجموعه هایXY,XυY و X* مجموعه هایی باقاعده روی∑ هستند. (iii همبستگی: X یک مجموعه باقاعده روی∑ است اگر آن بتواند با تکرار متناهی از مرحله گام بازگشت از عناصر پایه ای بدست آید.

اسلاید 34: 2-3 عبارات و مجموعه های با قاعده مثال:مجموعه رشته هایی که با یک a شروع شده و شامل حداقل یک b هستند، مجموعه ای با قاعده روی {a,b} است.

اسلاید 35: 2-3 عبارات و مجموعه های با قاعده عبارت با قاعده:فرض کنید که∑ یک الفبا است. عبارات باقاعده روی∑ به صورت بازگشتی زیر تعریف می شوند:(i پایه:Ø، λ و {a}،به ازاء هر aє∑، عباراتی باقاعده روی∑ هستند.(ii گام بازگشت: فرض کنید که u,v عباراتی باقاعده روی∑ باشند.در این صورت عبارات uv, uυvو u* نیز عباراتی باقاعده روی∑ هستند. (iii همبستگی: u یک عبارت باقاعده روی∑ است اگر آن بتواند با تکرار متناهی از مرحله گام بازگشت از عناصر پایه ای بدست آید.

اسلاید 36: 2-3 عبارات و مجموعه های با قاعده مثالهایی از عبارات با قاعده:(i a*ba*b(aυb)*(ii (aυb)*ba*ba*(iii (aυb)*b(aυb)*b(aυb)*یک عبارت با قاعده برای مجموعه رشته هایی که شامل زیر رشته aa نمی باشند،عبارت با قاعده a*(ab )*υb*(ab )*a ،ممکن است شامل هیچ پیشوندی از bها نباشد. تمامی aها بایستی حداقل به یک b ختم شده و یا عنصر پایانی رشته باشند. ++

اسلاید 37: فصل سوم: گرامرهای مستقل از متناهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: گرامرها و زبان های مستقل از متن اشتقاق و درخت آن گرامرهای قاعده

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

اسلاید 39: 3-1 گرامرها و زبانهای مستقل از متنگرامر مستقل از متن:یک گرامر مستقل از متن، یک چهارتایی (V,∑,P,S) است که درآن Vیک مجموعه متناهی از متغیرها،∑(الفبا)یک مجموعه متناهی از عناصر پایانی،P یک مجموعه متناهی از قوانین و S یک عنصر مشخص از V به نام عنصر ابتدایی است.فرض می شود که Vو∑مجموعه هایی غیر الحاقی هستند.

اسلاید 40: 3-1 گرامرها و زبانهای مستقل از متنقانون:یک قانون که به آن یک تولید نیز می گویند، عضوی از مجموعه V×(Vυ∑)*است. قانون [A,w] معمولاً به صورت نوشته می شود.

اسلاید 41: 3-1 گرامرها و زبانهای مستقل از متننکته:از آنجائیکه رشته تهی در(Vυ∑)* وجود دارد، لذا λ نیز ممکن است در سمت راست یک قانون قرار گیرد.نکته:قانونی به شکل به قانون تهی یا قانون لامبدا موسوم است.

اسلاید 42: 3-1 گرامرها و زبانهای مستقل از متنمرحله اصلی در فرایند تولید، تبدیل یک رشته با استفاده از یک قانون است.مثال:بکارگیری قانون A w برای متغیر Aدر uAv رشته uwvرا تولید می کندکه آن را به صورت نشان می دهیم.

اسلاید 43: 3-1 گرامرها و زبانهای مستقل از متنیک رشته w از v قابل اشتقاق است اگر یک دنباله متناهی از قوانین که v را به w تبدیل می کنند وجود داشته باشد.قابلیت اشتقاق w ازv را به صورت نشان می دهیم.

اسلاید 44: 3-1 گرامرها و زبانهای مستقل از متنمجموعه رشته های قابل اشتقاق از v:فرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن و V є(Vυ∑)* باشد. مجموعه رشته های قابل اشتقاق از v به صورت بازگشتی زیر تعریف می شود:(i پایه:v از v قابل اشتقاق است.(ii گام بازگشت: اگر u=xAy از v قابل اشتقاق بوده و A wєP باشد، آنگاه xwy از v قابل اشتقاق خواهد بود.(iii همبستگی: تمامی رشته های ایجاد شده از v با بکارگیری تعداد متناهی گام بازگشت از v قابل اشتقاقند.

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

اسلاید 46: 3-1 گرامرها و زبانهای مستقل از متنفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد.فرم جمله ای:یک رشته w є(Vυ∑)* یک فرم جمله ای از G است اگر یک اشتقاق S * w وجود داشته باشد.جمله:یک رشته wє∑* یک جمله از G است اگر یک اشتقاق* w S درG وجود داشته باشد.زبان G: که آنرا با L(G)نشان می دهند،مجموعه زیراست.

اسلاید 47: 3-1 گرامرها و زبانهای مستقل از متنفرم جمله ای ها، رشته هایی قابل اشتقاق ازعنصرابتدایی گرامرهستند .جملات فرم جمله ایهایی هستند که تنها شامل عناصر پایانی می باشند.به مجموعه ای از رشته ها روی یک مجموعه الفبا(∑) زبان مستقل از متن گفته می شود.

اسلاید 48: 3-1 گرامرها و زبانهای مستقل از متنیک قانون A به شکل را بازگشت مستقیم می نامیم.به یک اشتقاق که A در w نیست،بازگشت غیر مستقیم می گوییم.

اسلاید 49: 3-1 گرامرها و زبانهای مستقل از متنمثال: گرامر G که یک زبان شامل رشته هایی با تعداد مثبت و زوجی از aها را تولید می کند.G=(V,∑,P,S)V={S,A}∑ ={a,b}P: S A AA AAA l bA l Ab l a

اسلاید 50: 3-1 گرامرها و زبانهای مستقل از متناشتقاق راست و چپ:اشتقاق چپ:هر قانونی که به اشتقاق اولین متغیر سمت چپ رشته می پردازد.اشتقاق راست: به قوانینی که راست ترین متغیر موجود در هر رشته را تبدیل می کنند.

اسلاید 51: 3-1 گرامرها و زبانهای مستقل از متندرخت اشتقاق:فرض کنید که G=(V,∑,P,S)یک گرامر مستقل از متن بوده وS * wیک اشتقاق باشد.درخت اشتقاق S * w یک درخت مرتب شده است که به صورت زیر ساخته می شود:

اسلاید 52: 3-1 گرامرها و زبانهای مستقل از متن(i درخت اشتقاق (DT)را با ریشه Sمقداردهی کنید.(ii اگر با قانونی در اشتقاق بکار رفته برای رشته uAv باشد، آنگاه را به عنوان فرزندان A به درخت اضافه کنید.(iiiاگر قانونی در اشتقاق بکار رغته برای رشته uAv باشد، آنگاه را به عنوان تنها فرزندA به درخت اضافه کنید.

اسلاید 53: 3-1 گرامرها و زبانهای مستقل از متنترتیب برگهادرختاشتقاقSSSAAaAaAAAabAAAabaAAَababAAababaAababaaSAASAAaSAAAAAaAASAAAAabAabAASAAAAabaAASAAAAabaAabAASAAAAabaaAabAASAAAAabA,Aa,Aa,,A,A,Aa,b,AAAa,b,a,A,Aa,b,a,b,A,Aa,b,a,b,a,Aa,b,a,b,a,a

اسلاید 54: 3-1 گرامرها و زبانهای مستقل از متنnپیش قضیه:فرض کنید که G یک گرامر مستقل از متن بوده وv w یک اشتقاق در G باشد که V می تواند به صورت با w نوشته شود.در این صورت رشته های pє(∑υV)*ای وجود دارند که در شرایط زیر صدق می کنند:(i (ii(iii

اسلاید 55: 3-2مثالهایی از گرامرها و زبان هافرض کنید که G گرامری با قوانین زیر باشد:S aSa l aBaB bB l aدر این صورت L(G)={a b a l n >0 , m >0} خواهد بود. nnm

اسلاید 56: 3-2مثالهایی از گرامرها و زبان هایک رشته w متقارن است اگر w=w باشد.R{a b c d l n ≥0 , m >0}n2nmmS aSdd l AA bAc l bcزبانگرامرزبانگرامرمجموعه متقارن روی {a,b} S aSa l bSb

اسلاید 57: 3-2مثالهایی از گرامرها و زبان هازبانگرامرגּS abS cB lB bB l b ({ab) (cb ) l n≥0, m >0} nnnmnزبانگرامر{a b l 0≤n≤m≤2n}nmגּ G: S aSb l aSbb l

اسلاید 58: 3-3گرامرهای باقاعدهگرامر باقاعده: یک گرامر مستقل از متن است که هر قانون آن دارای یکی از حالات زیر است:(i A a(ii λ A (iii A aBکه در آن A,B є V و aє∑ می باشد. یک زبان با قاعده است اگر بتواند توسط یک گرامر با قاعده تولید شود.

اسلاید 59: 3-3گرامرهای باقاعدهمثال: گرامر بی قاعده گرامر با قاعده S aB l G: S abSA lB bS l bA A Aa l A aA l גּגּגּגּ

اسلاید 60: 3-4مروری بر گرامرها و زبان هازبانگرامرL={a b l n>0}2n3mG: S AASB l AABA a B bbb قانون به کار رفته اشتقاقn-1n-1n-1S (AA) SB (AA) B (aa) B (aa) (bbb) =a bnnnnnn2n3mS AASBS AABA aB bbbاثبات:

اسلاید 61: 3-4مروری بر گرامرها و زبان هازبانگرامرL(G)=a*(a*ba*ba*)*גּS aS l bB lB aB l bS l bCC aC lגּ{a b c d l n ≥m >0}n2nmmG:S aSdd l A A bAc l bcزبانگرامرمثال:

اسلاید 62: فصل چهارم: مقدمه ای بر پارسر هااهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: اشتقاق چپ و ابهام گراف یک گرامر پارسر ها

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

اسلاید 64: 4-1 اشتقاقهای چپ و ابهامزبان یک گرامر: مجموعه ای از رشته های پایانی است که می توانند به هر روشی از عنصر ابتدائی مشتق شوند.قضیه:فرض کنیدG=(V,∑,P,S) یک گرامر مستقل از متن باشد. یک رشته w در L(G) است اگر و تنها اگر یک اشتقاق چپ w از S وجود داشته باشد.

اسلاید 65: 4-1 اشتقاقهای چپ و ابهامیک گرامر مستقل از متن G مبهم (ambiguous) است، اگر یک رشته w L(G) وجود داشته باشد بطوریکه با دو اشتقاق چپ مجزا تولید شود. مثال: گرامر G: S aS l Sa l aG یک گرامر مبهم است زیرا رشته aa دارای دو اشتقاق چپ مجزا است.S aS S Sa aa aa

اسلاید 66: 4-1 اشتقاقهای چپ و ابهامابهام از ویژگیهای گرامر است ، نه از ویژگیهای زبان.مثال:گرامر G: S bS l Sb l aزبان G ،b*ab* است.اشتقاقهای چپ زیر ابهام G را نشان می دهند.S bS S Sb bSb bSb bab bab

اسلاید 67: 4-1 اشتقاقهای چپ و ابهامنکته: یک گرامر غیر مبهم است اگر در هر مرحله از یک اشتقاق چپ تنها یک قانون وجود داشته باشد که ما را به اشتقاق یک رشته کامل هدایت کند. S aSb l A l A aAbb l abbλ

اسلاید 68: 4-2 گراف یک گرامراشتقاقهای چپ یک گرامر مستقل از متن G می تواند به وسیله یک گراف جهت دار g(G) (گراف چپ گرامرG)نشان داده شود. گره های گراف ، فرم جمله ای های چپ گرامر هستند.یک فرم جمله ای چپ، رشته ای است که می تواند بوسیله یک اشتقاق چپ از عنصر ابتدایی نتیجه شود.

اسلاید 69: 4-2 گراف یک گرامرفرض کنید که G=(V,∑,P,S)یک گرامر مستقل از متن باشد. گراف چپ گرامرG،g(G)،گراف جهت دار(N,P,A) است که گره ها و کمانهای آن به صورت زیر تعریف می شوند:(i(ii A={[v,w,r]єN×N×P l v w by application of rule r} L

اسلاید 70: 4-2 گراف یک گرامرگرامر مستقل از متن دارای تعداد محدودی قانون می باشد، لذا هر گره نیز دارای تعداد محدودی فرزند خواهد بود، به گرافی با این ویژگی، گراف متناهی محلی گوییم.

اسلاید 71: 4-2 گراف یک گرامردو استراتژی مختلف برای پیدا کردن یک اشتقاق w از S وجود دارد:1- پارسر بالا به پائین: جستجواز گره S شروع شده و تا یافتن رشته w ادامه می یابد.2- پارسر پائین به بالا:شروع جستجو با رشته پایانی w و ادامه آن تا یافتن عنصر ابتدایی است.

اسلاید 72: الگوریتم های تجزیهالگوریتم های تجزیه:1- الگوریتم تجزیه بالا به پایین سطحی2- الگوریتم تجزیه بالا به پایین عمقی3- الگوریتم تجزیه پایین به بالای سطحی4- الگوریتم تجزیه پایین به بالای عمقی

اسلاید 73: 4-3 پارسر بالا به پایین سطحینکته:یک پارسر تعیین می کند که آیا یک رشته ورودی از قوانین گرامر قابل اشتقاق است یا خیر.پارسر بالا به پایین: اشتقاقهایی را با استفاده از قوانین روی متغیرهای چپ یک فرم جمله ای ایجاد می کند.

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

اسلاید 75: 4-3 پارسر بالا به پایین عمقیامکان انتخاب نادرست یک آینده دو مشکل در پارسرهای عمقی ایجاد می کند:1- اول اینکه الگوریتم بایستی بتواند یک انتخاب نادرست را تشخیص بدهد.2- دوم اینکه پارسر پس از تشخیص یک انتخاب نادرست به عقب برگشته و اشتقاق دیگری را تولید نماید.

اسلاید 76: 4-3 پارسر بالا به پایین عمقییک اشتقاق از (b+b)AE: V= {S,A,T} = {b,+,(,)} P: 1- S A 2- A T 3- A T+T 4- T b 5- T (A)گرامر:

اسلاید 77: 4-3 پارسر بالا به پایین عمقی اشتقاق پشته[S,1][A,2][T,5][(A),3][(A+T),2][(T+T),4][(b+T),4]S A T (A) (A+T) (T+T) (b+T) (b+b)

اسلاید 78: 4-5 تجزیه پایین به بالاهنگامی که ساختار جستجو با رشته P آغاز می شود، الگوریتم حاصل یک پارسر پایین به بالا خواهد بود.مثال:قانون کاهش(b)+b(T)+b(A)BT+bA+bA+TAST bT TT (A)A TT bA A+TS A

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

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

اسلاید 81: فصل پنجم: فرمهای نرمالیک فرم نرمال با اعمال محدودیتهایی روی شکل قوانین موجود در گرامر تعریف می شود. گرامرها در یک فرم نرمال، مجموعه کاملی از زبانهای مستقل از متن را تولید می کنند. فرم های نرمال برای گرامرهای مستقل از متن:1- فرم های نرمال شومسکی2- فرم های نرمال گریباش

اسلاید 82: 5-1 حذف قوانین لامبداءفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد.یک گرامر G=(V,∑,P,S) وجود دارد به طوریکه(i L(G)=L(G)(ii قوانین P به شکل A w می باشند که A є V و w є ((V-{S})υ∑)* است.

اسلاید 83: 5-1 حذف قوانین لامبداءمثال:عنصر ابتدایی گرامر G بازگشتی است. G:S aS l AB l AC A aA l B bB l bS C cC lגּגּG:S S S aS l AB l AC A aA l B bB l bS C cC lגּגּ

اسلاید 84: 5-1 حذف قوانین لامبداءبه متغیری که بتواند رشته تهی را مشتق کند، میرا (nullable) گفته می شود.یک گرامر بدون متغیرهای لامبداء به گرامر غیر انقباضی (noncontracting) موسوم است.

اسلاید 85: 5-1 حذف قوانین لامبداءفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد. الگوریتم زیر مجموعه ای از متغیرهای میرایG را تولید می کند.الگوریتم : ورودی: یک گرامر مستقل از متن G=(V,∑,P,S) 1. NULL : = {A l A єP}2. repeat 2.1 PREV := NULL 2.2 for each variable A є V do If there is an A rule A w and w є PREV* then NULL : = NULL υ{A}until NULL = PREVגּ

اسلاید 86: 5-1 حذف قوانین لامبداءفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد. اگر A * w باشد، آنگاه گرامر G=(V,∑,P {A w},S) معادل با G است.Gنکته: یک گرامر با قوانین لامبداء غیر انقباضی نیست.

اسلاید 87: 5-1 حذف قوانین لامبداءفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن GL=(VL,∑,PL,SL) وجود دارد بطوریکه (i L(G L)=L(G)(ii SL یک متغیر بازگشتی نیست.(iii A در PL وجود دارد اگر و فقط اگر єL(G) و A=SL باشد.גּλ

اسلاید 88: 5-2 حذف قوانین زنجیره ایبکارگیری یک قانون نه تنها طول رشته مشتق شده را افزایش نمی دهد، بلکه عناصر پایانی اضافی نیز تولید می کند. در واقع، این قانون یک متغیر رامجدداً نامگذاری می کند. قوانینی به این شکل به قوانین زنجیره ای موسومند.

اسلاید 89: 5-2 حذف قوانین زنجیره ایقوانین زیر را در نظر بگیرید:A aA l a l BB bB l b l CA aA l a l bB l b l CB bB l b l Cقانون زنجیره ای مشخص می کند که هر رشته قابل اشتقاق از B، ازA نیز قابل اشتقاق است. بکارگیری یک قانون زنجیره ای، یک مرحلهاضافی است که می تواند با افزودن قوانین A حذف شود. قانون زنجیره ای را می توان با سه قانون A به صورت زیر جایگزین نمود:

اسلاید 90: 5-2 حذف قوانین زنجیره ایپیش قضیهفرض کنید که G یک گرامر مستقل از متن غیر انقباضی حقیقی است. الگوریتم زیر مجموعه متغیرهای قابل اشتقاق از A را تنها با استفاده از قوانین زنجیره ای تولید می کند.

اسلاید 91: 5-2 حذف قوانین زنجیره ایایجاد مجموعه CHAIN(A)ورودی: یک گرامر مستقل از متن غیر انقباضی حقیقی G=(V,∑,P,S) 1. CHAIN(A) : = {A}2. PREV : = ø3. repeat 3.1. NEW : = CHAIN(A)-PREV 3.2. PREV : = CHAIN(A) 3.3. for each variable BєNEW do for each rule B C do CHAIN(A) : = CHAIN(A)υ{C}until CHAIN(A) = PREV

اسلاید 92: 5-2 حذف قوانین زنجیره ایقضیهفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن GC وجود دارد بطوریکه(i L(G C)=L(G)(ii GC هیچ قانون زنجیره ای نداشته باشد.

اسلاید 93: 5-3 عناصر غیر مفیدعناصر مفید و عناصر غیر مفید:فرض کنید G یک گرامر مستقل از متن است. در این صورت یک عنصر x (V) مفید(useful) است اگر یک اشتقاق S * uxw * w وجود داشته باشد بطوری که u,vє(Vυ∑)* و wє∑ * باشد. به عنصری که مفید نیست، غیر مفید(useless) گفته می شود.GG

اسلاید 94: 5-3 عناصر غیر مفیدیک عنصر پایانی مفید است اگر در یک رشته از زبان G رخ دهد. یک متغیر مفید است اگر در یک اشتقاق که با یک عنصر ابتدائی شروع شده و یک رشته پایانی را تولید می کند، رخ دهد.دو شرط بایستی برای یک متغیر مفید برقرار باشد:1- متغیر بتواند در یک فرم جمله ای گرامررخ دهد یا به عبارتی در یک رشته قابل اشتقاق از S وجود داشته باشد.2- اشتقاق یک رشته پایانی از ان متغیر وجود داشته باشد.به متغیری که در یک فرم جمله ای رخ می دهد،قابل دسترس (reachable) از S گفته می شود.

اسلاید 95: قضیهفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن است. الگوریتمی برای ایجاد یک گرامر مستقل از متن GT=(VT,∑T,PT,S) وجود دارد بطوریکه (i L(G T)=L(G)(ii هر متغیر در GT یک رشته پایانی در GT را مشتق کند.5-3 عناصر غیر مفید

اسلاید 96: 5-3 عناصر غیر مفیدمثال:G: S AC l BS l B A aA l aF B CF l b C cC l D D aD l BD l C E aA l BSA F bB l bحذف متغیرهای غیر مفیدVT = {S,A,B,E,F}∑T = {a,b}PT = S BS l B A aA l aF B b E aA l BSA F bB l b

اسلاید 97: 5-3 عناصر غیر مفیدپیش قضیهفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن است. الگوریتم زیر مجموعه ای کامل از متغیرهای قابل دسترس از S را تولید می کند.

اسلاید 98: 5-3 عناصر غیر مفیدایجاد متغیرهای قابل دسترس ورودی: یک گرامر مستقل از متن G=(V,∑,P,S) 1. REACH := {S}2. PREV : = ø3. repeat 3.1 NEW := REACH – PREV 3.2 PREV := REACH 3.3 for each variable AєNEW do for each rule A W do add all variables in w to REACHuntil REACH = PREV

اسلاید 99: 5-3 عناصر غیر مفیدقضیهفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد. الگوریتمی برای ایجاد یک گرامر مستقل از متن GU وجود دارد بطوریکه(i L(G U)=L(G)(ii GU هیچ عنصر غیر مفیدی ندارد.

اسلاید 100: 5-3 عناصر غیر مفیدمثالگرامر زیر را در نظر بگیرید.G : S a l ABA bلزوم بکارگیری تبدیلات به یک ترتیب معین با بکارگیری فرآیندهای هر دو ترتیب و مقایسه نتایج آنها مشخص می شود.

اسلاید 101: 5-3 عناصر غیر مفید1- حذف عناصر غیر قابل دسترس:S a ABA b2-حذف متغیرهایی که رشته پایانی را تولید نمی کنند:S aA b1-حذف متغیرهایی که رشته پایانی راتولید نمی کنند:S aA b 2- حذف عناصر غیر قابل دسترس:S aمتغیر A و عنصر پایانی B غیر مفید هستند.

اسلاید 102: 5-4 فرم نرمال شومسکیفرم نرمال شومسکی:یک گرامر مستقل از متن G=(V,∑,P,S)در فرم نرمال شومسکی است اگر هر قانون دارای یکی از حالتهای زیر باشد:(i A BC(ii A a (iii S که B,CєV-{S} است. גּ

اسلاید 103: 5-4 فرم نرمال شومسکیدرخت اشتقاق در یک گرامر به فرم شومسکی یک درخت دودویی است.قضیهفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن باشد. الگوریتمی وجود دارد که یک گرامر G=(V,∑,P,S) در فرم نرمال شومسکی و معادل با G ایجاد کند.

اسلاید 104: 5-4 فرم نرمال شومسکیمثالG: S aABC l a A aA l a B bcB l bc C cC l cG : S AT1 a A a T1 AT2 T2 BC A AA a B BT3 BC T3 CB C CC c B b C cفرم شومسکی

اسلاید 105: 5-4 فرم نرمال شومسکیS A+T l b l (A)A A+T l b l (A)T b l (A)S AY l b l LZZ AR A AY l b l LZT b l LZY PTP +L (R )Y بیانگر+Tاست.Z بیانگر A) است.L بیانگر( است.R بیانگر) است.P بیانگر+ است.مثال:

اسلاید 106: 5-5 حذف بازگشت چپ مستقیمبرای اجتناب از وقوع یک تجزیه پایان ناپذیر بایستی قوانین بازگشت چپ را از گرامر حذف کنیم.قانون بازگشت چپ مستقیم A A+T در گرامر AE محاسبات پایان ناپذیری را در هر الگوریتم سطحی و عمقی امکانپذیر می سازد.

اسلاید 107: 5-5 حذف بازگشت چپ مستقیممثال:1)A aA l bA bZ l bZ aZ l a2)A Aa l Ab l b l cA bZ l cZ l b l cZ aZ l bZ l a l b

اسلاید 108: پیش قضیهفرض کنید که G=(V,∑,P,S) یک گرامر مستقل از متن بوده و AєV یک متغیر بازگشتی چپ مستقیم در G باشد. الگوریتمی وجود دارد که یک گرامر معادل G=(V,∑,P,S) ایجاد نماید بطوریکه A یک متغیر بازگشتی چپ مستقیم نباشد.5-5 حذف بازگشت چپ مستقیم

اسلاید 109: 5-6 فرم نرمال گریباشایجاد پیشوندهای پایانی کشف بن بست ها را توسط الگوریتم های تجزیه بالا به پایین تسهیل می کند. یک فرم نرمال ( نظیر فرم گریباش) طوری ارائه می شود که بکارگیری هر قانون بتواند طول پیشوند پایانی رشته مشتق شده را افزایش دهد که این امر ما را از وجود بازگشت چپ، چه مستقیم و چه غیر مستقیم، مطمئن می سازد.

اسلاید 110: 5-6 فرم نرمال گریباشفرم نرمال گریباش:یک گرامر مستقل از متن G=(V,∑,P,S)در فرم نرمال گریباش است اگر هر قانون دارای یکی از حالتهای زیر باشد:(i S (ii A a (iii A aA1A2…An کهaє∑ و برای هر i=1,2,….n ، AiєV-{S} است. λ

اسلاید 111: 5-6 فرم نرمال گریباشمثال:S SaB l aBגּB bB l S ST l SA l AB l aS ST l SA l AB l aB CB l bT ABA aC bS aBZT l aZT l aBT l aT l aBZA l aZA l aBA l aA l aB l aS aBZ l aZ l aB l aB bB l bT aBA aC bZ aBZ l aZ l aB l a فرم شومسکی فرم گریباش

اسلاید 112: 5-6 فرم نرمال گریباشمثال: اشتقاق چپ رشته abaab فرم نرمال گریباش فرم نرمال شومسکی GSaBSaBaBSaBaBaBaBaBaBaBabBaBaBaBabaBaBaBabaaBaBabaabBaBabaabaBabaabaSSSASTASATAABATAaBATA abATAabaTAabaABAabaaBAabaabAabaabaSaBZAabZAabaZAabaaBAabaabAabaaba

اسلاید 113: فصل ششم: آتاماتای متناهیاهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: آتاماتای قطعی دیاگرام حالتآتاماتای غیر قطعی

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

اسلاید 115: 6-2 آتاماتای متناهی قطعی(Finite-State Machine)یک آتاماتای متناهی قطعی (DFA) به صورت پنج تایی M=(Q,∑,∂,q0,F) بیان می شود که در آن Q یک مجموعه متناهی از حالات،∑ یک مجموعه متناهی موسوم به الفبا،q0єQ مبین حالت ابتدایی،F زیرمجموعه ای از Q شامل حالات نهایی یا حالات پذیرش، و∂ یک تابع جامع از Q×∑ به Q که به تابع گذر موسوم است می باشد.

اسلاید 116: 6-2 آتاماتای متناهی قطعی(Finite-State Machine)حالات یک DFA بیانگر وضعیت داخلی ماشین هستند.ورودی، یک دنباله متناهی از الفبای ∑ است.یک محاسبه آتاماتا شامل اجرای مجموعه ای از دستورالعملها است. اجرای یک دستورالعمل حالت ماشین را تغییر می دهد.هدف از محاسبه یک آتاماتا تعیین قابلیت پذیرش یک رشته ورودی است.

اسلاید 117: 6-2 آتاماتای متناهی قطعی(Finite-State Machine)فرض کنید که M=(Q,∑,∂,q0,F) یک DFA باشد. زبان M، که با L(M) نشان داده می شود، مجموعه ای از رشته ها در *∑ است که توسط M پذیرفته می شود.

اسلاید 118: 6-2 آتاماتای متناهی قطعی(Finite-State Machine)مثال:DFA M یک مجموعه از رشته هایی را روی {a,b} می پذیرد که شامل زیر رشته bb هستند؛ بدینصورت که L(M)=(aυb)*bb(aυb)* است.M : Q={q0,q1.q2}∑= {a,b}F={q2}

اسلاید 119: 6-2 آتاماتای متناهی قطعی(Finite-State Machine)تابع گذر در یک جدول به نام جدول گذر داده شده است.حالات به صورت عمودی و الفبا به صورت افقی در جدول قرار گرفته اند. عملکرد آتاماتا در حالت qi با ورودی a ، با یافتن نقطه مشترک سطر متناظر qi و ستون متناظر a تعیین می شود.∂ a bq0 q0 q1q1 q0 q1q2 q2 q2

اسلاید 120: 6-2 آتاماتای متناهی قطعی(Finite-State Machine)تابع گذر توسعه یافته ∂ از یک DFA با تابع گذر ∂ تابعی است از Q×∑* به Q که به صورت بازگشتی زیر روی طول رشته ورودی تعریف می شود:(i پایه: length(w)=0 . در این صورت גּ w= و ∂(qi, )=qi است. length(w)=1 . در این صورت a w=(برای برخی aє∑) و ∂(qi,a )= ∂ (qi,a) است. (ii مرحله بازگشت: فرض کنید length(w)>1 باشد.آنگاهw=ua و ∂ (∂(qi,u),a) (qi,ua)= ∂ خواهد بود.^גּ^^^^

اسلاید 121: 6-3 دیاگرامهای حالت و مثالهادیاگرام حالت یک DFA، یک گراف جهت دار بر چسب شده است که گره های آن مبین حالات ماشین بوده و کمانهایش از تابع گذر بدست آمده است.مثال:q0q1q2aaa,bbb>

اسلاید 122: 6-3 دیاگرامهای حالت دیاگرام حالت یک M=(Q,∑,∂,q0,F) DFA یک گراف بر چسب دار G با شرایط زیر است:(i گره های G عناصر Q هستند.(ii برچسب کمانهای G عناصر∑ هستند.(iii q0 گره ابتدایی با فرم نمایشی است.(iv F مجموعه گره های پذیرش است که هرگره پذیرش با مشخص می شود.(v یک کمان از گره qiبهqj با برچسب a وجود دارد اگر ∂(qi,a)=qj باشد.(vi برای هر گرهqiوعنصر є∑aدقیقاً یکی کمان با برچسب a از qi خارج می شود.>

اسلاید 123: 6-3 دیاگرامهای حالت و مثالهامحاسبه DFA با ورودی ababb و مسیر متناظر آن در دیاگرام به صورت زیر است: مسیر محاسبه[ q0,ababb][q0,babb][q1,abb][q0, bb][q1,b][q2, ] גּ┴┴┴┴┴q0,q0,q1,q0,q1,q2رشتهababbقابل پذیرش است زیرا در حالت پایانی q2متوقف شده است.

اسلاید 124: 6-3 دیاگرامهای حالت و مثالهامثال:رشته هایی روی {a,b} که شامل زیر رشته bb نمی باشند.q0q1q4q5q2q3>aaaaabbbbba,b

اسلاید 125: 6-3 دیاگرامهای حالت و مثالهامثال:DFA M زبانی شامل رشته ها روی {a,b} با تعداد زوجی aو تعداد فردی b را می پذیرد.[ea,eb][ea,ob][oa,eb][oa,ob]>aaaabbbbM:

اسلاید 126: 6-3 دیاگرامهای حالت و مثالهادیاگرام حالت زیر DFA غیر کاملی را تعریف می کند که عبارت (ab)*c را می پذیرد.q1q2abcq0>

اسلاید 127: 6-4 آتاماتای متناهی غیر قطعییک آتاماتای متناهی غیر قطعی یک پنچ تایی M=(Q,∑,∂,q0,F) است که در آن Q یک مجموعه متناهی از حالات،∑ یک مجموعه متناهی موسوم به الفبا،q0єQ مبین حالت ابتدایی،F زیرمجموعه ای از Q شامل حالات نهایی یا حالات پذیرش، و∂ یک تابع جامع از Q×∑ به P(Q) می باشد.

اسلاید 128: 6-4 آتاماتای متناهی غیر قطعیزبان NFA M که با L(M) نشان داده می شود، مجموعه ای از رشته های پذیرفته شده به وسیله M است. بدین صورت کهL(M)={w l there is a comutation [q0,w] *[qi, ] with qiєF}┴גּ

اسلاید 129: 6-4 آتاماتای متناهی غیر قطعیدیاگرام حالت یک M=(Q,∑,∂,q0,F) NFA یک گراف جهت دار G با شرایط زیر است:(i گره های G عناصرQ هستند.(ii برچسب کمانهای G عناصر ∑ هستند.(iii q0 گره ابتدایی است.(iv f مجموعه گره های پذیش است.(v یک کمان از گره qi به qj با برچسب a وجود دارداگر ∂(qi,a)=qj باشد.

اسلاید 130: 6-4 آتاماتای متناهی غیر قطعیمثال:دیاگرامهای حالت M1وM2 آتاماتای متناهی را تعریف می کنند که (aυb)*bb(aυb)* را می پذیرند.aq0q1q2M1: >abba,ba,bq0q1q2M2: >bba,b

اسلاید 131: 6-4 آتاماتای متناهی غیر قطعیq0q1q3q2q4>abba,baa,ba,bNFA:

اسلاید 132: 6-5 گذرهای لامبدایک آتاماتای متناهی غیر قطعی با گذرهلی لامبدا یک پنچ تایی M=(Q,∑,∂,q0,F) مشابه NFA است با این تفاوت که ∂ تابعی از Q×(∑υ{ }) به P(Q) می باشد.λ

اسلاید 133: 6-5 گذرهای لامبدامثال:می خواهیم از گذرهای لامبدا برای ایجاد یک גּNFA- که رشته هایی به طول زوج را بروی {a,b} می پذیرد، استفاده کنیم. ابتدا دیاگرام حالت را برای ماشینی که رشته های به طول دو را می پذیرد تشکیل می دهیم.q0q1q2>a,ba,b

اسلاید 134: برای پذیرش رشته تهی ، یک کمان لامبدا از q0 به q2 اضافه می شود. رشته هایی به طول زوج مثبت با استفاده از کمان لامبدایq2 به q0 برای تکرار دنباله q2,q1,q0 پذیرفته می شوند.6-5 گذرهای لامبداq0q1q2>a,ba,bגּגּ

اسلاید 135: 6-6 حذف غیر قطعیتهمبستگی لامبدای یک حالت qi ، که با –closure(qi)גּ نشان داده می شود، به صورت بازگشتی زیر تعریف می شود.(i پایه: –closure(qi)גּ є qi (ii مرحله بازگشت: فرض کنید که qj یک عنصر از –closure(qi)גּ باشد.اگر qkє∂(qj, ) باشد، آنگاه –closure(qj)גּ є qk است. (iii همبستگی: qj در –closure(qi)גּ است اگر بتواند با یک تکرار متناهی ازمرحله بازگشت بدست آید.גּ

اسلاید 136: 6-6 حذف غیر قطعیتمثال:جدولهای گذر برای تابع گذر∂ و تابع گذر ورودی t یک גּNFA- به همراه دیاگرام M ارائه شده است. زبان M،a+c*b* می باشد.q0q1q2M: >aaabcגּ

اسلاید 137: 6-6 حذف غیر قطعیت∂q0q1q2a{q1,q2,q3}øøcøø{q2}bø{q1}øגּøø{q1}tq0q1q2a{q1,q2,q3}øøcøø{q1,q2}bø{q1}{q1}

اسلاید 138: 6-6 حذف غیر قطعیتمثال:ماشینهای M1وM2 به ترتیب a(ba)*وa* را می پذیرند. q1q2q3 M1: >M2: >aba

اسلاید 139: 6-6 حذف غیر قطعیتبا ایجاد یک حالت ابتدایی جدید و اتصال آن به حالات ابتدایی ماشینهای اصلی با استفاده از گذر لامبدا می توانیم یک NFA- M بسازیم که a(ba)*υa* را بپذیرد.גּq0q1q3M: >aabגּq2גּ

اسلاید 140: 6-6 حذف غیر قطعیتتابع گذر ورودی M به صورت زیر است:tq0q1q2q3a{q2,q3}{q1}ø{q3}bø ø{q1}ø

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

اسلاید 142: فصل هفتم : زبانها و مجموعه های با قاعدهگرامرها به عنوان تولید کننده های زبان، و آتاماتای متناهی به عنوان پذیرنده های زبان معرفی شده اند.هر آتاماتای متناهی با الفبای ∑ یک زبان روی ∑ را می پذیرد.خانواده زبانهای پذیرفته شده توسط آتاماتا دقیقاً شامل مجموعه های باقاعده روی ∑ است.

اسلاید 143: 7-1 آتاماتای متناهی و مجموعه های با قاعدهمجموعه های با قاعده با استفاده از عملیات اجتماع، الحاق و عملگر ستاره(kleen star) از عناصر پایه ای ایجاد می شوند.

اسلاید 144: فرض کنید که F ,S و F ,S به ترتیب حالات ابتدایی و پایانی M1وM2 باشند.حالات ابتدایی و پایانی ماشین را با SوF نشان می دهیم. زبان L(M1)υL(M2) توسط ماشین زیر پزیرفته می شود:M1M1M2M2SSSFFFM1M2M1M2M1M2גּ>גּגּגּ7-1 آتاماتای متناهی و مجموعه های با قاعده

اسلاید 145: 7-2 گراف عباراتگراف عبارات: یک گراف جهت دار است که برچسب کمانهای آن عبارات با قاعده می باشند. یک گراف عبارت، همانند یک دیاگرام حالت، شامل یک گره ابتدایی مجزا و یک مجموعه از گره های پذیرش است.

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

اسلاید 147: 7-2 گراف عباراتمثال:13bbcc>این گراف عبارت b*ccb* را می پذیرد.

اسلاید 148: 7-2 گراف عباراتقضیه kleen :یک زبان L توسط یک DFA با الفبای∑ پذیرفته می شود اگر و تنها اگر L یک مجموعه با قاده روی∑ باشد.

اسلاید 149: 7-3 گرامرهای باقاعده و آتاماتای متناهیبه یک گرامر مستقل از متن با قاعده گوییم اگر هر قانون آن به شکل A aB، A a یا גּ A باشد.زبان a b توسط گرامر G تولید می شود:+ +G: S aS l aA A bA l bSAZM: >abba

اسلاید 150: 7-3 گرامرهای باقاعده و آتاماتای متناهییک محاسبه در یک آتاماتا با رشته ورودی شروع شده، چپ ترین عنصر را به ترتیب پردازش کرده و پس از تحلیل کامل رشته متوقف می شود.از طرف دیگر، تولید با عنصر ابتدایی گرامر شروع شده و عناصر پایانی را به پیشوند فرم جمله ای مشتق شده اضافه می کند.

اسلاید 151: 7-3 گرامرهای باقاعده و آتاماتای متناهیمثال:گرامر زیر زبان a*(aυb ) را تولید نموده و NFA M آن را می پذیرد.+G: S aS l Bb a B bB lגּSBZM: >aabb

اسلاید 152: 7-3 گرامرهای باقاعده و آتاماتای متناهیمثال:S aA l bBA aS l bCB bS l aC l C aB l bAגּSABC>abbaaabb

اسلاید 153: 7-4 ویژگیهای همبستگی زبانهای باقاعدهیک زبان روی الفبای با قاعده است ، اگر آن:(i یک مجموعه (عبارت) باقاعده روی∑(ii پذیرفته شده توسط NFA,DFA یا גּ NFA-(iii تولید شده توسط یک گرامر با قاعده باشد.

اسلاید 154: 7-4 ویژگیهای همبستگی زبانهای باقاعدهقضیه اگر L1 و L2 دو زبان با قاعده باشند، آنگاه L1L2 , L1υL2 وL1* نیز زبانهای باقاعده خواهند بود.زبانهای باقاعده نسبت به عمل مکمل بسته هستند. اگر L روی الفبای∑ با قاعده باشد، آنگاه L=∑*-L نیز با قاعده خواهند بود._

اسلاید 155: 7-4 ویژگیهای همبستگی زبانهای باقاعدهقضیهاگر Lیک زبان با قاعده باشد، آنگاه L نیز باقاعده است._قضیهاگرL1 وL2 زبانهایی باقاعده باشند، آنگاه L1∩L2 نیز باقاعده است.

اسلاید 156: 7-5 یک زبان بی قاعدهزبانهای بی قاعده:زبان {a b l i≥0} با قاعده نیست.i iفرض کنید که L یک زبان روی∑ باشد. اگر رشته های є∑ ui و(i≥0)viє∑* با uiviєLو uivjєL برای i≠j وجود داشته باشد، آنگاه L یک زبان باقاعده نیست.مثلاً مجموعه L شامل رشته های متقارن روی {a,b} ،باقاعده نیست./

اسلاید 157: 7-5 یک زبان بی قاعدهنکته:اشتراک دو زبان باقاعده یک زبان با قاعده تولید می کند.نکته:اشتراک یک زبان با قاعده با یک زبان مستقل از متن باقاعده نیست.قضیه:فرض کنید که L1 یک زبان با قاعده و L2 یک زبان مستقل از متن باشد. زبان L1∩L2 لزوماً باقاعده نیست.

اسلاید 158: 7-6 پیش قضیه فشار برای زبانهای باقاعدهفرض کنید که G دیاگرام حالت یک DFA با k حالت بوده و p یک مسیر به طول k یا بیشتر باشد. در این صورت مسیر p را می توان به زیر مسیرهای r,p وs تجزیه نمود بطوریکه p=qrs و length(qr)≤k بوده و r یک چرخه باشد.

اسلاید 159: 7-6 پیش قضیه فشار برای زبانهای باقاعدهقضیه:فرض کنید که L یک زبان با قاعده است که توسط یک DFA M باk حالت پذیرفته می شود و فرض کنید که z هر رشته موجود در L با length(z)≤k باشد.در این صورت z می تواند به صورت uwv نوشته شود بطوریکه length(uv)≤k ، length(v)>0 و به ازای هر i≥0 ، uv w є L باشد.iپیش قضیه فشار ابزار قدرتمندی برای اثبات بی قاعدگی زبانها است.

اسلاید 160: 7-6 پیش قضیه فشار برای زبانهای باقاعدهمثال:برای اینکه نشان دهیم با قاعده نیست بایستی رشته ای را با طول مناسب در L پیدا کنیم که هیچ رشته فشردنی برای آن وجود نداشته باشد.فرض می کنیم که L باقاعده است. K را تعداد مشخص شده توسط پیش قضیه فشار در نظر می گیریم. با فرض اینکه z رشته a b است ، هر تجزیه uvw از z که در شرایط پیش قضیه فشار صدق می کند بایستی به شکل زیر باشدکه i+j≤k و j>0 است. {a b l i≥0}i ik k

اسلاید 161: 7-6 پیش قضیه فشار برای زبانهای باقاعدهu v wa a a bijk-i-jkفشار هر زیر رشته به این شکل،uv w=a b a a b =a a b را تولید می کند که در زبان L وجود ندارد. از آنجائیکه zєL هیچ تجزیه ای ندارد که در شرایط پیش قضیه صدق کند، لذا نتیجه می گیریم که زبان L با قاعده نیست.ijjk-i-jkkkj2

اسلاید 162: 7-6 پیش قضیه فشار برای زبانهای باقاعدهقضیه:فرض کنید که M یک DFA با k حالت باشد.(i L(M) اگر وتنها اگر M یک رشته z با length(z)>kرا بپذیرد.(ii L(M) به تعداد نا متناهی عضو دارد اگر وتنها اگر M یک رشته z با length(z)<2k را بپذیرد.فرض کنید که M1 و M2 دو DFA باشند. یک روال تصمیم گیری برای تعیین هم ارزی M1 و M2 وجود دارد.

اسلاید 163: فصل هشتم: آتاماتای Pushdownاهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: آتاماتای Pushdown انواع PDAآتاماتای دو پشته ایبهینه سازی DFA

اسلاید 164: زبانهای باقاعده به عنوان زبانهایی تولید شده توسط گرامرهای باقاعده و پذیرفته شده توسط آتاماتای متناهی شناخته می شود.یک آتاماتای pushdown ، یک ماشین با حالات متناهی همراه با یک حافظه پشته ای خارجی است . افزودن یک پشته به آتاماتا قابلیت مدیریت حافظه LIFO را فراهم می کند.LIFO : Last-In , First-Out

اسلاید 165: 8-1 آتاماتای pushdownیک آتاماتای pushdown ، یک شش تایی (Q,∑,Γ,∂,q0,F) است که Q یک مجموعه متناهی از حالات ، ∑ یک مجموعه متناهی موسوم به الفبای ورودی، Γ یک مجموعه متناهی موسوم به الفبای پشته،q0 حالت ابتدایی ، F Q یک مجموعه متناهی از حالات پایانی، یک تابع گذر از Q×(∑υ{ }) ×(Γ υ{ }) به زیر مجموعه های Q× (Γ υ{ }) می باشد.∩_λλλ

اسلاید 166: 8-1 آتاماتای pushdownیک PDA دارای دو الفباست:1-الفبای ورودی ∑که رشته های ورودی را شکل می دهد.2- الفبای Γ که عناصر آن ممکن است روی پشته ذخیره شوند.

اسلاید 167: 8-1 آتاماتای pushdownنکتهعناصر الفبای پشته ای را با حروف بزرگ نشان می دهیم.رشته های عناصر پشته ای را با استفاده از حروف یونانی نشان می دهیم.یک PDA با استفاده از حالت جاری ، عنصر ورودی و عنصر بالایی پشته رفتار ماشین را تعیین می کند.

اسلاید 168: 8-1 آتاماتای pushdownگذر زیر سبب می شود:الف) حالت ماشین را از qi به qj تغییر می دهد.ب) عنصر a را پردازش کند( هد نوار را به جلو براند).ج) A را از بالای پشته حذف کند( عمل pop ).د) B را در پشته قرار دهد ( عمل pop ).[ qj , B ] є ∂ ( q1 , a , A )حالت جدیدحالت جاریعنصر جاری پشتهعنصر جدید پشتهعنصر جاری ورودی

اسلاید 169: 8-1 آتاماتای pushdownیک آتاماتای pushdown می تواند توسط یک دیاگرام حالت نیز توصیف شود. برچسب روی کمانها، عنصر ورودی و عمل پشته را مشخص می کند.

اسلاید 170: 8-1 آتاماتای pushdownحال می توانیم یک PDA M برای پذیرش زبان {a b li≥0} ایجاد کنیم.i i M: Q={q0,q1} ∑={a,b} Γ ={A} F={q0,q1} ∂(q0,a, )={[q0,A]} ∂(q0,b,A)={[q1, ]} ∂(q1,b,A)={[q1, ]}גּגּגּq0q1>/Aגּ a גּ b A/גּ b A/

اسلاید 171: 8-1 آتاماتای pushdownفرض کنید که (Q,∑,Γ,∂,q0,F) یک PDA باشد. یک رشته wє∑* توسط M قابل پذیرش است اگر یک محاسبه [q0,w, ] * [qi, , ] وجود داشته باشد بطوریکه qi є F باشد. زبان M مجموعه تمامی رشته های پذیرفته شده توسط M است.λλλ ┴

اسلاید 172: 8-1 آتاماتای pushdownبه محاسبه ای که یک رشته ورودی را می پذیرد، محاسبه موفق گفته می شود و به محاسبه ای که تمام رشته ورودی را پذیرفته و در یک حالت غیر پذیرش متوقف می شود، محاسبه ناموفق گفته می شود.

اسلاید 173: 8-1 آتاماتای pushdownمثال:PDA M زبان {w c w l wє{a,b}*} را می پذیرد.R M: Q={q0,q1} ∑={a,b,c} Γ={A,B} F={q1}גּ∂(q0,a, )={[q0,A]}∂(q0,b, )={[q1,B]}∂(q1,c, )={[q1, ]}גּגּגּ∂(q1,a,A)={[q1, ]}∂(q1,b,B)={[q1, ]}גּגּq0q1>/Aגּ a גּ a A/גּ/גּ c /Bגּ b גּ b B/

اسلاید 174: 8-1 آتاماتای pushdownیک PDA قطعی است اگر حداکثر یک گذر برای هر ترکیبی از حالت، عنصر ورودی و عنصر بالای پشته وجود داشته باشد. دو گذر [qj,c]є∂(qi.u.A) و [qk,D]є∂(qi,v,B) سازگار هستند اگر یکی از شرایط زیر را دارا باشند:(i u=v و A=B.(ii u=v و A= یا B= .(iii A=B و u=v یا v= .(iv u= یا v= و A= یا B= .גּגּגּגּגּגּגּ

اسلاید 175: 8-1 آتاماتای pushdownیک PDA قطعی است اگر آن شامل گذرهای سازگار مجزا نباشد.مثال:زبان L={a l i≥0} {a b I≥0} شامل a ها یا تعداد یکسانی از aها و bها است. پشته PDA M که زبان L را می پذیرد.ii iq0q1q2M: >/Aגּ a גּ A/גּגּ/ גּ גּגּ b A/גּ b A/

اسلاید 176: 8-2 انواع PDAهر گذر در PDA با سه عمل همراه است:1-pop کردن پشته2-pushکردن یک عنصر پشته ای 3-پردازش یک عنصر ورودییک PDA ساده (اتمی) است اگر هر گذر تنها موجب وقوع یکی از این عملیات شود.

اسلاید 177: 8-2 انواع PDAگذر ها در یک PDA ساده به اشکال زیر می باشند:[qj,A] є ∂(qi, , )[qj, ] є ∂(qi,a, )[qj, ] є ∂(qi, ,A)גּגּגּגּגּגּیک گذر توسعه یافته، یک عمل روی PDA است که یک رشته از عناصر را در پشته push می کند. گذر[qi,BCD]є∂(qi,u,A) رشته BCD را در پشته push می کند.

اسلاید 178: 8-2 انواع PDAمثال:فرض کنید که L={a b l i≥1} است.i iPDAتوسعه یافتهPDA سادهPDA גּQ={q0,q1,q2}∂(q0,a, )={[q2,A]}∂(q2, , )={[q0,A]}∂(q0,b,A)={[q1, ]}∂(q1,b,A)={[q1, ]}גּגּגּגּגּגּגּגּגּQ={q0,q1,q2,q3,q4}∂(q0,a, )={[q3, ]}∂(q3, , )={[q2,A]}∂(q2, , )={[q0,A]}∂(q0,b, )={[q4, ]}∂(q4, ,A)={[q1, ]}∂(q1,b, )={[q4, ]גּגּגּגּגּגּגּQ={q0,q1}∂(q0,a, )={[q2,A]}∂(q0,b,A )={[q1, ]}∂(q1,b,A)={[q1, ]}גּגּגּ

اسلاید 179: 8-2 انواع PDAپیش قضیه:فرض کنید L یک زبان پذیرفته شده توسط (Q,∑,Γ,∂,q0,F) PDA M با پذیرش تعریف شده توسط حالت پایانی باشد. در این صورت یک PDA وجود دارد که زبان L را توسط حالت پایانی و پشته خالی بپذیرد.

اسلاید 180: 8-2 انواع PDAپیش قضیه:فرض کنید L یک زبان پذیرفته شده توسط (Q,∑,Γ,∂,q0,F) PDA M با پذیرش تعریف شده توسط پشته خالی باشد. در این صورت یک PDA وجود دارد که زبان L را توسط حالت پایانی و پشته خالی بپذیرد.

اسلاید 181: 8-2 انواع PDAقضیه:شرایط زیر با هم معادلند:(i زبان L توسط برخی PDAها پذیرفته می شود.(ii یک PDAM1 با LF(M1)=L وجود دارد.(iii یک PDAM2 با LE(M2)=L وجود دارد.

اسلاید 182: 8-3 آتاماتای pushdown و زبانهای مستقل از متنقضیه:فرض کنید که L یک زبان مستقل از متن باشد. در این صورت PDAای وجود دارد که زبان L را بپذیرد.

اسلاید 183: 8-3 آتاماتای pushdown و زبانهای مستقل از متنفرض کنید که (Q,∑,Γ,∂,q0,F) =M یک PDA باشد، یک PDA M′ توسعه یافته با تابع گذر∂′ بوسیله گذرهای ∂ از M ایجاد می شود:(i اگر [qi, ]є∂(qi,u, ) باشد، آنگاه برای هر AєΓ داریم [qj,A] є∂′(qi,u,A) .(i اگر [qj,B]є∂(qi,u, ) باشد، آنگاه برای هر AєΓ داریم [qj,BA] є∂′(qi,u,A) .גּגּגּ

اسلاید 184: 8-3 آتاماتای pushdown و زبانهای مستقل از متنمثال:یک گرامر از PDA M ایجاد می کنیم. زبان Mمجموعه {a cb l n≥0} است.n n M: Q={q0,q1} ∑={a,b,c} Γ={A} F={q1}גּ∂(q0,a, )={[q0,A]}∂(q0,c, )={[q1, ]}∂(q1,b,A)={[q1, ]}גּגּגּ

اسلاید 185: 8-3 آتاماتای pushdown و زبانهای مستقل از متنقضیه:فرض کنید که M یک PDA باشد. در این صورت یک گرامر مستقل از متن G با L(G)=L(M) وجود دارد.

اسلاید 186: 8-4 پیش قضیه فشار برای زبانهای مستقل از متنپیش قضیه:فرض کنید که G یک گرامر مستقل از متن در فرم نرمال شومسکی و A * w یک اشتقاق از w є ∑* با درخت اشتقاق T باشد. اگر عمقT برابرn باشد، آنگاه length(w)≤2 خواهد بود.n-1

اسلاید 187: 8-4 پیش قضیه فشار برای زبانهای مستقل از متنفرض کنید G=(V,∑,P,S) یک گرامر مستقل از متن در فرم نرمال شومسکی و S * w یک اشتقاق از w L(G) است. اگر length(w)≤2ⁿ باشد، آنگاه عمق درخت اشتقاق حداقل برابرn+1 خواهد بود.

اسلاید 188: 8-4 پیش قضیه فشار برای زبانهای مستقل از متنقضیه (پیش قضیه فشار برای زبانهای مستقل از متن)فرض کنید که L یک زبان مستقل از متن باشد.یک عدد k وابسته به L وجود داردبطوریکه هر رشته ZєL با length(z)>k می تواند به صورت z=uvwxy نوشته شود که دارای شرایط زیر باشد.(i length(vwx)≤ k(ii length(v)+length(x)>0(iii برای i≥0 ، uv wx y є Li i مستقل از متن نیست.L={w єa* l اول است length(w) } زبان

اسلاید 189: 8-5 خصوصیات همبستگی زبانهای مستقل از متنقضیه:مجموعه زبانهای مستقل از متن نسبت به عملیات اجتماع، الحاق و عملگر ستاره (kleen star) بسته هستند.قضیه:مجموعه زبانهای مستقل از متن نسبت به عملیات اشتراک و مکمل بسته نیست.قضیه:فرض کنید که R یک زبان با قاعده و L یک زبان مستقل از متن باشد. در این صورت R∩L مستقل از متن است.

اسلاید 190: 8-6 آتاماتای دو پشته ایآتاماتای دو پشته ای:PDA دو پشته ای دارای ساختار (Q,∑,Γ,∂,q0,F) است. Q,∑,Γ,∂,q0,F مشابه PDA تک پشته ای می باشند. تابع گذر∂ ، تابعی از Q×(∑υ{ })×(Γυ{ })×(Γυ{ }) به زیر مجموعه هایی از Q×(Γυ{ })×(Γυ{ }) است.حالت عناصر ورودی و عناصر بالای هر دو پشته تعیین می کنند که کدام گذر بایستی انتخاب شود.גּגּגּגּגּ

اسلاید 191: 8-6 آتاماتای دو پشته ایمثال:PDA دو پشته ای تعریف شده زیر زبان L={a b c l i≥ 0} را می پذیرد.i i i M: Q={q0,q1,q2} ∑={a,b,c} Γ={A} F={q2}גּ∂(q0, , , )={[q2, , ]}∂(q0,a, , )={[q0,A, ]}∂(q0,b,A, )={[q1, ,A]}∂(q1,b,A, )={[q1, ,A]}∂(q1,c, ,A)={[q2, , ]}∂(q2,c, ,A)={[q2, , ]}גּגּגּגּגּגּגּגּגּגּגּגּגּגּגּגּגּ

اسلاید 192: فصل نهم:ماشینهای تورینگاهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: ماشین تورینگ انواع پذیرش ماشین های چند شیارهماشین های تورینگ غیر قطعی

اسلاید 193: فصل نهم : ماشینهای تورینگماشین تورینگ یک ماشین با حالات متناهی است که هر گذر آن عنصری را روی نوار چاپ می کند.ماشین تورینگ یک پنچ تایی (Q,∑,Γ,∂,q0) است که در آن Q مجموعه متناهی از حالات ، Γ یک مجموعه متناهی موسوم به الفبای نوارشامل یک عنصر ویژه B که نماینگر فاصله خالی است، ∑یک مجموعه از Γ–{B} موسوم به الفبای ورودی، ∂یک تابع جزئی از Γ × Q به Q×Γ× {L×R} موسوم به تابع گذر و q0єQ یک حالت مشخص به نام حالت ابتدایی می باشد.

اسلاید 194: 9-1 ماشین تورینگ استانداردنوار یک ماشین تورینگ در یک جهت تا بی نهایت ادامه می یابد. مکانهای نوار با اعداد طبیعی از چپ به راست شماره گذاری می شوند.…0 1 2 3 4 5 …q0

اسلاید 195: 9-1 ماشین تورینگ استانداردیک گذر شامل سه عمل است:1- تغییر حالت 2- نوشتن یک عنصر روی مربع در حال پویش توسط هد نوار3- حرکت هد نوار.جهت حرکت توسط آخرین جزء گذر تعیین می شود.

اسلاید 196: 9-1 ماشین تورینگ استاندارداین گذر حالت ماشین را از qi به qj تغییر داده، عنصر x نوار را با y جایگزین نموده و هد نوار را یک مکان به چپ حرکت می دهد.یک ماشین تورینگ هنگامی متوقف می شود که برای زوج مرتب حالت جاری و عنصر ورودی، هیچ گذری تعریف نشده باشد. یک گذر ممکن است بخواهد از مکان صفر نوار یک حرکت به چپ محدوده نوار انجام دهد که در این صورت متوقف می شود و به این نوع توقف، توقف غیر عادی گوییم. هرگاه می گوییم یک محاسبه متوقف می شود، منظور توقف در شرایط عادی است.

اسلاید 197: 9-1 ماشین تورینگ استانداردمثال:ماشین تورینگ COPY با الفبای ورودی {a,b} یک کپی از رشته ورودی را تولید می کند. به عبارتی، محاسبه ای که با نوار شامل BuB شروع می شود با نوار BuBuB متوقف می گردد.q0q1q7q2q5q3q6q4COPY: >B/B RB/B LX/a LY/b LX/X RY/Y Ra/a Rb/b Ra/X Rb/Y Ra/a Rb/b Ra/a Rb/b RB/B RB/B RB/a LB/b La/a Rb/b Ra/a Lb/b LB/B L

اسلاید 198: 9-2 ماشین تورینگ به عنوان پذیرنده زبانفرض کنید که (Q,∑,Γ,∂,q0,F) یک ماشین تورینگ باشد. یک رشته Uє∑* توسط حالت پایانی پذیرفته می شود اگر محاسبه M با ورودی u در یک حالت پایانی متوقف شود. محاسبه ای که به طور غیر عادی متوقف می شود رشته ورودی را بدون توجه به حالت پایانی ماشین رد می کند. زبان M ، که با L(M) نشان داده می شود، مجموعه تمامی رشته های پذیرفته شده توسط M است.

اسلاید 199: 9-2 ماشین تورینگ به عنوان پذیرنده زبانیک زبان پذیرفته شده توسط یک ماشین تورینگ به زبان بازگشتی شمارش پذیر موسوم است.ماشین تورینگی که برای تمامی رشته های ورودی متوقف می شود زبانی را می پذیرد که به آن بازگشتی گویند.بازگشتی بودن از ویژگیهای یک زبان است نه از خصوصیات ماشین تورینگ پذیرنده آن.

اسلاید 200: 9-2 ماشین تورینگ به عنوان پذیرنده زبانمثال:ماشین تورینگq0q1q2q3M: >B/B Rb/b Rb/b Ra/a Ra/a Rزبان (aυb)*aa(aυb)* را می پذیرد.

اسلاید 201: 9-3 انواع پذیرش در ماشینهای تورینگانواع پذیرش در ماشینهای تورینگ:در ماشین تورینگی که برای پذیرش توسط توقف طراحی شده است، یک رشته ورودی پذیرفته می شود اگر محاسبه رشته موجب توقف ماشین شود.فرض کنید که (Q,∑,Γ,∂,q0,F) یک ماشین تورینگ با پذیرش توسط توقف باشد. یک رشته Uє∑* توسط توقف پذیرفته می شود اگر محاسبه M با ورودی u به طور عادی متوقف شود.

اسلاید 202: 9-3 انواع پذیرش در ماشینهای تورینگمثال: زبان (aυb)*aa(aυb)* q0q1q2q3>B/B Rb/b Rb/b Ra/a Ra/a RqfB/B Ra/a Rb/b Rb/b Ra/a RB/B RB/B R

اسلاید 203: 9-3 انواع پذیرش در ماشینهای تورینگنوعی از پذیرش موسوم به پذیرش توسط ورود که از حالت پایانی استفاده کرده و هیچ نیازی به محاسبات پذیرس جهت توقف ندارد.یک رشته پذیرفته می شود اگر محاسبه وارد یک حالت پایانی شده باشد.

اسلاید 204: 9-4 ماشینهای چند شیارهیک نوار چند شیاره نواری است که به شیارهای متععدی تقسیم شده باشد. یک مکان در یک نوار n شیاره شاما n عنصر از الفبای نوار است. دیاگرام زیر یک نوار دو شیاره با هد نوار در حالت پویش دو مکان معین را نشان می دهد.شیار 2شیار 1qi

اسلاید 205: 9-4 ماشینهای چند شیارهقضیه:یک زبان L توسط یک ماشین تورینگ دو شیاره پذیرفته می شود اگر و تنها اگر آن توسط یک ماشین تورینگ استاندارد پذیرفته شود.

اسلاید 206: 9-5 ماشین تورینگ با نوار دو طرفهماشین تورینگ با نوار دو طرفه:یک ماشین تورینگ با یک نوار دو طرفه مشابه ماشین تورینگ استاندارد است با این تفاوت که نوار آن از هر دو طرف تا بینهایت ادامه می یابد.یک ماشین با نوار دو طرفه می تواند با قراردادن یک عنصر ویژه روی نوار جهت نمایش محدوده چپ نوار یک طرفه، عملیات یک ماشین استاندارد را شبیه سازی کند.

اسلاید 207: 9-5 ماشین تورینگ با نوار دو طرفهمثال:ماشین تورینگ استانداردM رشته هایی را روی {a,b} می پذیرد که در آن قبل از هر b، در صورت وجود، حداقل سه a وجود داشته باشد.q0q1q2q3M: >B/B Rb/b La/a Rq4q5B/B La/a LB/B La/a LB/B La/a L

اسلاید 208: 9-5 ماشین تورینگ با نوار دو طرفهقضیه:یک زبان L توسط یک ماشین تورینگ با یک نوار دوطرفه پذیرفته می شود اگر و تنها اگر آن توسط یک ماشین تورینگ استاندارد پذیرفته می شود.

اسلاید 209: 9-6 ماشینهای چند نوارهیک ماشین kنواره شامل kنوار و kهد مجزا است.حالات و الفباهای یک ماشین چند نواره مشابه ماشین تورینگ استاندارد است. ماشین به طور همزمان نوارها را می خواند.این کار با اتصال هر یک از هدها به یک ثبّات کنترلی مجزا که حاوی حالت جاری است انجام می شود.نوار 3نوار 2نوار 1qi

اسلاید 210: 9-6 ماشینهای چند نوارهیک گذر در یک ماشین چند نواره ممکن است:(i حالت را تغییر دهد.(ii یک عنصر روی هر یک از نوارها بنویسد.(iii هر یک از هدها را به صورت مجزا جابجا کند.قضیه: یک زبان L توسط یک ماشین تورینگ چند نواره پذیرفته می شود اگر و تنها اگر آن توسط یک ماشین تورینگ استاندارد پذیرفته می شود.

اسلاید 211: 9-6 ماشینهای چند نوارهمثال:ماشین تورینگ دونواره ای که دیاگرام حالت آن درزیرآمده است،زبان {uu l uє{a,b}*} را می پذیرد.q0q1q2q3>B/B R , B/B Rq3q4B/B L , B/B LB/B R , y/y Ry/y R , B/B Rx/x L , y/y Lx/x L , y/y Sx/x R , x/x Rx/x R , B/x R

اسلاید 212: 9-6 ماشینهای تورینگ غیر قطعییک ماشین تورینگ غیر قطعی ممکن است یک تعداد متناهی از گذرها را برای یک وضعیت مشخص تعین کند. اجزا یک ماشین غیر قطعی ، به جز تابع گذر، عیناً مشابه اجزا ماشین تورینگ استاندارد است. گذرها در یک ماشین غیر قطعی یه وسیله یک تابع جزئی ازQ×Γ به زیر مجموعه هایی از Q×Γ×{L,R} تعریف می شود.

اسلاید 213: 9-6 ماشینهای تورینگ غیر قطعیمثال:ماشین غیر قطعی زیر رشته هایی را می پذیرد که در آن یک c قبل یا بعد از ab وجود داشته باشد.q0q1q2q3>B/B Rb/b Rc/c Rq4q5a/a Lq6q7a/a Rc/c Lb/b La/a Rb/b Rc/c R

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

اسلاید 215: فصل دهم : طبقه بندی شومسکیگرامرهای بدون محدودیت بزرگترین گروه از گرامرهای عبارت می باشند. یک قانون u v مشخص می کند که یک رخداد از زیررشته u در یک رشته ممکن است با رشته v جایگزین شود. یک اشتقاق دنباله ای از جایگزینی ها مجاز است. تنها محدودیتی که روی یک قانون از یک گرامر اعمال می شود این است که سمت چپ آن نبایستی تهی باشد. به این سیستمهای بازنویسی رشته ها، گرامرهای نوع صفر نیز گفته می شود.

اسلاید 216: 10-1 گرامرهای بدون محدودیتیک گرامر بدون محدودیت یک گرامر چهارتایی(V,∑,P,S) است که V یک مجموعه متناهی از متغیرها، ∑ (الفبا)یک مجموعه متناهی از عناصر پایانی،P یک مجموعه از قوانین و S یک عنصر مشخص در V می باشد. یک قانون از یک گرامر بدون محدودی به شکل u v است که در آن uє(Vυ∑) و vє(Vυ∑)* می باشد.فرض می شود که مجموعه های V و∑ غیر الحاقی هستند.+

اسلاید 217: 10-1 گرامرهای بدون محدودیتگرامرهای باقاعده و مستقل از متن زیر مجموعه هایی از گرامرهای بدون محدودیت هستند. یک گرامر مستقل ازمتن یک گرامر عبارت است که در سمتچپ هر قانون آن تنها یک متغیر وجود دارد. قوانین یک گرامر باقاعده به یکی از اشکال(i A aB(ii A a (iii A می باشد که A,BєV و ∑ є a است.λ

اسلاید 218: 10-1 گرامرهای بدون محدودیتمثال:گرامر بدون محدودیت زیر با عنصر ابتدایی Sزبان{a b c l i≥0}را تولید می کند.i i iV={S,A,C}∑={a,b,c}S aAbc l A aAbc lCb bCCc ccגּגּ

اسلاید 219: 10-1 گرامرهای بدون محدودیتقضیه:فرض کنید که G= (V,∑,P,S) یک گرامر بدون محدودیت باشد. در این صورت L(G) یک زبان بازگشتی شمارش پذیر است.قضیه:فرض کنید که L یک زبان بازگشتی شمارش پذیر باشد. در این صورت یک گرامر بدون محدودیت G با L(G)=L وجود دارد.قضیه:مجموعه زبانهای بازگشتی شمارش پذیرنسبت به عمل اجتماع، الحاق و عملگر ستاره (kleen star) بسته است.

اسلاید 220: 10-2 گرامرهای وابسته به متنگرامرهای وابسته به متن یک مرحله میانی بین گرامرهای مستقل از متن و گرامرهای بدون محدودیت می باشند. در این گرامرها، هیچ محدودیتی برای سمت چپ یک قانون وجود ندارد، اما طول سمت راست آن بایستی حداقل به اندازه طول سمت چپ باشد.

اسلاید 221: 10-2 گرامرهای وابسته به متنیک گرامر عبارت وابسته به متن است اگر هر قانون به شکل u v باشد که uє(Vυ∑) و vє(Vυ∑)* وlength(u)≤length(v) است.+به قانونی که در شرایط فوق صدق کند یکنواخت(monotonic) گفته می شود.قضیه:هر زبان وابسته به متن بازگشتی است.

اسلاید 222: 10-3 آتاماتای خطی محدودیک آتاماتای خطی محدود(LBA) یک ساختار Q,∑,Γ,∂,q0,<,>,F) M=(است که در آن Q,∑,Γ,∂,q0, F مشابه ماشین تورینگ غیر قطعی می باشند. عناصر >,< عناصری مشخص از ∑ هستند.

اسلاید 223: قضیه:فرض کنید که L یک زبان وابسته به متن است. در این صورت، یک آتاماتای خطی محدود M با L(M)=L وجود دارد.10-3 آتاماتای خطی محدودقضیه:فرض کنید که L یک زبان پذیرفته شده توسط یک آتاماتای خطی محدود باشد. در این صورت }גּ L- { یک زبان وابسته به متن است.

اسلاید 224: 10-4 طبقه بندی شومسکیطبقه بندی شومسکی شامل چهار گروه از گرامرها(زبانها) است:1- گرامرهای بدون محدودیت2- گرامرهای وابسته به متن3- گرامرهای مستقل از متن4- گرامرهای باقاعدهکه به ترتیب به گرامرهای نوع 0 ، نوع 1 ، نوع 2 ، و نوع 3معروفند.

اسلاید 225: 10-4 طبقه بندی شومسکیگرامرهاگرامرهای نوع 0،گرامرهای عبارات،گرامرهای بدون محدودیتگرامرهای نوع 1،گرامرهای وابسته به متن،گرامرهای یگنواختگرامرهای نوع 2،گرامرهای مستقل از متنگرامرهای نوع 3،گرامرهای باقاعده،گرامرهای خطی چپ،گرامرهای خطی راستزبانهازبانهای بازگشتیشمارش پذیرزبانهای وابسته به متنزبانهای مستقل از متنزبانهای باقاعدهماشینهای پذیرنده ماشین تورینگ،ماشین تورینگ غیر قطعیآتاماتای خطی محدودآتاماتای pushdownآتاماتای متناهی قطعی،آتاماتای متناهی غیر قطعی