سلام. یکم روش کار کنید. abbba و bbaaabb رو قبول نمیکنه.

(۰۲ دى ۱۳۹۱ ۱۱:۵۲ ب.ظ)Jooybari نوشته شده توسط:  سلام. یکم روش کار کنید. abbba و bbaaabb رو قبول نمیکنه.

abbba رو قبول می کنه. اما دومی رو نه.
فعلا پاک می کنم تا بعد دوباره ویرایش کنم.
ممنون.

سلام
اینم گرامری هست که من برای این زبان نوشتم

[tex]S\rightarrow ASB/a/b[/tex]
[tex]A\rightarrow abA/baA/aA/BA/\lambda[/tex]
[tex]B\rightarrow bB/AB/\lambda[/tex]

توضیحات
-اگر در رشته نهایی تعداد a بیشتر بود، در خط اول برای برداشتن S و رفتن به خط های بعدی گرامر از a استفاده می کنیم اگر b بیشتر بود از b
-متغییر A برای تولید a در نظر گرفته شده و متغییر B برای تولید b ( حالاتی که تعدادی ab و یا ba پشت سرهم در رشته نهایی داریم، از متغییر A برای تولید این حالات استفاده می شود)

-با قواعد
[tex]A\rightarrow BA[/tex]
و
[tex]B\rightarrow AB[/tex]

بین دو خط آخر گرامر سوئیچ می کنیم و هرجانیاز باشه a کوچک یا b کوچک تولید می کنیم.

سلام.

ممنون. اول فکر می کردم bbaaabb رو تولید نمی کنه، اما روش تولیدش ۸ خان رستمه.
s---> BbB ---> bB ---> bBB ---> bbBaB ---> bbaB ---> bbaaBb ---> bbaaaBbb ---> bbaaabb

دمت گرم، اینو از کجا آوردی

چون قرار بود تعداد a و b حداقل یکی اختلاف داشته باشن، دوتا غیرپایانه A و B تعریف کردم. توی A تعداد a ها کمتر از b ها نیست و B هم تعداد b ها کمتر از a ها نیست. اون a یا b اضافه هم برای اون حداقل اختلافه. و باید درنظر بگیرید که اگه از A->AA استفاده نکنید توی تولید رشته هایی که هم با b شروع میشن و هم به b ختم میشن به مشکل میخورید. درضمن اگه تعداد a ها با b های A و B نتونن برابر باشن، وقتی از A->AA استفاده میکنید توی پذیرش رشته های با اختلاف ۱ به مشکل میخورید.

من فکر می کنم اگه a ها و b ها برابر نباشند و w عضو *(a,b) باشه، L نه منظم هست نه مستقل از متن.
DFA که نمیشه رسم کرد مشخصه.
PDA رو واسه این شک دارم که نمیشه رسم کرد که برای بررسی بزرگتر یا کوچکتر بودن تعداد a و b نسبت به هم باید حافظه ی بی شمار داشت.
زیرا مثلا ممکنه بشه گفت تعداد a ها یکی بیشتر از b ها باشه ولی وقتی تعداد a و b متغیر هست ممکنه مثلا ۲ یا ۳ یا ۴ یا .... تا a از b بیشتر داشته باشیم یا برعکس.
و چون شرط ثابتی نداریم کار شدنی نیست.البته به نظر من با یک پشته این کار امکان پذیر نیست.
به نظرم متناقض هست و مثال های جزئی ای که دوستان میزنند به کل مقدم نیست.

به نظر من مستقل از متنه. یه گرامر براش نوشتم. اگه گرامرش رشته ای رو تولید نمیکنه یا اشتباه تولید میکنه بگید.

یه راه اینه که دو حالت بشه؛ یکی n_a>n_b و یکی بالعکس؛ بعد میشه واسه هر حالت جداگونه یه مستقل از متن نوشت؛ مثلا برای اولی:
[tex]S1\rightarrow aS_1|aS|SS_1[/tex]
که S همون n_a=n_b رو تولید میکنه:
[tex]S\rightarrow aSb|bSa|SS|\lambda[/tex]
برای دومی هم کافیه تو خط اول به جای S_1 بزارید S_2 و به جای a هم b؛
جواب نهایی اجتماع این دو حالت میشه:
[tex]A\rightarrow S_1|S_2[/tex]

(۳۰ دى ۱۳۹۱ ۰۳:۰۹ ب.ظ)csharpisatechnology نوشته شده توسط:  PDA رو واسه این شک دارم که نمیشه رسم کرد که برای بررسی بزرگتر یا کوچکتر بودن تعداد a و b نسبت به هم باید حافظه ی بی شمار داشت.

چک کردن این حالت کارو سخت میکنه؛ بهتره فقط مراقب حالت تساوی باشید؛ یعنی اگه بالای پشته z بود و ورودی تا آخر پردازش شده، ماشین در حالت غیر پایانی قرار داشته باشه؛ مثلا از q0 و z بالای پشته شروع کنید و اولین سمبل ورودی رو پوش کنید؛ بعد از اون به ازای سمبلهای یکسان در ورودی و بالای پشته، یکی به اون سمبل در پشته اضافه، و به ازای سمبل ورودی و پشته مخالف، landa پوش کنید؛ در آخر اگه ورودی تموم بشه (لاندا) و بالای پشته a یا b باشه، برید به qf، در غیر اینصورت (یعنی بالای پشته نه a و نه b یعنی لاندا باشه) در همون q0 که غیر نهاییه میمونه؛