(۱۳ آبان ۱۳۹۲ ۱۲:۳۴ ق.ظ)zimenswall نوشته شده توسط:  اول از تمام رشته های زبان اول که آخرشون رشته a دارن را ، فقط a آخرشون را حذف میکنی. یعنی رشته های داخل زبان دوم را از آخر رشته های زبان اول میچینی
[tex]\left \{ \lambda,ab,aab,ba,bab \right \}[/tex]

تقسیم شما مشکل داره. با خذف a از زبان ۱ به مجموعه [tex]\left \{ \lambda,ba,bab \right \}[/tex] میرسیم. a رو از رشته هایی که به a ختم میشن رو حذف میکنیم. اگه آخر یه رشته a نداشته باشه به تهی میرسه.

(۱۳ آبان ۱۳۹۲ ۰۵:۵۰ ب.ظ)Jooybari نوشته شده توسط:  

(13 آبان ۱۳۹۲ ۱۲:۳۴ ق.ظ)zimenswall نوشته شده توسط:  [tex]\left \{ \lambda ,a,aa,baa,baba ,ab,aab,ba,bab \right \}[/tex]

تقسیم شما مشکل داره. با خذف a از زبان ۱ به مجموعه [tex]\left \{ \lambda,ba,bab \right \}[/tex] میرسیم. a رو از رشته هایی که به a ختم میشن رو حذف میکنیم. اگه آخر یه رشته a نداشته باشه به تهی میرسه.

پس یه بار دیگه حلش میکنم
[tex]L1 = {\lambda ,a,ab,aab,baa,baba}[/tex]
[tex]L2 = {a,b}[/tex]

و میخواهیم
[tex](L1/(L1/L2))[/tex]

حذف a
[tex]\left \{ \lambda,ba,bab \right \}[/tex]

حذف b
[tex]\left \{ a,aa\right \}[/tex]

پس زبان [tex]L1/L2[/tex] میشه
[tex]\left \{ \lambda ,a,aa ,ba,bab \right \}[/tex]


حالا مرحله دوم (تقسیم قسمت دوم)
۱/ لاندا
[tex]\left \{ \lambda ,a,ab,aab,baa,baba \right \}[/tex]

۲/ a
[tex]\left \{ \lambda,ba,bab \right \}[/tex]

۳/ aa
[tex]\left \{ b \right \}[/tex]

۴/ ba
[tex]\left \{ ba \right \}[/tex]

۵/ bab
[tex]\left \{ \right \}[/tex]


و مجموع ۵ مجموعه قبلی نهایتا میشه
[tex]\left \{\lambda ,a,ab,aab,baa,baba,ba, bab,b \right \}[/tex]
که با اون قبلی در یک aa تفاوت داشت.
پس تا حالا شانس آوردم که اون دو سه تا تستی که زدم اشتباه نشده. با راه حل غلط جواب درست میزدم

توی تستی که زده بودم دقیقتر نگاه کردم دیدم من جواب را فقط از روی شمارش بدست آوردم (تعداد هر دو تا مجموعه که بدست آوردم ۹ تا بوده) و خیلی روی رشته ها دقیق نشده بودم.
تشکر از آقای jooybary که خطای منو گوشزد کردند.
من که دیگه کامل فهمیدم چی شد. انشاا.. دوستان هم فهمیده باشن

اگه L1 باشه این:
L1:{ali,alireza,ahmadreza,hamidreza,hasan} X
L2:{hamid,ahmad,reza,hasan} X

حالا مثلن بخوایم نسبت راست دو رشته L1/L2 رو بدست بیاریم، باید یکی به یکی تست کنیم و رشته ها رو تقسیم کنیم به هم و هرکدوم رو ساده کنیم.
ali/hamid نداره
ali/ahmad این نداره
ali/reza اینم نداره چون نسبت راست هست
ali/hasan نداره
میریم سراغ بعدی یعنی علیرضا:
alireza/hamid نداره
alireza/ahmad نداره
alireza/reza این داره میتونیم رضا بالایی رو با با رضای پایین بزنیم و میمونه فقط ali
alireza/hasan نداریم
رشته بعدی احمدرضا:
ahmadreza/hamid نداره
ahmadreza/ahmad نداریم چون رشته راست هست باید اون چیزی که ساده میشه راست باشه ولی اگه نسبت چپ خواسته بود این میتونست قبول بشه.
ahmadreza/reza این قبول میشه و رضای بالا با رضای پایین زده میشه میمونه ahmad
ahmadreza/hasan نداره
رشته بعد یعنی حمیدرضا:
hamidreza/hamid نداره دقت کن نسبت راست هست و فقط میتونی رشته رو از راست ساده کنی.
hamidreza/ahmad نداره
hamidreza/reza قبول میشه و رضای پایین با رضای بالا میره و میمونه hamid
رشته بعدی حسن:
hasan/hamid نداره
hasan/ahmad نداره
hasan/reza نداره
hasan/hasan قبول میشه و میمونه Lambda یعنی رشته بالا رو میتونی Lambda.hasan در نظر بگیری و تقسیمش کنی به حسن.
حالا کل رشته هایی که قبول شد میشه جواب:
L1/L2:{ali,ahmad,hamid,lambda} X
دقت کن این نسبت راست هست،


