۱/یک زبان منظم است اگر توسط یک dfa پذیرش شود وبرای یک زبان منظم میتوان nfa رسم کرد ولی پذیرش یک زبان توسط nfa تضمینی بر منظم بودن ان نیست.درسته؟
۲/از ما خواسته شده به عنوان مثال برای زبانی که تعداد a,b هردو جداگانه زوج باشد روی {a,b}یک عبارت منظم و یک dfa رسم کنیم.راه اصولی برای حل چنین سوالاتی چیست؟رشته های مختلفی از زبان تولید و بر اساس ان و تجارب قبلی عمل کنیم و یا راه حل تستی و میانبری وجود دارد؟
۳/کلیه راههای اثبات منظم بودن یک زبان را نام ببرید؟و بهترین راه برای تشخیص منظم بودن کدام است؟
ممنون میشم راهنمایی کنید
(۰۷ دى ۱۳۹۰ ۱۲:۲۵ ق.ظ)navid-p نوشته شده توسط: ۱/یک زبان منظم است اگر توسط یک dfa پذیرش شود وبرای یک زبان منظم میتوان nfa رسم کرد ولی پذیرش یک زبان توسط nfa تضمینی بر منظم بودن ان نیست.درسته؟در مورد قسمت اول اینو میدونیم که هر nfa میتونه به یک dfa تبدیل بشه پس اگر برای یک زبان nfa رسم کردی می تونی این nfa رو به یه dfa lمعادل تبدیل کنی پس تونستی برای زبان dfa بکشی پس هر چی با nfa بکشی هم منظمه
۲/از ما خواسته شده به عنوان مثال برای زبانی که تعداد a,b هردو جداگانه زوج باشد روی {a,b}یک عبارت منظم و یک dfa رسم کنیم.راه اصولی برای حل چنین سوالاتی چیست؟رشته های مختلفی از زبان تولید و بر اساس ان و تجارب قبلی عمل کنیم و یا راه حل تستی و میانبری وجود دارد؟
۳/کلیه راههای اثبات منظم بودن یک زبان را نام ببرید؟و بهترین راه برای تشخیص منظم بودن کدام است؟
ممنون میشم راهنمایی کنید
در مور قسمت سوم هم تا اونجایی که من میدونم یکی اینه که بتونی براش dfa یا nfa بکشی،بعد اینکه به طور کلی زبان های متناهی منظم هستند پس هر کجا دیدی متناهیه حتما منظمه، راه دیگه اینه که بتونی براش گرامر منظم بنویسی
دوستان اگر کسی در مورد سوال ۲و۳ اطلاعات کاملتری داره لطفا پاسخ بده
مثل طراحی مدار های ترتیبی توی مدار منطقی در نظر بگیرین. هر حالت توی عکس زیر دو تا عدد تشکیل شده. صفر یعنی زوج هست و یک یعنی فرد. عدد سمت چپ زوج یا فرد بودن a در یک حالت و عدد سمت راست بیانگر همین وضعیت برای تعداد bها هست. خوب چون شما الان تعداد زوج a و b را می خوای حالت صفر صفر میشه پایانی.
قیافه‌ی سوالا به مشق می خوره
در مورد سوال سه نوشتن عبارت منظم، کشیدن اتوماتا، نوشتن گرامر خطی
سوال دو هم راهی که آقای pos فرمودن صحیحه اصولا این روش برای تمام بخش پذیری‌ها کار می کنه .
یه سوال دیگه.ایا بدون بلد بودن لم تزریق میشه تمام سولات مرتبط به زبانها رو حل کرد؟راه ساده تری وجود داره برای تشخیص؟
زبانها و گرامرهای مبهم جزو ازمون هست؟رفع ابهام و گرامرهای ساده چطور؟
برای تبدیل گرامر مستقل از متن به فرم نرمال چامسکی باید ۱/قوانین lambda
۲/قوانین یکه و۳/قوانین غیر مفید حذف شوند. ایا این مراحل برای تبدیل به فرم گریباخ نیز وجود دارد؟
واگر جواب مثبته پس تمرین ۱۰ بخش ۲-۶ در حل تمرین اشتباه حل شده.
S_>aSb/aS/aaS
Sاینجا غیر مفید نیست؟