۰
subtitle
ارسال: #۱
  
تشخیص زبانهای ذاتاً مبهم
سلام دوستان
می خواستم بدونم راه تشخیص یک زبان ذاتاً مبهم چیست؟
با تشکر
می خواستم بدونم راه تشخیص یک زبان ذاتاً مبهم چیست؟
با تشکر
۲
ارسال: #۲
  
RE: تشخیص زبانهای ذاتاً مبهم
سلام.
زبان ها کلا دو دسته هستن:
یا ذاتاََ مبهم هستن، یا غیر مبهم. چیزی به اسم زبان مبهم نداریم. اگه حداقل یه گرامر غیر مبهم واسه زبانی وجود داشته باشه بهش میگیم زبان غیر مبهم.
زبانی غیر مبهم هست که بشه یه گرامر یا ماشین قطعی براش نوشت. و اگه حداقل بشه یکی واسش نوشت پس میشه بی نهایت تا نوشت.
زبانی ذاتاََ مبهم هست که حتی یه گرامر غیر مبهم نداره.
زبانی که مستقل از متن هست اگه همه ی گرامر هاش مبهم باشه یعنی برای تمامی گرامر هاش حداقل یه رشته وجود داشته باشه که دو تا درخت اشتقاق یا دو تا LMD یا RMD داشته باشه، اونوقت ذاتا مبهم هست اون زبان.(هیچ گرامر غیر مبهمی نداشته باشه)
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
مثلا زبان مستقل از متن زیر ذاتاََ مبهم هست:
{a^n b^n c^m | n,m>=0} اجتماعش با {a^n b^m c^m | n,m>=0} = زبان L
S-> S1 | S2
S1 -> AC
A -> aAb | lambda
C -> cC | lambda
S2 -> BD
A -> bB | lambda
C -> BdC | lambda
رشته یa^n b^n c^n رو در نظر بگیرید. هم از S1 ساخته میشه هم از طریق S2
خب پس حداقل یه رشته پیدا کردیم که از دو طریق ساخته بشه توی گرامر این زبان، پس این گرامر مبهم هست. از طرفی این زبان هیچ گرامر غیر مبهمی نداره، در نتیجه میشه زبان ذاتاََ مبهم. البته میشه رفع ابهام کرد از این زبان، میشه توی L1 یا L2 که L اجتماع این دو هست، توی یکیشون m برابر با n نباشه. اونوقته که فقط این رشته از طریق S1 ساخته میشه یا S2 و نه از دو راه. اگه این تغییر اعمال بشه، زبان میشه غیر مبهم.
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
در مجموع یه زبان ذاتاََ مبهم هست که همه ی گرامر هاش مبهم باشن. گرامری هم مبهم هست که حداقل یه رشته تووش دو تا درخت اشتقاق داشته باشه.
این یه مثال خوب هست:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
برای درک مفاهیم نظریه و کلاََ، وویس دکتر کارگهی که توی مانشت قرار داره بسیار کمک کننده هست:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
زبان ها کلا دو دسته هستن:
یا ذاتاََ مبهم هستن، یا غیر مبهم. چیزی به اسم زبان مبهم نداریم. اگه حداقل یه گرامر غیر مبهم واسه زبانی وجود داشته باشه بهش میگیم زبان غیر مبهم.
زبانی غیر مبهم هست که بشه یه گرامر یا ماشین قطعی براش نوشت. و اگه حداقل بشه یکی واسش نوشت پس میشه بی نهایت تا نوشت.
زبانی ذاتاََ مبهم هست که حتی یه گرامر غیر مبهم نداره.
زبانی که مستقل از متن هست اگه همه ی گرامر هاش مبهم باشه یعنی برای تمامی گرامر هاش حداقل یه رشته وجود داشته باشه که دو تا درخت اشتقاق یا دو تا LMD یا RMD داشته باشه، اونوقت ذاتا مبهم هست اون زبان.(هیچ گرامر غیر مبهمی نداشته باشه)
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
مثلا زبان مستقل از متن زیر ذاتاََ مبهم هست:
{a^n b^n c^m | n,m>=0} اجتماعش با {a^n b^m c^m | n,m>=0} = زبان L
S-> S1 | S2
S1 -> AC
A -> aAb | lambda
C -> cC | lambda
S2 -> BD
A -> bB | lambda
C -> BdC | lambda
رشته یa^n b^n c^n رو در نظر بگیرید. هم از S1 ساخته میشه هم از طریق S2
خب پس حداقل یه رشته پیدا کردیم که از دو طریق ساخته بشه توی گرامر این زبان، پس این گرامر مبهم هست. از طرفی این زبان هیچ گرامر غیر مبهمی نداره، در نتیجه میشه زبان ذاتاََ مبهم. البته میشه رفع ابهام کرد از این زبان، میشه توی L1 یا L2 که L اجتماع این دو هست، توی یکیشون m برابر با n نباشه. اونوقته که فقط این رشته از طریق S1 ساخته میشه یا S2 و نه از دو راه. اگه این تغییر اعمال بشه، زبان میشه غیر مبهم.
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
در مجموع یه زبان ذاتاََ مبهم هست که همه ی گرامر هاش مبهم باشن. گرامری هم مبهم هست که حداقل یه رشته تووش دو تا درخت اشتقاق داشته باشه.
این یه مثال خوب هست:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
برای درک مفاهیم نظریه و کلاََ، وویس دکتر کارگهی که توی مانشت قرار داره بسیار کمک کننده هست:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۳
  
RE: تشخیص زبانهای ذاتاً مبهم
نه. مورد به مورد باید اثبات بشن. کلا تعدادشون خیلی کمه. تو یک مقاله خوندم که نوشته بود حدود ۵۳ مثال توسط افراد مختلف تو کتابها و مقالات مختلف نوشته شده
Sent from my HTC One_E8 dual sim using Tapatalk
Sent from my HTC One_E8 dual sim using Tapatalk
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close