سلام دوستان لطفا درباره این سوال راهنمایی کنید.
گرامر وابسته به متن Gمفروض است:
[tex]S\rightarrow S_{1}B[/tex]
[tex]S_{1}\rightarrow aS_{1}b[/tex]
[tex]bB\rightarrow bbbB[/tex]
[tex]aS_{1}b\rightarrow aa[/tex]
[tex]B\rightarrow \epsilon[/tex]
زبان گرامر G کدام است؟
۱) [tex]\left \{ a^{n 1}b^{n k}|n\geqslant 1,k\geqslant 0\right \}[/tex]
۲) [tex]\left \{ a^{n}b^{k}|n\geqslant 2,k\geqslant 0\right \}[/tex]
۳)[tex]\left \{ a^{n}b^{n 2k}|n\geqslant 2,k\geqslant 0\right \}[/tex]
۴- [tex]\left \{ a^{n 1}b^{n 2k-1}|n\geqslant 1,k\geqslant 0\right \}[/tex]
کتاب گسترش علوم پایه گفته جواب گزینه ۱ هست ولی مثلا گرامر رشته aa رو تولید می کنه ولی به نظر من(شاید هم اشتباه می کنم) زبان گزینه ۱ تولید نمی کنه ، نمی دونم همچین سوال هایی رو از کجا باید فهمید که کدوم گزینه می شه
می دونم وقت نیست ولی اگر تونستید لطف کنید و جواب بدین
این تست سال ۸۹ دقیقا تمرین ۱ از فصل ۲-۱۱ هست و جوابش گزینه ۴ هست نه ۱/
برای اینکه رابطه رو پیدا کنیم اول باید یه سری رشته رو تولید کنیم که با گزینه ها همخونی داشته باشه:
[tex]S\Rightarrow aS_{1}bB\Rightarrow aaS_{1}bbB\Rightarrow ^{*}a^{n}S_{1}b^{n}B\Rightarrow a^{n\dotplus 1}b^{n-1}B[/tex]
که اینجا میتونیم جای B ، لامبدا بذاریم و رشته تولیدی به شکل [tex]a^{n\dotplus 1}b^{n-1}[/tex] باشه
یا اینکه دوباره با جایگزینی bB، مجدد به تولید b های جدید بپردازیم.
که به این شکل در میاد:
[tex]\Rightarrow a^{n\dotplus 1}b^{n-2}bB\Rightarrow a^{n\dotplus 1}b^{n-2}bbbB\Rightarrow a^{n\dotplus 1}b^{n\dotplus 1}B[/tex]
در نتیجه زبان به شکل زیر میشه:
[tex]L=\left \{a^{n\dotplus 1}b^{n\dotplus k },n\geqslant 1, k=-1,1,3,... \right \}=\left \{a^{n\dotplus 1}b^{n\dotplus 2k-1 },n\geqslant 1, k\geq 0 \right \}[/tex]