۰
subtitle
ارسال: #۱
آیا زبان uvwv^R منظمه؟ حل شد
اول بگم که این با سوال قبلی که تو انجمن پرسیدم شرطش فرق داره
زبان [tex]uvwv^{R} : u,v,w\in \left \{ a,b \right \}^{ }, \left | u \right | = \left | v \right | = 2[/tex]
گفته شده مستقل از متنه و نامنظم ولی نظر خودم منظمه.
اون u اول زبان که هیچی. v هم که فقط دو عنصر بیشتر نداره و فقط w میمونه که هر چی میتونه باشه (البته حداقل طولش باید یک باشه).
پس یه nfa میشه براش که u دو عنصر دلخواه بیاد و بعد v چون طول دو داره پس چهار حالت براش هست و بعد w که حداقل یه چیزی بیاد و بعد دوباره برعکس v. شکل nfa که به ذهنم رسید را اینجا گذاشتم
![[تصویر: 216493_Img112.jpg]](https://img.manesht.ir/216493_Img112.jpg)
اگه اشتباه شده لطف کنید کمک کنید.
تشکر
زبان [tex]uvwv^{R} : u,v,w\in \left \{ a,b \right \}^{ }, \left | u \right | = \left | v \right | = 2[/tex]
گفته شده مستقل از متنه و نامنظم ولی نظر خودم منظمه.
اون u اول زبان که هیچی. v هم که فقط دو عنصر بیشتر نداره و فقط w میمونه که هر چی میتونه باشه (البته حداقل طولش باید یک باشه).
پس یه nfa میشه براش که u دو عنصر دلخواه بیاد و بعد v چون طول دو داره پس چهار حالت براش هست و بعد w که حداقل یه چیزی بیاد و بعد دوباره برعکس v. شکل nfa که به ذهنم رسید را اینجا گذاشتم
اگه اشتباه شده لطف کنید کمک کنید.
تشکر
۱
ارسال: #۲
RE: آیا زبان uvwv^R منظمه؟ حل شد
کجاش حل شد اقا جان ؟ از انجمن مانشت بعیده 
پس چرا تذکر ندادید که NFA رسم شده غلطه ؟ از قسمت w نباید به هم متصل می شدن
الان ممکنه از سمت چپ از مسیر بالاتر وارد بشیم ولی از سمت راست ( بعد از مشاهده w ) از مسیر دومی از بالا خارج شیم
خوب این جوری دیگه معکوس aa رو نمی بینیم دیگه!!!
یعنی برای هر مسیر که رسم کردیم باید w رو جدا گانه تو همون مسیر فرض می کردیم نه که از قسمت w مسیر ها رو به هم وصل کنیم
تازه با شرط |w| = دو هم همچنان این زبان منظمه ها
پس چرا تذکر ندادید که NFA رسم شده غلطه ؟ از قسمت w نباید به هم متصل می شدن
الان ممکنه از سمت چپ از مسیر بالاتر وارد بشیم ولی از سمت راست ( بعد از مشاهده w ) از مسیر دومی از بالا خارج شیم
خوب این جوری دیگه معکوس aa رو نمی بینیم دیگه!!!
یعنی برای هر مسیر که رسم کردیم باید w رو جدا گانه تو همون مسیر فرض می کردیم نه که از قسمت w مسیر ها رو به هم وصل کنیم
تازه با شرط |w| = دو هم همچنان این زبان منظمه ها
ارسال: #۳
RE: آیا زبان uvwv^R منظمه؟ حل شد
(۲۸ مهر ۱۳۹۲ ۱۰:۳۶ ب.ظ)ایزدی نوشته شده توسط: کجاش حل شد اقا جان ؟ از انجمن مانشت بعیده
پس چرا تذکر ندادید که NFA رسم شده غلطه ؟ از قسمت w نباید به هم متصل می شدن
الان ممکنه از سمت چپ از مسیر بالاتر وارد بشیم ولی از سمت راست ( بعد از مشاهده w ) از مسیر دومی از بالا خارج شیم
خوب این جوری دیگه معکوس aa رو نمی بینیم دیگه!!!
یعنی برای هر مسیر که رسم کردیم باید w رو جدا گانه تو همون مسیر فرض می کردیم نه که از قسمت w مسیر ها رو به هم وصل کنیم
تازه با شرط |w| = دو هم همچنان این زبان منظمه ها
ممنون تذکر دادید. من در پست اول هم گفته بودم اگر جایی مشکل داره دوستان بگن. من خودم اونموقع که کشیدم فقط حواسم به پذیرش رشته بود به عدم پذیرش رشته های خارج از زبان دقت نداشتم.
اما شرط این مسئله w=2 و u=2 بوده که در اون کتابی که خوندم اشتباه ذکر شده بود.
با شرطی که گفته شد (w=2 و u=2) زبان مستقل از متنه. چون بین رشته v و معکوسش دو کاراکتر وجود داره و این باعث میشه زبان منظم نباشه. اگر دلیلی بر منظم بودنش دارید بفرمایید. همونجور که من و دوستان نمودار را اشتباه رسم کردم شاید در تحلیل جواب این سوال هم اشتباه کرده باشیم
۰
ارسال: #۴
RE: آیا زبان uvwv^R منظمه؟
(۰۷ مهر ۱۳۹۲ ۰۸:۴۱ ب.ظ)zimenswall نوشته شده توسط: اول بگم که این با سوال قبلی که تو انجمن پرسیدم شرطش فرق داره
زبان [tex]uvwv^{R} : u,v,w\in \left \{ a,b \right \}^{ }, \left | u \right | = \left | v \right | = 2[/tex]
گفته شده مستقل از متنه و نامنظم ولی نظر خودم منظمه.
اون u اول زبان که هیچی. v هم که فقط دو عنصر بیشتر نداره و فقط w میمونه که هر چی میتونه باشه (البته حداقل طولش باید یک باشه).
پس یه nfa میشه براش که u دو عنصر دلخواه بیاد و بعد v چون طول دو داره پس چهار حالت براش هست و بعد w که حداقل یه چیزی بیاد و بعد دوباره برعکس v. شکل nfa که به ذهنم رسید را اینجا گذاشتم
اگه اشتباه شده لطف کنید کمک کنید.
تشکر
این زبان منظمه؛
چیزی که شما دیده بودید احتمالا با شرط ۲ = |u| = |w| بوده که مستقل از متنه؛
ارسال: #۵
RE: آیا زبان uvwv^R منظمه؟
(۰۷ مهر ۱۳۹۲ ۱۰:۲۹ ب.ظ)Ghiasoddin نوشته شده توسط:(07 مهر ۱۳۹۲ ۰۸:۴۱ ب.ظ)zimenswall نوشته شده توسط: اول بگم که این با سوال قبلی که تو انجمن پرسیدم شرطش فرق داره
زبان [tex]uvwv^{R} : u,v,w\in \left \{ a,b \right \}^{ }, \left | u \right | = \left | v \right | = 2[/tex]
گفته شده مستقل از متنه و نامنظم ولی نظر خودم منظمه.
اون u اول زبان که هیچی. v هم که فقط دو عنصر بیشتر نداره و فقط w میمونه که هر چی میتونه باشه (البته حداقل طولش باید یک باشه).
پس یه nfa میشه براش که u دو عنصر دلخواه بیاد و بعد v چون طول دو داره پس چهار حالت براش هست و بعد w که حداقل یه چیزی بیاد و بعد دوباره برعکس v. شکل nfa که به ذهنم رسید را اینجا گذاشتم
اگه اشتباه شده لطف کنید کمک کنید.
تشکر
این زبان منظمه؛
چیزی که شما دیده بودید احتمالا با شرط ۲ = |u| = |w| بوده که مستقل از متنه؛
پس چیزی که من تو ذهن داشتم درست بوده.
البته تو کتابی که خوندم v و u را برابر دو گذاشته بوده و به قول شما شاید اشتباه کردن و باید w =2 میشده که در این صورت نامنظم و مستقل از متن میشده.
تشکر
۰
ارسال: #۶
RE: آیا زبان uvwv^R منظمه؟ حل شد
خواهش می کنم
NFA رو رسم کردم حالا ک NFA داریم یقینا این زبان منظمه
اما به عنوان ی نکته می شه گفتش که اگر تعداد محدودی حرف به زبان اضافه بشه در واقع یه زبان منظم بهش اضافه شده و حالا ک زبان اولیه منظمه پس زبان در نهایت همچنان منظمه
در ضمن vR رو هم اشتباه رسم کرده بودید ک می دونم از عجله بوده اما تغییرش دادم ک در نهایت برای بقیه شک ایجاد نشه
NFA رو رسم کردم حالا ک NFA داریم یقینا این زبان منظمه
اما به عنوان ی نکته می شه گفتش که اگر تعداد محدودی حرف به زبان اضافه بشه در واقع یه زبان منظم بهش اضافه شده و حالا ک زبان اولیه منظمه پس زبان در نهایت همچنان منظمه
در ضمن vR رو هم اشتباه رسم کرده بودید ک می دونم از عجله بوده اما تغییرش دادم ک در نهایت برای بقیه شک ایجاد نشه
ارسال: #۷
RE: آیا زبان uvwv^R منظمه؟ حل شد
(۲۸ مهر ۱۳۹۲ ۱۱:۵۶ ب.ظ)ایزدی نوشته شده توسط: خواهش می کنم
NFA رو رسم کردم حالا ک NFA داریم یقینا این زبان منظمه
اما به عنوان ی نکته می شه گفتش که اگر تعداد محدودی حرف به زبان اضافه بشه در واقع یه زبان منظم بهش اضافه شده و حالا ک زبان اولیه منظمه پس زبان در نهایت همچنان منظمه
در ضمن vR رو هم اشتباه رسم کرده بودید ک می دونم از عجله بوده اما تغییرش دادم ک در نهایت برای بقیه شک ایجاد نشه
تشکر
ولی شرایط گرامر را اشتباه متوجه شدید
گرامر مد نظر ما این بود که مستقل از متنه
[tex]uvwv^{R} : u,v,w\in \left \{ a,b \right \}^{ }, \left | u \right | = \left | w \right | = 2[/tex]
طول رشته v نامحدوده
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close