زبان های مستقل از متن

صفحه 1:
ری ‎Fe fh Pies‏ =E_Y/ WJ 

صفحه 2:
زبان های مستقل از متن استاد مربوطه: جناب آقای مهران آقابی تهیه کننده: دانشجو سید محمد حسین سلیم بهرامی 

صفحه 3:
اهداف * گرامرها و زبان های مستقل از متن ‎Glad!‏ و درخت آن * گرامرهای قاعده 

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

صفحه 5:
گرامر مستقل از متن: یک گرلمر مستقل از متن.بیک چهارتلیی (6(,2),)9) است که درّن (کیک مجموعه متناهی از متفیرها, 2(الفبالیک مجموعه متناهی از عناصر پایلنی:)بیک مجموعه متناهی از قوانین و 8 یک عنصر مشخص از () به نام عنصر ابتدایی است. فرض می شود که 0و 2مجموعه هایی غیر الحاقی هستند. 

صفحه 6:
nde) sili ‏یک قانون که به آن یک تولید نيز می گویند. عضوی از مجموعه (0*)60۷۶)است. قانون‎ qd ge agg A> ۲/1 ‏معمولاً به صورت‎ [Owl نکته:از آنجائیکه رشته تهی در(لا(۳6)* وجود دارد. لذا ۸ نیز ممکن است در سمت راست یک قانون قرار گیرد. نكته:قانونى به شكلم + لك به قانون تهى يا قانون لامبدا موسوم است. مرحله اصلى در فرايند توليد. تبديل يك رشته با استفاده از يك قانون است. مثال:بكار كيرى قانون بي © براى متغير در 1ك رشته بميعرا توليد مى كندكه آن را به ‎HAYS UWtr‏ دهيم. 

صفحه 7:
یک رشته سداز مه قابل اشتقاق است اگر یک دنباله متناهی از قوانین که مرا به سا تبدیل می کنند وجود داشته باشد. قابليت اشتقاق بمداز را به صورت/154 ۲ نشان می دهیم. 

صفحه 8:
مجموعه رشته های قابل اشتقاق از :۱۷ فرض كنيد که (۷,۶,۴,5)<) یک گرامر مستقل از متن و( 6)۷/۷۶ لا باشد. مجموعه رشته های قابل اشتقاق از ۷ به صورت باز گشتی زیر تعریف می شود: ۱-پایه: ۷ از ۷ قابل اشتقاق است. ۲-گام بازگشت: اگر 2۵۷ لا از ۷ قابل اشتقاق بوده و ۷/6۳ 8 باشد. آنگاه 6۷۷( از ۷ قابل اشتقاق خواهد بود. ۳-همبستگی: تمامی رشته های ایجاد شده از ۷ با بکارگیری تعداد متناهی گام بازگشت از ۷ قابل اشتقاقند. نکته‌زیک گرامر شامل یک الفبا یک روش تولید رشته ها است. اين رشته ها ممکن است شامل متغیرها و عناصر پاینی باشند. 

صفحه 9:
فرض کنید که (),*),02))0,۶) یک گرامر مستقل از متن باشد. فرم جمله ایبیک رشته (6)600 ممه* یک فرم جمله ای از 68 است اگر یک اشتقاق رن جع 6 وجود داشته باشد. جمله:یک رشته 26 یک جمله از 8) است اگر یک اشتقاق* جف مدا در۶) وجود داشته باشد. زبان 8): که آنرا با (0)) رانشان می دهند.مجموعه زیراست. ‎wh‏ بو" ,2 ع۷) 

صفحه 10:
فرم جمله ای هاء رشته هایی قابل اشتقاق ازعنصرابتدایی گرامرهستند . جملات فرم جمله ایهایی هستند که تنها شامل عناصر پایانی می باشند. به مجموعه ای از رشته ها روی یک مجموعه الفبا(2) زبان مستقل از متن گفته می شود. 

صفحه 11:
.يك قانون © به شكا5 324 + ل را بازگشت مستقیم می نامیم. به يك اشتقاق,] 11 جل |[ حير 9 در ‎com‏ ‏با غیر مستقیم می گوییم. 

صفحه 12:
اشتقاق راست و چپ: اشتقاق چپ:هر قانونی که به اشتقاق اولین متغیر سمت چپ رشته می پردازد. اشتقاق راست: به قوانینی که راست ترین متغیر موجود در هر رشته را تبدیل می کنند. 

صفحه 13:
درخت اشتقاق: فرض کنید که (02)0,۲,0*,0)یک گرامر مستقل از متن بوده وس 6 یک اشتقاق باشد.درخت اشتقاق رس ) یک درخت مرتب شده است که به صورت زیر ساخته می شود: ۱- درخت اشتقاق )را با ربشه مقداردهی کنید. ‎GHAVUL) A> X%%% soy‏ در اشتقاق بکار رفته برای رشته 0 باشد. آنگاه وبل أعنوان فرزندان © به درخت اضافه كنيد. ‎A A SI‏ قانونى در اشتقاق بكار رفته براى رشته بل باشد, آنگاه را به عنوان تنها فرزند) به درخت اضافه کنید. 

صفحه 14:
ترتیب برگها ‎oe‏ ‏®3 0, 6 © بط ,نت 8 ره میت 

صفحه 15:
فرض كنيد كه 8© يى كرامر مستقل از متن بوده وريه تل ریک اشتقاق در 8) باشد که ‎wA wa:‏ می تواند به صورت/۲۹ ۰۷۸ كت با مه نوشته شود.در این صورت رشته های (۳6)216*#ای وجود دارند که در شرایط زیر جر حف پم 2 مرح اوه = 

صفحه 16:
0 تن فرض کنید که 69 گرامری با قوانین زیر باشد: 6-۰ ۰ 6-۲۵۱ در این صورت [< مب , ‎a >O‏ امسوا 2)6() را خواهد بود. 

صفحه 17:
= گرامرهای با قاعده گرامر باقاعده: یک گرامر مستقل از متن است که هر قانون آن دارای یکی از حالات زیر است: ‎(i‏ وه AA (ii AaB (iii ‏که در آن ۵ 6 0,۵) و ۶06 می باشد.‎ یک زبان با قاعده است اگر بتواند توسط یک گرامر با قاعده تولید شود. 

صفحه 18:
کف »9 .موفق و موید باشید