سلام دوستان
این سوالی که اینجا مینویسم از تمرینای فصل ۵ هستش، همون تمرینای اول فصل، سوال ۷ قسمت و که به این صورته:
گرامر مستقل از متن برای زبان زیر میخواد اینم زبانش:
L={ w ϵ {a ,b}* n_a(v) ≥ n_b(v) وقتی v هر پیشوندی از w باشد}
تشکر دوستان
فرض کنیم تعداد a و b ها در w مساوی باشه:
[tex]n_a(w)=n_b(w),n_a(v)\geq n_b(v)[/tex]
با این فرض میشه گرامر زیر رو نوشت:
[tex]S\rightarrow aSb|SS|\lambda[/tex]
حالا برای اینکه فرضی که کردیم رو برداریم کافیه قاعده
[tex]S\rightarrow aS[/tex]
رو اضافه کنیم؛
سلام. وقتی v برابر نال (رشته بطول صفر) درنظر گرفته بشه شرط مسئله برقراره. جواب مسئله میشه [tex]{\sum}^*[/tex].
سلام دوستان
ممنون به خاطرجوابای واقعا خوبتون. به نظرم جواب دوست خوبمون Ghiasoddin درست باشه.
تشکر بچه ها.
فکر کنم منظور سوالتون رو متوجه نشدم. اگه قرار باشه به ازای تمام مقادیر v رابطه [tex]n_a(v)\geq n_b(v)[/tex] برقرار باشه جواب آقای Ghiasoddin کاملاً درسته. چیزی که من درنظر گرفته بودم شرط وجودی برای v بود. یعنی یک پیشوند از w مثل v وجود داشته باشه که شرط مسئله رو داشته باشه.
این سوال، جزء سوالای کنکور سال ۹۱ بوده. البته بصورت زیر مطرح شده.
[tex]L = \left \{ w|w\, \epsilon(a,b)^{*} \right \}[/tex] بطوری که در هر پیشوند دلخواه از W، تعداد aها حداقل به اندازه تعداد bها باشد.
جواب بصورت زیر است :
[tex]S\rightarrow aS | aSbS |\varepsilon[/tex]
S دوم بخاطر این هست که بعد از b هم باید رشته توسعه پیدا کند.