سلام دوستان میشه تو فهم این سوال کمکم کنید پیشاپیش سپاسگذارم
مجموعه متغیرهایV و پایانه های T مفروضند. زبان L عبارات است از مجموعه تمام قواعد تولید گرامرهای مستقل از متنی ک روی V,T تعریف می شوند آنگاه Lزبانی ...
۱)منظم است
۲)تصمیم ناپذیر است
۳)مستقل از متن است ولی منظم نیست.
۴)تصمیم ناپذیر است ولی مستقل ازمتن نیست.
جواب گزینه ۲
باتشکر
![[تصویر: 320514_39954365455305582715.png]](https://img.manesht.ir/320514_39954365455305582715.png)
آیا کسی نیست مرا یاری دهد؟؟؟؟
گرامرهای مستقل از متن به صورت زیر هستند:
[tex]\alpha--.>\beta[/tex]
که [tex]\alpha\in V[/tex] و [tex]\beta\in(Sigma\cup V)^{\ast}[/tex]
یعنی سمت راست قوانین حتما همیشه دقیقا یک متغیر وجود دارد
که اگه مجموعه ی متغیر ها رو [tex]\{x_1,x_2,...,x_n\}[/tex] و مجموعه ی القبا رو [tex]\{a_1,a_2,...,a_m\}[/tex] در نظر بگیریم
سمت راست قوانین یا [tex]x_1[/tex] است یا [tex]x_2[/tex] است یا ....یا [tex]x_n[/tex]
سمت چپ قوانین می تونه هر چیزی از [tex](Sigma\cup V)^{\ast}[/tex] باشه که یعنی [tex](x_1,x_2,,,,,,\: x_n,a_1,a_2,,....a_m)^{\ast}[/tex]
پس هر قانون به فرم
[tex](x_1 x_2 \: ... x_n)-->(x_1 x_2 ... x_n a_1 a_2 ... a_m)^{\ast}[/tex]
است
پس عبارت [tex](x_1 x_2 \: ... x_n)-->(x_1 x_2 ... x_n a_1 a_2 ... a_m)^{\ast}[/tex] تمام گرامر های به فرم مشتقل از متن رو تولید می کنه
که اگه در یک زبان L2 که تمام نمادهای [tex]x_1وx_2و...وx_nوa_1وa_2و...وa_m,"-->"[/tex] عضو الفبای زبان است عبارت
[tex](x_1 x_2 \: ... x_n)-->(x_1 x_2 ... x_n a_1 a_2 ... a_m)^{\ast}[/tex] یک عبارت منظم محسوب می شود
پس تمام گرامر های مستقل از متن رو می شه با عبارت منظم بدست آورد پس مجموعه ی گرامر های مستقل از متن ، مجموعه ای منظم است.
یه روش حل دیگه ی این سوال بدست آوردن گرامر منظم (به جای عبارت منظم) برای تولید همه ی گرامر های مستقل از متن است
گرامز G:
[tex]S-->V\: "\-->"\: X[/tex]
[tex]V-->x_1|x_2|...|x_n[/tex]
[tex]T-->a_1|a_2|...|a_n[/tex]
[tex]X-->TX|VX|\lambda[/tex]
اگه دقت کنید الفبای زبان تولید شده توسط این زبان نمادهای [tex]x_1وx_2و...وx_nوa_1وa_2و...وa_m,"-->"[/tex] است
و اگه از S شروع کنید یه سری قانون هایی به فرم
[tex]\alpha--.>\beta[/tex] هستند که
که [tex]\alpha\in V[/tex] و [tex]\beta\in(T\cup V)^{\ast}[/tex]
که اهر کدام از نوع مستقل از متن هستند
و اگه دقت کنید گرامر G که در بالا معرفی شد گرامری منظم است
(۱۹ آذر ۱۳۹۳ ۱۱:۰۸ ب.ظ)fatemeh69 نوشته شده توسط: گرامرهای مستقل از متن به صورت زیر هستند:
[tex]\alpha--.>\beta[/tex]
که [tex]\alpha\in V[/tex] و [tex]\beta\in(Sigma\cup V)^{\ast}[/tex]
یعنی سمت راست قوانین حتما همیشه دقیقا یک متغیر وجود دارد
که اگه مجموعه ی متغیر ها رو [tex]\{x_1,x_2,...,x_n\}[/tex] و مجموعه ی القبا رو [tex]\{a_1,a_2,...,a_m\}[/tex] در نظر بگیریم
سمت راست قوانین یا [tex]x_1[/tex] است یا [tex]x_2[/tex] است یا ....یا [tex]x_n[/tex]
سمت چپ قوانین می تونه هر چیزی از [tex](Sigma\cup V)^{\ast}[/tex] باشه که یعنی [tex](x_1,x_2,,,,,,\: x_n,a_1,a_2,,....a_m)^{\ast}[/tex]
ببین فاطمه جان من الان میدونم ک L مستقل از متن ولی سوال چیزی زیادی توضیح نداده ک بفهمم منظم هست یا نه مگر منظم زیر مجموعه مستقل نیست حالا بر اساس چ توضیحی از سوال فهمیده گزینه درست تصمیم ناپذیر
شما L رو چی در نظر می گیرید؟
اگه L مجموعه ی تمام رشته های عبارت زیر است:
[tex](x_1 x_2 \: ... x_n)-->(x_1 x_2 ... x_n a_1 a_2 ... a_m)^{\ast}[/tex]
خب اینو که گفتم این خودش به عبارت منظم است پس مجموعه ی رشته های این عبارت یه زبان منظم است
به یک نکته دقت کنید که درسته که اعضای زبان قوانین گرامر های مستقل از متنه
اما خود زبان از نوع منظم است
یعنی با یک زبان از نوع منظم می توان تمام قواعد مستقل از متن رو تولید کرد
پاسخنامه هم اشتباها زده گزینه دو منظورش همون گزینه ۱ بوده (اشتباه تایپی داره)
آخه خودش هم آخرش نوشته که "بنابریان زبان L منظم است"
(۱۹ آذر ۱۳۹۳ ۱۱:۳۵ ب.ظ)fatemeh69 نوشته شده توسط: شما L رو چی در نظر می گیرید؟
اگه L مجموعه ی تمام رشته های عبارت زیر است:
[tex](x_1 x_2 \: ... x_n)-->(x_1 x_2 ... x_n a_1 a_2 ... a_m)^{\ast}[/tex]
خب اینو که گفتم این خودش به عبارت منظم است پس مجموعه ی رشته های این عبارت یه زبان منظم است
به یک نکته دقت کنید که درسته که اعضای زبان قوانین گرامر های مستقل از متنه
اما خود زبان از نوع منظم است
یعنی با یک زبان از نوع منظم می توان تمام قواعد مستقل از متن رو تولید کرد
پاسخنامه هم اشتباها زده گزینه دو منظورش همون گزینه ۱ بوده (اشتباه تایپی داره)
آخه خودش هم آخرش نوشته که "بنابریان زبان L منظم است"
ممنونم واقن فاطمه جان به قول مامانا خدا عمرت بده یا پیر شی مادر
