صفحه‌ها: ۱ ۲
سلام
متاسفانه اصلا عملگر تقسیم در زبان رو نمیفهمم
L1/L2
منم مثل شما در این مورد زیاد مشکل داشتم ولی با این مثال که تو کتاب پارسه بود تقریبا مشکلم حل شد.
البته راه حل من نمیدونم درسته یا نه، ولی جوابی که بدست آوردم درست بود
خیلی ساده است.
مثلا aba / a
یعنی رشته a را از آخر رشته aba بچین
میشه ab
یا مثلا aabba / bba
چیدن bba از آخر رشته aabba
میشه aa
یا bba / lamda
میشه چیدن لاندا از آخر رشته bba که دقیقا میشه خود رشته bba
یا مثلا bbab / a و abab / bb
این دو تا چون آخرشون با اون رشته ای که قراره بهشون تقسیم بشن یکی نیست پس عملا تقسیمی صورت نمیگیره و جواب تهی میشه (البته اینو خودم بلد نبودم و همینجا یاد گرفتم)
دیگه واضح تر از این نمیشه بگی. یه بار این مثال را حل کنید، بهتر متوجه میشید
فرض کن
[tex]L1 = {\lambda ,a,ab,aab,baa,baba}[/tex]
[tex]L2 = {a,b}[/tex]
و شما اینو میخوای
[tex](L1/(L1/L2))[/tex]
اول از تمام رشته های زبان اول که آخرشون رشته a دارن را ، فقط a آخرشون را حذف میکنی. یعنی رشته های داخل زبان دوم را از آخر رشته های زبان اول میچینی
حذف 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 داره - آخ جون
احمد بالا رو با پایین میزنیم و فقط میمونه rezaahmadreza\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 رو نیز حساب کرد که زحمتش رو بکش
(۱۳ آبان ۱۳۹۲ ۱۲:۳۴ ق.ظ)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 که خطای منو گوشزد کردند.
من که دیگه کامل فهمیدم چی شد. انشاا.. دوستان هم فهمیده باشن
متاسفانه منطقش رو نفهمیدم
(۱۴ آبان ۱۳۹۲ ۰۷:۴۲ ب.ظ)H-Arshad نوشته شده توسط: متاسفانه منطقش رو نفهمیدم
خیلی ساده است.
مثلا aba / a
یعنی رشته a را از آخر رشته aba بچین
میشه ab
یا مثلا aabba / bba
چیدن bba از آخر رشته aabba
میشه aa
یا bba / lamda
میشه چیدن لاندا از آخر رشته bba که دقیقا میشه خود رشته bba
یا مثلا bbab / a و abab / bb
این دو تا چون آخرشون با اون رشته ای که قراره بهشون تقسیم بشن یکی نیست پس عملا تقسیمی صورت نمیگیره و جواب تهی میشه (البته اینو خودم بلد نبودم و همینجا یاد گرفتم)
دیگه واضح تر از این نمیشه بگی. یه بار اون مثال بالایی که گفتم را حل کنید، بهتر متوجه میشید
سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم
(۲۰ آبان ۱۳۹۲ ۱۲:۳۷ ق.ظ)cat نوشته شده توسط: یک روش ساده: L1/L2دوست عزیز اشتباه حساب کردی جواب این میشه
پیشوندهای یک رشته که می دانید چیست؟بله
پسوندهای یک رشته را هم حتما می دانید چیست؟بله
خوب.
حال به این شیوه عمل کنید:
۱/ ابتدا کلیه ی پیشوند های رشته های زبان L1 را بنویسید.
۲/ سپس از بین مجموعه ی این پیشوند ها فقط آنهایی را اتخاب کنید که پسوندی از آنها در L2 وجود دارد. و تمام.
مثال: L1/L2
L1={a,aba,bb} , L2={a,ba} l
۱/پیشوند های رشته های زبان L1:
a , ab , aba, b , bb , LANDA
۲/ حال از رشته های فوق فقط آنهایی را انتخاب می کنیم که پسوندی از آنها در L2 موجود باشد.
a , aba , LANDA
و تمام. L1/L2 بدست آمد.
a,ab,landa
با احترام به همه دوستان ولی با خوندن پست هاتون باید بگم همه تون بجز یکی مفهوم خارج قسمت راست رو اشتباه فهمیدید....
این دو مثال رو از روی لینز بخونید یا خودتون حل کنید این دو مثال دقیقا نشون میده که در مورد خارج قسمت راست اشتباه یاد گرفتید....
{L1={a^nb^m:n>=1,m>=0ًًٌٌٍ}U{ba
{L2={b^m:m>=1
{L1/L2={a^nb^m:n>=1,m>=0ًًٌٌٍ
حالا اگه در زبانL2 وmبزرگتر مساوی صفر بود انوقت L1/L2 برابر چی مشید؟
خودتون حل کنید ولی جواب اینه که دقیقا خود زبان L1 میشه یعنی در اینجا ba هم جزو L1/L2 خواهد بود در صورتی که وقتی m بزرگتر مساوی یک بود ba جزو L1/L2 نبود گه بتونید این دو مثال رو بفهمین انوقت مفهوم خارج قسمت راست رو کاملا فهمیدید.....بازم اگه خواستید میتونم چیزی که خودم فهمیدم رو براتون توضیح بدم ولی اگه خودتون با این دو مثال متوجه بشین خیلی بهتره.....
(۰۴ آذر ۱۳۹۲ ۱۰:۰۷ ب.ظ)agwdt2012 نوشته شده توسط: دوست عزیز اشتباه حساب کردی جواب این میشه
a,ab,landa
در مثال فوق در قسمت مشاده و مقایسه بی دقتی شد و ab بجای aba نوشته شد.
اما کلیت روش گفته شده صحیح است.
در ضمن پیشنهاد می کنم در تحلیلتان از افراد و نوشته ها تجدید نظر کنید.
در پست فوق من روشی ساده ارایه دادم که نتیجه صحیح هم ارایه میدهد.
اما آیا خودم هم از آن روش استفاده می کنم؟ خیر.
با یک نگاه تشخیص میدهم خارج قسمت یا تقسیم از راست یک زبان چیست.
اشتباه در محاسبات اجتناب ناپذیر است. آن را به کلیت مسیله تعمیم ندهیم.
(۲۴ آبان ۱۳۹۲ ۰۷:۵۳ ب.ظ)kaviresabz نوشته شده توسط: سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم
اگر میشه سوال زیر رو به همین روش کتاب لینز حل کنید و توضیح هم بدید که چطور dfa رو میکشید آخه من هر کاری کردم نتونستم بفهمم که چطور میشه DFA برای خارج قسمت دو زبان رو کشید . ممنون
(*L1=L(a*baa
(*L2=L(ab
?=L1/L2
(*L2=L(ab
?=L1/L2
(۱۴ مرداد ۱۳۹۳ ۰۶:۱۹ ب.ظ)m-355 نوشته شده توسط:(24 آبان ۱۳۹۲ ۰۷:۵۳ ب.ظ)kaviresabz نوشته شده توسط: سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم
اگر میشه سوال زیر رو به همین روش کتاب لینز حل کنید و توضیح هم بدید که چطور dfa رو میکشید آخه من هر کاری کردم نتونستم بفهمم که چطور میشه DFA برای خارج قسمت دو زبان رو کشید . ممنون
(*L1=L(a*baa
(*L2=L(ab
?=L1/L2
سلام تو پیوست راه حل رو گذاشتم
تو مرحله دو الگوریتم رو دی اف ای انجام میشه
یادتون نره همیشه باید دی اف ای داشته باشید و حتما کاهش حالت شده باشه
[attachment=16829]
سلام.هنوز منطقش رو متوجه نشدید؟
سلام به همه دوستان.
روش کتاب لینز خیلی خوبه.
همونطور که دوستمون هم گفتند باید برای L1 یه DFAبکشید. حالا خوب دقت کنید: توی این DFA از هر حالت qi که تونستید حداقل با یه رشته از L2 به حالت نهایی برسید، اون qi میشه نهایی.=> بقیه حالات همه غیر نهایی هستند، همه.
اگه سوالی بود در خدمتم.
موفق باشید
(۲۴ آبان ۱۳۹۲ ۰۷:۵۳ ب.ظ)kaviresabz نوشته شده توسط: سلام
من روش کتاب لینز رو پیشنهاد میکنم
برای تقسیم :L1 به L2 ابتدا یک dfa معادل L1 رسم می کنیم
در مرحله بعد تک تک گره ها را برسی میکنیم تا ببینیم آیا میتوان با یک زیر رشته از L2 به یک حالت پذیرش رفت یا نه
اگر توانستیم آن گره را علامت می زنیم
در انتها عبارت منظم dfa جدید را بدست می آوریم
اگه دوست داشتید مثال بزارید تا با هم حل کنیم
سلام.این روش فقط برای زبان های منظم کاربرد داره.که احتمال داره هم خیلی طولانی شه