زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۲:۵۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

عملگر تقسیم دو زبان

ارسال:
  

H-Arshad پرسیده:

عملگر تقسیم دو زبان

سلام
متاسفانه اصلا عملگر تقسیم در زبان رو نمیفهمم
L1/L2 Huh

۳
ارسال:
  

zimenswall پاسخ داده:

RE: عملگر تقسیم دو زبان

منم مثل شما در این مورد زیاد مشکل داشتم ولی با این مثال که تو کتاب پارسه بود تقریبا مشکلم حل شد.
البته راه حل من نمیدونم درسته یا نه، ولی جوابی که بدست آوردم درست بود
خیلی ساده است.
مثلا 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 تفاوت داشت.
پس تا حالا شانس آوردم که اون دو سه تا تستی که زدم اشتباه نشده. با راه حل غلط جواب درست میزدم Big Grin

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

ارسال:
  

Jooybari پاسخ داده:

RE: عملگر تقسیم دو زبان

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

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

ارسال:
  

zimenswall پاسخ داده:

RE: عملگر تقسیم دو زبان

(۱۳ آبان ۱۳۹۲ ۰۵:۵۰ ب.ظ)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 تفاوت داشت.
پس تا حالا شانس آوردم که اون دو سه تا تستی که زدم اشتباه نشده. با راه حل غلط جواب درست میزدم Big Grin

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

۰
ارسال:
  

Dr.Cnet پاسخ داده:

RE: عملگر تقسیم دو زبان

اگه 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 داره - آخ جون Smile احمد بالا رو با پایین میزنیم و فقط میمونه 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 Smile
حالا رشته هایی که قبول شدن میشه جواب:
L1\L2: {reza,reza,lambda} X که میشه یک رضا رو حذف کرد چون تکراریه.

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

۰
ارسال:
  

H-Arshad پاسخ داده:

RE: عملگر تقسیم دو زبان

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

ارسال:
  

zimenswall پاسخ داده:

RE: عملگر تقسیم دو زبان

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

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

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

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

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

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

۰
ارسال:
  

MiladCr7 پاسخ داده:

RE: عملگر تقسیم دو زبان

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

ارسال:
  

afshari پاسخ داده:

RE: عملگر تقسیم دو زبان

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

ارسال: #۱۰
  

kaviresabz پاسخ داده:

RE: عملگر تقسیم دو زبان

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

ارسال: #۱۱
  

m-355 پاسخ داده:

RE: عملگر تقسیم دو زبان

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

اگر میشه سوال زیر رو به همین روش کتاب لینز حل کنید و توضیح هم بدید که چطور dfa رو میکشید آخه من هر کاری کردم نتونستم بفهمم که چطور میشه DFA برای خارج قسمت دو زبان رو کشید . ممنون
(*L1=L(a*baa
(*L2=L(ab
?=L1/L2
یافتن تمامی ارسال‌های این کاربر

ارسال: #۱۲
  

kaviresabz پاسخ داده:

RE: عملگر تقسیم دو زبان

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

اگر میشه سوال زیر رو به همین روش کتاب لینز حل کنید و توضیح هم بدید که چطور dfa رو میکشید آخه من هر کاری کردم نتونستم بفهمم که چطور میشه DFA برای خارج قسمت دو زبان رو کشید . ممنون
(*L1=L(a*baa
(*L2=L(ab
?=L1/L2

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

مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

ارسال: #۱۳
  

MiladCr7 پاسخ داده:

RE: عملگر تقسیم دو زبان

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

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

ارسال: #۱۴
  

afshari پاسخ داده:

RE: عملگر تقسیم دو زبان

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

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۹ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  تقسیم برای محاسبه کد افزونه چرخشی (CRC) Sanazzz ۴ ۶,۱۴۲ ۲۰ آذر ۱۳۹۷ ۰۱:۱۸ ب.ظ
آخرین ارسال: Sanazzz
  شبکه معنایی تقسیم شده در هوش rezahe73 ۰ ۱,۱۲۸ ۱۷ دى ۱۳۹۶ ۰۴:۰۹ ق.ظ
آخرین ارسال: rezahe73
  تقسیم افراد به دو تیم ss311 ۲ ۱,۶۱۳ ۱۲ دى ۱۳۹۶ ۱۱:۵۷ ب.ظ
آخرین ارسال: ss311
  تقسیم در جبر رابطه ای Ella ۱ ۲,۰۰۹ ۲۸ آذر ۱۳۹۶ ۱۲:۰۰ ق.ظ
آخرین ارسال: Ella
  دانلود رایگان کتاب «زبان عمومی دکتری زیر ذره بین» مرجع اصلی زبان کنکور دکتری generalenglish ۰ ۳,۶۹۷ ۱۸ اردیبهشت ۱۳۹۶ ۰۹:۴۳ ب.ظ
آخرین ارسال: generalenglish
  عملگر semigroup چیست؟ H-Arshad ۰ ۱,۱۶۹ ۱۵ دى ۱۳۹۵ ۰۶:۰۷ ب.ظ
آخرین ارسال: H-Arshad
  سوال از روش تقسیم و غلبه kamal3401 ۳ ۵,۱۳۶ ۱۱ خرداد ۱۳۹۵ ۰۲:۴۴ ق.ظ
آخرین ارسال: Behnam‌
  جدول تقدم عملگر ها hadi72345 ۲ ۳,۳۷۶ ۲۵ فروردین ۱۳۹۵ ۱۰:۳۳ ب.ظ
آخرین ارسال: dariush.fathi
  زبان های منظم تحت عملگر minus5 منظم است؟ Pure Liveliness ۲ ۱,۶۵۵ ۱۴ فروردین ۱۳۹۵ ۰۱:۲۷ ب.ظ
آخرین ارسال: Pure Liveliness

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close