۳
subtitle
ارسال: #۱
نکاتی از خواص زبان مستقل و زبان منظم
نکات زیر رو از کتاب پیتر لینز ترجمه ی صرافزاده+ناصری براتون میذارم:
===
(ف ۸ ص ۲۰۳ تا ۲۰۸):
==============
اشتراک دو زبان مستقل از متن،لزوما مستقل از متن نیست.در نتیجه خانواده ی زبانهای مستقل از متن تحت متم گیری(مکمل) بسته نیستند.
==
اشتراک یک زبان مستقل از متن و یک زبان منظم،مستقل از متن خواهد بود.
==
زبانهای مستقل از متن تحت همریختی و معکوس بسته اند.
==
زبان های خطی تحت همریختی بسته اند.
==
زبان های مستقل از متن به طور کلی تحت تفاضل بسته نیستند اما تحت تفاضل منظم بسته اند یعنی اگر L1 مستقل و L2 منظم باشد L1-L2 مستقل است.
==
زبانهای مستقل از متن معین(DCF) تحت عمل تفاضل منظم بسته اند.
==
زبانهای خطی تحت اجتماع بسته اند ولی تحت الحاق بسته نیستند.
==
زبانهای خطی تحت اشتراک بسته نیستند.
==
زبان های مستقل از متن معین تحت اجتماع و اشتراک بسته نیستند.
==
اگر L1 خطی و L2 منظم باشد آنگاه L1L2 خطی است.
==
زبانهای مستقل از متن غیرگنگ(غیر مبهم=معین) تحت اجتماع و اشتراک بسته نیستند.
==
۲ تا نکته از خودم :
اگر a^nb^m منظم است اگر m>=0 و n>=0 .
a^nb^n مستقل است ولی منظم نیست اگر n به سمت بی نهایت میل کند(می توان برایش PDA رسم کرد ولی DFA نمی توان)
==
الگوریتمی وجود دارد که مشخص کند آیا زبان تولید شده توسط یک گرامر مستقل از متن شامل کلماتی با طول کمتر از n هستند.
==
اگر L1 مستقل و L2 منظم باشد، الگوریتمی برای تعیین اینکه آیا L1 و L2 عنصر مشترکی دارند یا خیر وجود دارد.
==
اگه استقبال کنید ادامه میدم
===
(ف ۸ ص ۲۰۳ تا ۲۰۸):
==============
اشتراک دو زبان مستقل از متن،لزوما مستقل از متن نیست.در نتیجه خانواده ی زبانهای مستقل از متن تحت متم گیری(مکمل) بسته نیستند.
==
اشتراک یک زبان مستقل از متن و یک زبان منظم،مستقل از متن خواهد بود.
==
زبانهای مستقل از متن تحت همریختی و معکوس بسته اند.
==
زبان های خطی تحت همریختی بسته اند.
==
زبان های مستقل از متن به طور کلی تحت تفاضل بسته نیستند اما تحت تفاضل منظم بسته اند یعنی اگر L1 مستقل و L2 منظم باشد L1-L2 مستقل است.
==
زبانهای مستقل از متن معین(DCF) تحت عمل تفاضل منظم بسته اند.
==
زبانهای خطی تحت اجتماع بسته اند ولی تحت الحاق بسته نیستند.
==
زبانهای خطی تحت اشتراک بسته نیستند.
==
زبان های مستقل از متن معین تحت اجتماع و اشتراک بسته نیستند.
==
اگر L1 خطی و L2 منظم باشد آنگاه L1L2 خطی است.
==
زبانهای مستقل از متن غیرگنگ(غیر مبهم=معین) تحت اجتماع و اشتراک بسته نیستند.
==
۲ تا نکته از خودم :
اگر a^nb^m منظم است اگر m>=0 و n>=0 .
a^nb^n مستقل است ولی منظم نیست اگر n به سمت بی نهایت میل کند(می توان برایش PDA رسم کرد ولی DFA نمی توان)
==
الگوریتمی وجود دارد که مشخص کند آیا زبان تولید شده توسط یک گرامر مستقل از متن شامل کلماتی با طول کمتر از n هستند.
==
اگر L1 مستقل و L2 منظم باشد، الگوریتمی برای تعیین اینکه آیا L1 و L2 عنصر مشترکی دارند یا خیر وجود دارد.
==
اگه استقبال کنید ادامه میدم
۲
ارسال: #۲
RE: نکاتی از خواص زبان مستقل و زبان منظم
بستگی به نحوه بیان ما داره:
۱-اشتراک یک زبان مستقل از متن و یک زبان منظم،مستقل از متن خواهد بود.(به طور کلی درسته ،چرا که اگر که زبان حاصل یک زبان منظم باشه می تونه مستقل از متن هم باشه)
اما جمله:
۲-اشتراک یک زبان مستقل از متن و یک زبان منظم،ممکن است منظم باشد هم درسته.(اما همواره مستقل از متن نیز است).
۳-اشتراک یک زبان مستقل از متن و یک زبان منظم، تنها مستقل از متن خواهد بود(این جمله اشتباهه، چرا ممکنه وضعیتی مشابه جمله قبل(۲) پیش بیاد و زبان هم منظم باشه و هم مستقل از متن)
۱-اشتراک یک زبان مستقل از متن و یک زبان منظم،مستقل از متن خواهد بود.(به طور کلی درسته ،چرا که اگر که زبان حاصل یک زبان منظم باشه می تونه مستقل از متن هم باشه)
اما جمله:
۲-اشتراک یک زبان مستقل از متن و یک زبان منظم،ممکن است منظم باشد هم درسته.(اما همواره مستقل از متن نیز است).
۳-اشتراک یک زبان مستقل از متن و یک زبان منظم، تنها مستقل از متن خواهد بود(این جمله اشتباهه، چرا ممکنه وضعیتی مشابه جمله قبل(۲) پیش بیاد و زبان هم منظم باشه و هم مستقل از متن)
۱
ارسال: #۳
نکاتی از خواص زبان مستقل و زبان منظم
یه مثال نقض میارم تا براتون ثابت کنم که اشتراک یک زبان مستقل از متن و یک زبان منظم می تونه منظم نباشه:
مثلا a^nb^n و n>=0 مستقل هست ولی منظم نیست.
و زبان a^mb^n و n>=0 و m>=0 ،منظم هست(می دونیم یه زبون منظم همیشه مستقل هم هست ولی عکسش ممکنه نباشه).
حالا اشتراکشون میشه a^nb^n و n>=0 که مستقل هست ولی منظم نیست. پس نتیجه می گیریم که :
اشتراک یک زبان مستقل از متن و یک زبان منظم می تونه منظم نباشه.(البته گاهی هم می تونه منظم باشه اما نه همیشه)
مثلا a^nb^n و n>=0 مستقل هست ولی منظم نیست.
و زبان a^mb^n و n>=0 و m>=0 ،منظم هست(می دونیم یه زبون منظم همیشه مستقل هم هست ولی عکسش ممکنه نباشه).
حالا اشتراکشون میشه a^nb^n و n>=0 که مستقل هست ولی منظم نیست. پس نتیجه می گیریم که :
اشتراک یک زبان مستقل از متن و یک زبان منظم می تونه منظم نباشه.(البته گاهی هم می تونه منظم باشه اما نه همیشه)
ارسال: #۴
RE: نکاتی از خواص زبان مستقل و زبان منظم
(۱۵ آبان ۱۳۹۱ ۰۵:۲۳ ق.ظ)csharpisatechnology نوشته شده توسط: یه مثال نقض میارم تا براتون ثابت کنم که اشتراک یک زبان مستقل از متن و یک زبان منظم می تونه منظم نباشه:
مثلا a^nb^n و n>=0 مستقل هست ولی منظم نیست.
و زبان a^mb^n و n>=0 و m>=0 ،منظم هست(می دونیم یه زبون منظم همیشه مستقل هم هست ولی عکسش ممکنه نباشه).
حالا اشتراکشون میشه a^nb^n و n>=0 که مستقل هست ولی منظم نیست. پس نتیجه می گیریم که :
اشتراک یک زبان مستقل از متن و یک زبان منظم می تونه منظم نباشه.(البته گاهی هم می تونه منظم باشه اما نه همیشه)
شکی نیست. چیزی که من گفتم اینه که این اشتراک لزوماً مستقل از متن نیست. شما گفته بودید این اشتراک حتماً مستقل از متنه. بهتر بود گفته میشد منظم یا مستقل از متنه. شرط کافی برای منظم بودنو گفتم. شرط کافی برای منظم نبودن هم اینه که زبان مستقل از متن زیرمجموعه ای از زبان منظم باشه.
۰
ارسال: #۵
نکاتی از خواص زبان مستقل و زبان منظم
سلام. متشکر بخاطر ارسالتون. ولی من روی "اشتراک یک زبان مستقل از متن و یک زبان منظم،مستقل از متن خواهد بود." شک دارم. اگه زبان منظم زیرمجموعه زبان مستقل از متن باشه یکی از حالاتیه که اشتراکشون منظمه.
۰
ارسال: #۶
نکاتی از خواص زبان مستقل و زبان منظم
آیا الگوریتمی وجود دارد که رشته ی u و عبارت منظم r(روی همان الفبا)را بگیرد و محاسبه کند u می تواند r را پذیرش کند یا نه؟ بلی
====
آیا الگوریتمی وجود دارد که رشته ی u و عبارت منظم r(روی همان الفبا)را بگیرد و محاسبه کند u معادل r است یا نه؟ بلی
====
![[تصویر: 142045_1_1379088061.gif]](https://img.manesht.ir/142045_1_1379088061.gif)
<HR>
![[تصویر: 142045_2_1379088061.gif]](https://img.manesht.ir/142045_2_1379088061.gif)
==
هر کدوم رو متوجه نمیشید واسم پیام خصوصی بزنید هر شب بررسی می کنم.
====
آیا الگوریتمی وجود دارد که رشته ی u و عبارت منظم r(روی همان الفبا)را بگیرد و محاسبه کند u معادل r است یا نه؟ بلی
====
<HR>
==
هر کدوم رو متوجه نمیشید واسم پیام خصوصی بزنید هر شب بررسی می کنم.
۰
ارسال: #۷
نکاتی از خواص زبان مستقل و زبان منظم
من این جمله ی شما رو قبول ندارم که : "شرط کافی برای منظم نبودن هم اینه که زبان مستقل از متن زیرمجموعه ای از زبان منظم باشه."
==
به راحتی به مثال تناقض ثابت می کنم حرفتون اشتباهه :
مثال L1=ab که مستقل هست.
L2=ab u bb که منظم هست.
می دونیم L1 زیر مجموعه ی L2 هست. اما اشتراک L1 و L2 که میشه L1=ab هرگز نامنظم نیست. پس رو چه حسابی می گید»
"شرط کافی برای منظم نبودن هم اینه که زبان مستقل از متن زیرمجموعه ای از زبان منظم باشه." ؟؟؟؟؟؟؟؟؟؟؟؟
لطفا قبل از پاسخ به این سوال خوب دقت بفرمایید چون قسمت های بسیار ظریفی توی این جور مباحث وجود داره که نباید با عجله پاسخ داد.
===
ضمنا این جمله شما رو هم قبول دارم که " بهتر بود گفته میشد اشتراک یه زبان منظم و یک زبان مستقل ،منظم یا مستقل از متنه."
اما اینو کسی می فهمه که حرفه ای باشه اما یه تازه کار ممکنه فکر کنه منظم یعنی همون مستقل .
پس بهتره بگیم:
"اشتراک یه زبون مستقل و یه زبون منظم حتما مستقل هست اما ممکنه منظم نباشه ممکنه گاهی منظم بشه و به طور کلی تحت اشتراک منظم بسته نیستند."
==
اگه مشکلی احساس کردید پ.خ بزنید.
==
به راحتی به مثال تناقض ثابت می کنم حرفتون اشتباهه :
مثال L1=ab که مستقل هست.
L2=ab u bb که منظم هست.
می دونیم L1 زیر مجموعه ی L2 هست. اما اشتراک L1 و L2 که میشه L1=ab هرگز نامنظم نیست. پس رو چه حسابی می گید»
"شرط کافی برای منظم نبودن هم اینه که زبان مستقل از متن زیرمجموعه ای از زبان منظم باشه." ؟؟؟؟؟؟؟؟؟؟؟؟
لطفا قبل از پاسخ به این سوال خوب دقت بفرمایید چون قسمت های بسیار ظریفی توی این جور مباحث وجود داره که نباید با عجله پاسخ داد.
===
ضمنا این جمله شما رو هم قبول دارم که " بهتر بود گفته میشد اشتراک یه زبان منظم و یک زبان مستقل ،منظم یا مستقل از متنه."
اما اینو کسی می فهمه که حرفه ای باشه اما یه تازه کار ممکنه فکر کنه منظم یعنی همون مستقل .
پس بهتره بگیم:
"اشتراک یه زبون مستقل و یه زبون منظم حتما مستقل هست اما ممکنه منظم نباشه ممکنه گاهی منظم بشه و به طور کلی تحت اشتراک منظم بسته نیستند."
==
اگه مشکلی احساس کردید پ.خ بزنید.
۰
ارسال: #۸
نکاتی از خواص زبان مستقل و زبان منظم
دوست عزیز ما زبانی رو مستقل از متن معرفی میکنیم که علاوه بر پیاده سازی با گرامر مستقل از متنظف منظم نباشه. همیشه حداقل سطح رو میبینیم، مثل مستقل از متن معین و منظم و ...
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close