۰
subtitle
ارسال: #۱
صحت زبان های منظم
[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]
این یک عبارت منظم برای زبان زیر هست که در پایین گرامر و زبانش رو نوشتم ایا اینی که من نوشتم درست هستم برای رشته با معکوسه خودش؟
یه سوال دیگم هم اینه که در این گرامر در قسمت دوم یک 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]
۰
ارسال: #۲
RE: صحت زبان های منظم
الف)
رشته 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]
است که میبینیم نه خطی راست است نه خطی چپ پس گرامر منظم نیست.
رشته 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]) که من ربطشو با بقیه سوالاتون پیدا نمیکنم.
بچه‌ها واقعا خیلی خوبه که به سوالهایی که پرسیده میشه این قدر توجه میکنید و کامل پاسخ میدین. من به نوبه خودم ازتون تشکر می کنم.
می خواستم بگم تو گرامری که afagh1389 توضیح دادن [tex]a|b[/tex] باید حذف بشه.
امیدوارم سوء برداشت نشه، قصد بی ادبی نداشتم فقط میخواستم دوستانی که این تاپیکو می خونن به اشتباه نیفتن.
masoudkhan اول سوالتون یه زبان نوشتین ([tex]L(G)={a*b*}[/tex]) که من ربطشو با بقیه سوالاتون پیدا نمیکنم.
ارسال: #۵
RE: صحت زبان های منظم
(۱۷ خرداد ۱۳۹۰ ۰۸:۵۱ ق.ظ)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 گرامر رو نامنظم می کنه ؟
۰
ارسال: #۶
RE: صحت زبان های منظم
ممنون آقا بهداد بابت تذکرتون
من خیلی بی دقت هستم توی کنکور هم خیلی بی دقتی کردم
این a,b رو که نوشته بودم به این خاطر بود که یک لحظه با [tex]w=w^{R}[/tex]
اشتباه گرفتم!!!!
من خیلی بی دقت هستم توی کنکور هم خیلی بی دقتی کردم
این a,b رو که نوشته بودم به این خاطر بود که یک لحظه با [tex]w=w^{R}[/tex]
اشتباه گرفتم!!!!
۰
ارسال: #۷
صحت زبان های منظم
من مشکل در این بود که فکر می کردم هر چقدر a خونده بشه همون قدر هم b خونده میشه یعنی حساب کردم که * در هر دو تاشون برابره که به نظر اشتباه من غلط بوده
مرسی افاق جان
مرسی افاق جان
ارسال: #۸
RE: صحت زبان های منظم
(۱۷ خرداد ۱۳۹۰ ۰۱:۴۷ ب.ظ)masoudkhan نوشته شده توسط: من مشکل در این بود که فکر می کردم هر چقدر a خونده بشه همون قدر هم b خونده میشه یعنی حساب کردم که * در هر دو تاشون برابره که به نظر اشتباه من غلط بودهبله درسته مشکلتون همین جا بود
مرسی افاق جان
a* یعنی یک طوقه با برچسب a که طوقه کنترل شده نیست و هر تعدادی a میشه باهاش تولید کرد.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close