حالا اگه بخوایم نسبت چپ L1\L2 رو بدست بیاریم:
باز یکی یکی تست میکنیم، اول رشته ali
ali\hamid نداره
ali\ahmad نداره
ali\reza نداره
ali\hasan نداره
رشته بعد alireza
alireza\ahmad نداره
alireza\reza نداره چون نسبت چپ هست و شما فقط میتونی رشته رو از چپ ساده کنی.
alireza\hasan نداره
رشته بعد احمدرضا
ahmadreza\hamid نداره
ahmadreza\ahmad داره - آخ جون احمد بالا رو با پایین میزنیم و فقط میمونه reza
ahmadreza\reza نداره چون نسبت چپ هست...
ahmadreza\hasan نداره
رشته بعدی hamidreza
hamidreza\hamid داره و میمونه reza
hamidreza\ahmad نداره
hamidreza\reza نداره چون نسبت چپ هست
hamidreza\hasan هم نداره.
رشته بعدی hasan
hasan\hamid نداره
hasan\ahmad نداره
hasan\reza نداره
hasan\hasan این داره میتونی رشته بالا رو hasan.lamda در نظر بگیری و حسن رو با حسن بزنی و میمونه Lamda
حالا رشته هایی که قبول شدن میشه جواب:
L1\L2: {reza,reza,lambda} X که میشه یک رضا رو حذف کرد چون تکراریه.

میشه L2/L1 ,L2\L1 رو نیز حساب کرد که زحمتش رو بکش

متاسفانه منطقش رو نفهمیدم

(۱۴ آبان ۱۳۹۲ ۰۷:۴۲ ب.ظ)H-Arshad نوشته شده توسط:  متاسفانه منطقش رو نفهمیدم

خیلی ساده است.
مثلا aba / a
یعنی رشته a را از آخر رشته aba بچین
میشه ab

یا مثلا aabba / bba
چیدن bba از آخر رشته aabba
میشه aa

یا bba / lamda
میشه چیدن لاندا از آخر رشته bba که دقیقا میشه خود رشته bba

یا مثلا bbab / a و abab / bb
این دو تا چون آخرشون با اون رشته ای که قراره بهشون تقسیم بشن یکی نیست پس عملا تقسیمی صورت نمیگیره و جواب تهی میشه (البته اینو خودم بلد نبودم و همینجا یاد گرفتم)

دیگه واضح تر از این نمیشه بگی. یه بار اون مثال بالایی که گفتم را حل کنید، بهتر متوجه میشید

سلام.هنوز منطقش رو متوجه نشدید؟

سلام به همه دوستان.
روش کتاب لینز خیلی خوبه.
همونطور که دوستمون هم گفتند باید برای L1 یه DFAبکشید. حالا خوب دقت کنید: توی این DFA از هر حالت qi که تونستید حداقل با یه رشته از L2 به حالت نهایی برسید، اون qi میشه نهایی.=> بقیه حالات همه غیر نهایی هستند، همه.
اگه سوالی بود در خدمتم.
موفق باشید

سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم

(۲۴ آبان ۱۳۹۲ ۰۷:۵۳ ب.ظ)kaviresabz نوشته شده توسط:  سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم

اگر میشه سوال زیر رو به همین روش کتاب لینز حل کنید و توضیح هم بدید که چطور dfa رو میکشید آخه من هر کاری کردم نتونستم بفهمم که چطور میشه DFA برای خارج قسمت دو زبان رو کشید . ممنون

(۱۴ مرداد ۱۳۹۳ ۰۶:۱۹ ب.ظ)m-355 نوشته شده توسط:  

(24 آبان ۱۳۹۲ ۰۷:۵۳ ب.ظ)kaviresabz نوشته شده توسط:  سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم

اگر میشه سوال زیر رو به همین روش کتاب لینز حل کنید و توضیح هم بدید که چطور dfa رو میکشید آخه من هر کاری کردم نتونستم بفهمم که چطور میشه DFA برای خارج قسمت دو زبان رو کشید . ممنون

(*L1=L(a*baa
(*L2=L(ab
?=L1/L2

سلام تو پیوست راه حل رو گذاشتم
تو مرحله دو الگوریتم رو دی اف ای انجام میشه
یادتون نره همیشه باید دی اف ای داشته باشید و حتما کاهش حالت شده باشه

(۲۴ آبان ۱۳۹۲ ۰۷:۵۳ ب.ظ)kaviresabz نوشته شده توسط:  سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم

سلام.این روش فقط برای زبان های منظم کاربرد داره.که احتمال داره هم خیلی طولانی شه

(۰۱ مهر ۱۳۹۳ ۰۳:۲۱ ب.ظ)miladcr7 نوشته شده توسط:  

(24 آبان ۱۳۹۲ ۰۷:۵۳ ب.ظ)kaviresabz نوشته شده توسط:  سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم

سلام.این روش فقط برای زبان های منظم کاربرد داره.که احتمال داره هم خیلی طولانی شه

سلام به همه دوستان.
بله، این روش مربوط به زبان های منظم هست.
همونطور که دوستمون هم گفتند باید برای L1 یه DFAبکشید. حالا خوب دقت کنید: توی این DFA از هر حالت qi که تونستید حداقل با یه رشته از L2 به حالت نهایی برسید، اون qi میشه نهایی.=> بقیه حالات همه غیر نهایی هستند، همه.
اگه سوالی بود در خدمتم.
موفق باشید