۰
subtitle
ارسال: #۱
دلیل مستقل از متن بودن یک زبان نامعلوم!
تست زیر مربوط به سراسری ۸۹ هست،
زبان های [tex]A,B,C\: \subseteq\: \{a,b\}\ast[/tex] به صورت زیر معرفی شده اند:
[tex]A\: =\: \{b\}B\: \cup\: \{a\}C[/tex]
[tex]B\: =\: \{\gamma\}\: \cup\: \{b\}\cup\{a\}C\: \cup\{a\}[/tex]
[tex]C\: =\: \{a\}A\: \cup\: \{\gamma\}\: \cup\: \{b\}[/tex]
کدام گزینه درست است؟
۱) [tex]CB\: \subseteq\: A[/tex]
۲) [tex]\{a\}\ast\: \subseteq\: A[/tex] و A منظم است
۳) A منظم نیست ولی مستقل از متن است.
۴) [tex]\{b\}\{b\}\ast\subseteq A[/tex] و A مستقل از متن است.
کتاب پوران جواب رو گزینه ۴ اعلام کرده و این طور توضیح داده: با توجه به اینکه زبانهای نوشته شده را می توان با گرامر مستقل از متن مدل نمود A مستقل از متن است ولی در مورد منظم بودن آن نمی توان ابراز نظر کرد.
حالا سوال من اینه که از کجا فهمید که میشه این سه زبان رو با گرامر مستقل از متن مدل نمود. این سه تا همه به هم مربوط هستند، حداقل اگه یکی شون به زبان دیگه ای وابسته نبود، مستقل از متن بودن ولی الان به نظر من قطعی نمیشه حرفی زد.
زبان های [tex]A,B,C\: \subseteq\: \{a,b\}\ast[/tex] به صورت زیر معرفی شده اند:
[tex]A\: =\: \{b\}B\: \cup\: \{a\}C[/tex]
[tex]B\: =\: \{\gamma\}\: \cup\: \{b\}\cup\{a\}C\: \cup\{a\}[/tex]
[tex]C\: =\: \{a\}A\: \cup\: \{\gamma\}\: \cup\: \{b\}[/tex]
کدام گزینه درست است؟
۱) [tex]CB\: \subseteq\: A[/tex]
۲) [tex]\{a\}\ast\: \subseteq\: A[/tex] و A منظم است
۳) A منظم نیست ولی مستقل از متن است.
۴) [tex]\{b\}\{b\}\ast\subseteq A[/tex] و A مستقل از متن است.
کتاب پوران جواب رو گزینه ۴ اعلام کرده و این طور توضیح داده: با توجه به اینکه زبانهای نوشته شده را می توان با گرامر مستقل از متن مدل نمود A مستقل از متن است ولی در مورد منظم بودن آن نمی توان ابراز نظر کرد.
حالا سوال من اینه که از کجا فهمید که میشه این سه زبان رو با گرامر مستقل از متن مدل نمود. این سه تا همه به هم مربوط هستند، حداقل اگه یکی شون به زبان دیگه ای وابسته نبود، مستقل از متن بودن ولی الان به نظر من قطعی نمیشه حرفی زد.
۰
ارسال: #۲
RE: دلیل مستقل از متن بودن یک زبان نامعلوم!
سلام یه اشتباه کوچیک تو نوشتن سوال داشتیدزبان B این گونه است:
[tex]B=\{\lambda\}\cup\{b\}B\cup\{a\}C\cup\{a\}[/tex]
در این صورت عبارت[tex]\{b\}\{b\}^{\ast}\subseteq A[/tex]درست خواهد بود به علاوه همه ی زبان ها منظمند و می توان گرامر منظم زیر را برای آن ها نوشت:
[tex]A\rightarrow bB|aC[/tex]
[tex]B\rightarrow\lambda|bB|aC|a[/tex]
[tex]A\rightarrow bB|aC[/tex]
[tex]B=\{\lambda\}\cup\{b\}B\cup\{a\}C\cup\{a\}[/tex]
در این صورت عبارت[tex]\{b\}\{b\}^{\ast}\subseteq A[/tex]درست خواهد بود به علاوه همه ی زبان ها منظمند و می توان گرامر منظم زیر را برای آن ها نوشت:
[tex]A\rightarrow bB|aC[/tex]
[tex]B\rightarrow\lambda|bB|aC|a[/tex]
[tex]A\rightarrow bB|aC[/tex]
ارسال: #۳
RE: دلیل مستقل از متن بودن یک زبان نامعلوم!
(۲۷ خرداد ۱۳۹۳ ۰۸:۵۵ ب.ظ)fatemeh69 نوشته شده توسط: سلام یه اشتباه کوچیک تو نوشتن سوال داشتیدزبان B این گونه است:
[tex]B=\{\lambda\}\cup\{b\}B\cup\{a\}C\cup\{a\}[/tex]
در این صورت عبارت[tex]\{b\}\{b\}^{\ast}\subseteq A[/tex]درست خواهد بود به علاوه همه ی زبان ها منظمند و می توان گرامر منظم زیر را برای آن ها نوشت:
[tex]A\rightarrow bB|aC[/tex]
[tex]B\rightarrow\lambda|bB|aC|a[/tex]
[tex]A\rightarrow bB|aC[/tex]
شما از کجا مطمئنید؟
تستی که من از پوران دیدم دقیقا عین عبارتیه که نوشتم.
ارسال: #۴
RE: دلیل مستقل از متن بودن یک زبان نامعلوم!
(۲۹ خرداد ۱۳۹۳ ۰۸:۱۴ ب.ظ)ana9940 نوشته شده توسط:(27 خرداد ۱۳۹۳ ۰۸:۵۵ ب.ظ)fatemeh69 نوشته شده توسط: سلام یه اشتباه کوچیک تو نوشتن سوال داشتیدزبان B این گونه است:
[tex]B=\{\lambda\}\cup\{b\}B\cup\{a\}C\cup\{a\}[/tex]
در این صورت عبارت[tex]\{b\}\{b\}^{\ast}\subseteq A[/tex]درست خواهد بود به علاوه همه ی زبان ها منظمند و می توان گرامر منظم زیر را برای آن ها نوشت:
[tex]A\rightarrow bB|aC[/tex]
[tex]B\rightarrow\lambda|bB|aC|a[/tex]
[tex]A\rightarrow bB|aC[/tex]
شما از کجا مطمئنید؟
تستی که من از پوران دیدم دقیقا عین عبارتیه که نوشتم.
خوب تست کنکوره. سالش هم که نوشتید. ممکنه بعضی کتابا اشتباه نوشته باشن.
ارسال: #۵
RE: دلیل مستقل از متن بودن یک زبان نامعلوم!
ارسال: #۶
RE: دلیل مستقل از متن بودن یک زبان نامعلوم!
۰
ارسال: #۷
RE: دلیل مستقل از متن بودن یک زبان نامعلوم!
سلام. نال زیرمجموعه B,C میشه ولی زیرمجموعه A نمیتونه باشه. پس ۱ و ۲ غلطن.
به نظر من همشون منظمن. چون همشون رو میشه با یه گرامر چپ خطی نوشت. ولی [tex]\{b\}\{b\}^*[/tex] زیرمجموعه A نیست. عبارتها رو درست نوشتید؟
به نظر من همشون منظمن. چون همشون رو میشه با یه گرامر چپ خطی نوشت. ولی [tex]\{b\}\{b\}^*[/tex] زیرمجموعه A نیست. عبارتها رو درست نوشتید؟
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close