[tex]L(G)=\left \{ a^*b^* \right \}[/tex]
این یک عبارت منظم برای زبان زیر هست که در پایین گرامر و زبانش رو نوشتم ایا اینی که من نوشتم درست هستم برای رشته با معکوسه خودش؟
یه سوال دیگم هم اینه که در این گرامر در قسمت دوم یک B جدا هست که فکر کنم این منظم بودن رو زیر سوال میبره درسته؟
[tex]A\rightarrow abA|B,B\rightarrow baB|\lambda \Rightarrow L(G)=\left \{ w w^{R}: n\geq 0 \right \}[/tex]
==============
دو تا سوال در این گرامر داشتم
ایا این زبان منظم هست
من فکر می کنم باشه چون همه متغییر‌ها در سمت راست هستند فقط نکته ای که برام مبهمه اینه که در این گرامر ایا وجود دو تا متغییر در کنار هم ایرادی نداره ؟
[tex]s\rightarrow aA ,A\rightarrow aAB|\lambda ,B\rightarrow abB|aB|\lambda[/tex]
========
به نظرم در قسمت دوم به خاطر وجود A در وسط قانون تولید بنابراین این گرامر منظم نیست درسته؟
[tex]S\rightarrow aAB , A\rightarrow aAb|\lambda ,B\rightarrow b[/tex]
الف)
رشته abba رو در نظر بگیرید [tex]ww^{R}[/tex] هست برای نوشتن گرامر برای این زبان باید گرامر رو به این صورت بنویسید:
[tex]S\rightarrow aSa|bSb|\lambda[/tex]
منظم نیست چون به حافظه نیاز داریم و به پشته.
گرامری منظم است که یا خطی راست باشد یا خطی چپ.
ب) قسمت فرمهای نرمال رو مطالعه بفرمایید.
ج) منظم نیست
[tex]A\rightarrow aAb[/tex]
نیاز به پشته داریم یعنی حافظه. شبیه [tex]a^{n}b^{n}[/tex]
[tex]A\rightarrow aAb[/tex]
مانند [tex]A\rightarrow aC[/tex]
[tex]C\rightarrow Ab[/tex]
است که میبینیم نه خطی راست است نه خطی چپ پس گرامر منظم نیست.
masoudkhan عزیز،
قوانین گرامرهای منظم دارای یک تعریف مشخص هستن و با دیدن قوانین یه گرامر میشه تعیین کرد که آیا این گرامر منظم هست یا نه.مثلا در کتاب لینز گرامرهای منظم به دو دسته‌ی گرامرهای خطی چپ و خطی راست تقسیم میشن.شما کافیه تا شکل کلی قواعد این گرامرها رو بدونید تا در عرض سه شماره منظم بودن یا نبودن یه گرامر رو تشخیص بدید
سلام
بچه‌ها واقعا خیلی خوبه که به سوالهایی که پرسیده میشه این قدر توجه میکنید و کامل پاسخ میدین. من به نوبه خودم ازتون تشکر می کنم.
می خواستم بگم تو گرامری که afagh1389 توضیح دادن [tex]a|b[/tex] باید حذف بشه.
امیدوارم سوء برداشت نشه، قصد بی ادبی نداشتم فقط میخواستم دوستانی که این تاپیکو می خونن به اشتباه نیفتن.
masoudkhan اول سوالتون یه زبان نوشتین ([tex]L(G)={a*b*}[/tex]) که من ربطشو با بقیه سوالاتون پیدا نمیکنم.
ممنون آقا بهداد بابت تذکرتون
من خیلی بی دقت هستم توی کنکور هم خیلی بی دقتی کردم
این a,b رو که نوشته بودم به این خاطر بود که یک لحظه با [tex]w=w^{R}[/tex]
اشتباه گرفتم!!!!
(۱۷ خرداد ۱۳۹۰ ۰۸:۵۱ ق.ظ)behdad نوشته شده توسط: سلام
بچه‌ها واقعا خیلی خوبه که به سوالهایی که پرسیده میشه این قدر توجه میکنید و کامل پاسخ میدین. من به نوبه خودم ازتون تشکر می کنم.
می خواستم بگم تو گرامری که afagh1389 توضیح دادن [tex]a|b[/tex] باید حذف بشه.
امیدوارم سوء برداشت نشه، قصد بی ادبی نداشتم فقط میخواستم دوستانی که این تاپیکو می خونن به اشتباه نیفتن.
masoudkhan اول سوالتون یه زبان نوشتین ([tex]L(G)={a*b*}[/tex]) که من ربطشو با بقیه سوالاتون پیدا نمیکنم.
از همه دوستان ممنونم
بله اون قوانین رو خوندم منظورم یا خطی راست یا خطی چپ
در رابطه با اخرین موضوع یعنی
[tex]a^*b^*[/tex]
یعنی هر چقدر a و بعدش هر چقدر b خوب این نوشته من نوعی عبارت منظم هست درسته
حالا می تونیم بگیم که این عبارت منظم هست و یک زبان منظم رو ایجاد می کنه
اما نکته من اینجاست فرمول بالایی یعنی
[tex]a^*b^*[/tex]
با
[tex]a^nb^n: n\geq 0[/tex]
چه فرقی می کنن هر دو یکی هستند بنابراین می تونیم بگیم هر دو منظم هستند ایا این برداشت من درست هست؟
و سوال بعدیم در رابهط با گرامر دومین سوالم هست که داره یک زبان که رشته رو با معکوسش داره میسازه هست که در قانون اولش نوشته شده
[tex]A\rightarrow abA|B[/tex]
ایا این B موجب میشه بتونیم بگیم که این B گرامر رو نامنظم می کنه ؟
(۱۷ خرداد ۱۳۹۰ ۱۰:۵۱ ق.ظ)masoudkhan نوشته شده توسط: از همه دوستان ممنونم
بله اون قوانین رو خوندم منظورم یا خطی راست یا خطی چپ
در رابطه با اخرین موضوع یعنی
[tex]a^*b^*[/tex]
یعنی هر چقدر a و بعدش هر چقدر b خوب این نوشته من نوعی عبارت منظم هست درسته
حالا می تونیم بگیم که این عبارت منظم هست و یک زبان منظم رو ایجاد می کنه
اما نکته من اینجاست فرمول بالایی یعنی
[tex]a^*b^*[/tex]
با
[tex]a^nb^n: n\geq 0[/tex]
چه فرقی می کنن هر دو یکی هستند بنابراین می تونیم بگیم هر دو منظم هستند ایا این برداشت من درست هست؟
و سوال بعدیم در رابهط با گرامر دومین سوالم هست که داره یک زبان که رشته رو با معکوسش داره میسازه هست که در قانون اولش نوشته شده
[tex]A\rightarrow abA|B[/tex]
ایا این B موجب میشه بتونیم بگیم که این B گرامر رو نامنظم می کنه ؟
برای [tex]a^*b^*[/tex] ما نیاز نداریم که بدونیم چه تعداد a خوندیم که به همون تعداد b بخونیم چون مثلا abb هم عضو این زبان هست پس نیاز به حافظه نداریم و میتونید براش DFA رسم کنید ولی برای [tex]a^nb^n: n\geq 0[/tex] نیاز به حافظه (پشته) داریم که بتونیم با توجه به تعداد aها به همون تعداد b بخونیم که با DFA این کار امکان پذیر نیست.
ب )نه B مشکلی ایجاد نمیکنه به قانون A--> B قانون یکه میگویند که مثلا میتونید با قرار دادن ax ای که سمت راست قانون B---> ax. به جای B اون رو از این وضعیت در بیارید.
حالا باید در نظر بگیرید که آیا کل قوانین همه خطی راست یا کل قوانین همه خطی چپ هست یا نه ؟!
و A-->abA هم مشکلی ایجاد نمیکنه چون میتونید A-->aC
C--->bA رو اضافه کنید که گرامر خطی راست باشه.البته نیازی به نوشتن نیست دیگه میدونید گرامری به این فرم خطی است.
من مشکل در این بود که فکر می کردم هر چقدر a خونده بشه همون قدر هم b خونده میشه یعنی حساب کردم که * در هر دو تاشون برابره که به نظر اشتباه من غلط بوده
مرسی افاق جان
(۱۷ خرداد ۱۳۹۰ ۰۱:۴۷ ب.ظ)masoudkhan نوشته شده توسط: من مشکل در این بود که فکر می کردم هر چقدر a خونده بشه همون قدر هم b خونده میشه یعنی حساب کردم که * در هر دو تاشون برابره که به نظر اشتباه من غلط بودهبله درسته مشکلتون همین جا بود
مرسی افاق جان
a* یعنی یک طوقه با برچسب a که طوقه کنترل شده نیست و هر تعدادی a میشه باهاش تولید کرد.