سلام.
فرض کنید [tex]A\subseteq\{0,1\}^{\ast}[/tex] یک زبان منظم و [tex]S\subseteq\{0,1\}^{\ast}[/tex] یک مجموعه دلخواه باشد.
قرار دهید [tex]L_{A,S}\: =\: \{x\: \mid\: (\exists y\: \in\: A) \: \: \: xy\in S\}[/tex] . کدام گزینه درباره [tex]L_{A,S}[/tex] همواره صحیح است؟
۱- منظم است.
۲-نه مستقل از متن است ، نه منظم.
۳-مستقل از متن است،ولی مستقل از متن قطعی نیست.
۴-مستقل از متن است ، ولی منظم نیست.
با تشکر.
سلام. درنظر بگیرید:
[tex]A=\{ a\}[/tex]
[tex]S=\{ b^na^nb^na\}[/tex]
در نتیجه داریم:
[tex]L_{A,S}=\{b^na^nb^n\}[/tex]
گزینه ۲ میشه.
(۱۶ اسفند ۱۳۹۴ ۰۳:۳۶ ق.ظ)Jooybari نوشته شده توسط: سلام. درنظر بگیرید:ممنونم از پاسختون آقای جویباری.
[tex]A=\{ a\}[/tex]
[tex]S=\{ b^na^nb^na\}[/tex]
در نتیجه داریم:
[tex]L_{A,S}=\{b^na^nb^n\}[/tex]
گزینه ۲ میشه.
پس منظور سوال،همون خارج قسمت راست منظم هستش؟
خب اگه اینجور باشه،اگه ما S رو یک زبان منظم در نظر بگیریم،جواب هم منظم میشه!
و اگه S رو یه زبان مستقل از متن در نظر بگیریم،جواب هم مستقل از متن میشه!
شما S رو یک زبان وابسته به متن در نظر گرفتید،خب جوابشم وابسته به متن میشه.
من واقعا متوجه نشدم چرا ۲ درسته
(۱۶ اسفند ۱۳۹۴ ۰۵:۰۰ ق.ظ)IranianWizard نوشته شده توسط:(16 اسفند ۱۳۹۴ ۰۳:۳۶ ق.ظ)Jooybari نوشته شده توسط: سلام. درنظر بگیرید:ممنونم از پاسختون آقای جویباری.
[tex]A=\{ a\}[/tex]
[tex]S=\{ b^na^nb^na\}[/tex]
در نتیجه داریم:
[tex]L_{A,S}=\{b^na^nb^n\}[/tex]
گزینه ۲ میشه.
پس منظور سوال،همون خارج قسمت راست منظم هستش؟
خب اگه اینجور باشه،اگه ما S رو یک زبان منظم در نظر بگیریم،جواب هم منظم میشه!
و اگه S رو یه زبان مستقل از متن در نظر بگیریم،جواب هم مستقل از متن میشه!
شما S رو یک زبان وابسته به متن در نظر گرفتید،خب جوابشم وابسته به متن میشه.
من واقعا متوجه نشدم چرا ۲ درسته
خوب ذکر کرده که S دلخواهه. اگه لزوماً منظم یا مستقل از متن بود اون موقع گزینه ۲ اشتباه بود. در این مثال به نظرم جواب همینه.