۱)یک dfa طراحی کنید که رشته های روی {۰و۱} را بپذیرد اگر و فقط اگر مقدار رشته که بصورت نمایش دودویی یک عدد صحیح است به پیمانه‌ی ۸ صفر شود .به عنوان مثال ۱۰۰۰ و ۱۱۰۰۰ که بترتیب اعداد ۸ و ۲۴ را نشان می دهند توسط این dfa پذیرفته شوند.
۲)آیا زبان زیر منظم است؟اگر هست dfa آن را رسم کنید و اگر نیست با لم تزریق ثابت کنید.
[tex]L={w_1\subset w_2:w_1,w_2\in \left( a,b \right ),w_1\neq w_2}[/tex]
۳)برای هریک از حالتهایی که در dfa زیر داریم هربار یک یال را برداشته برای dfa حاصل عمل کاهش state را انجام داده وdfa کاهش یافته را رسم و گرامر معادل آن حالت را بنویسید در مجموع ۷ حالت داریم(هر یک با حذف یک یال ایجاد میشود.)
این شکل سوال ۳
[img]
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
[/img]
این هم حالت حل شده شکل اصلی بدون حذف هیچ یالی:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
البته شما باید مثلا برای بار اول یال a را حذف سپس کاهش استیت را انحام داده و دی اف ای کشیده و گرامر حاصل را بنویسید.
اول بگو "به پیمانه ۸ صفر شود" یعنی چی؟
(۳۱ اردیبهشت ۱۳۹۰ ۰۱:۳۳ ب.ظ)behdad نوشته شده توسط: اول بگو "به پیمانه ۸ صفر شود" یعنی چی؟
یعنی اینکه بر ۸ قابل تقسیم باشد.
مثل اعداد: ۸ - ۱۶ - ۲۴ - ۳۲ - ...
اعداد بخش پذیر بر ۸ یه این چنین فرم دودویی دارند ۱۰۰۰و۱۰۰۰۰ و۱۱۰۰۰ و ۱۰۰۰۰۰ و ....
(۳۱ اردیبهشت ۱۳۹۰ ۰۵:۳۷ ب.ظ)afagh1389 نوشته شده توسط: اعداد بخش پذیر بر ۸ یه این چنین فرم دودویی دارند ۱۰۰۰و۱۰۰۰۰ و۱۱۰۰۰ و ۱۰۰۰۰۰ و ....
یعنی اینکه کافی است ۳ بیت کوچکتر عدد مورد نظر، صفر باشند. سایر بیت‌ها اهمیتی ندارد که صفر یا یک باشند.
بله چون ۸=۳^۲ پس به غیر از ۱و۲و۴ بقیه بر ۸ بخش پذیرند و جمع دو عددی که بر ۸ بخش پذیرند باز بر ۸ بخش پذیره.
منظورم از بقیه ۸ و ۱۶و ۳۲و ۶۴ و .... است.
سوال دوم منظم نیست دیگه، درست میگم؟
w2=a^m b^m
w1=a^m b
y=a^L
x=a^m-L
z=b
وقتی i=2 باشه
w(i)=a^(m+L) b
که دیگه این رشته زیر مجموعه w2 نیست.