سلام
من یه سوال خیلی ساده راجع به مفاهیم دارم.
اینکه چه ارتباطی بین غیرقطعی و مبهم بودن یک زبان وجود داره؟ آیا ممکنه یه زبانی غیرقطعی باشه اما مبهم نباشه و برعکس، یعنی مبهم نباشه ولی غیرقطعی باشه؟ این 2تا اصلا ربطی به هم ندارند؟
خودم حس میکنم هیچ ارتباطی بینشون نیست! یعنی ممکنه یه زبان غیرقطعی باشه اما مبهم نباشه.
(03 بهمن 1392 11:13 ب.ظ)El@he نوشته شده توسط: [ -> ]اینکه چه ارتباطی بین غیرقطعی و مبهم بودن یک زبان وجود داره؟ آیا ممکنه یه زبانی غیرقطعی باشه اما مبهم نباشه و برعکس، یعنی مبهم نباشه ولی غیرقطعی باشه؟ این ۲تا اصلا ربطی به هم ندارند؟
خودم حس میکنم هیچ ارتباطی بینشون نیست! یعنی ممکنه یه زبان غیرقطعی باشه اما مبهم نباشه.
اینکه چه ارتباطی بین غیرقطعی و مبهم بودن یک زبان وجود داره؟
جواب :
مورد اول : ابهام موضوعی در رابطه با گرامر و زبان هست ولی عدم قطعیت موضوعی مرتبط با ماشینه .
مورد دوم: زبان ها دو دسته هستند ، ذاتا مبهم و غیرمبهم
مورد سوم: گرامر ها یا مبهم و غیر مبهم هستند
اگر زبان ذاتا مبهم باشه، پس تمام ماشین هاش غیرقطعی و تمام گرامرهاش مبهم هستند.
نتیجه: زبانی مبهم نیست که بشه یه گرامر یا ماشین قطعی براش ساخت
اگر زبانی مبهم نباشه، حتما حداقل یک گرامر غیرمبهم و یک ماشین غیرقطعی براش هست.
نکته: ممکنه برای زبان غیر مبهم گرامر مبهم باشه ولی این ابهام قابل رفعه. و یا حتی میتونیم براش ماشین غیرقطعی بکشیم ولی این عدم قطعیت قابل رفعه.
پس
- مبهم بودن گرامر و غیرقطعی بودن ماشین هیچ دلیلی بر مبهم بودن زبان نیست.
- مبهم بودن زبان دلیل بر غیرقطعی بودن ماشین و مبهم بودن گرامرشه
به قول کتاب پوران: آفت ابهام بسیار قوی تر از عدم قطعیت است. یعنی قطعیت را میشه یه خاکی به سر کرد ولی وقتی ابهام باشه هیچ کاری نمیشه کرد
مثلا زبان منظم ذاتا مبهم نیست ولی گرامرهای منظم میتونن مبهم باشن اما این ابهام قابل رفعه.
مثلا گرامر LLK یک زبان غیرمبهمه و گرامرهاش هم نمیتونه مبهم باشه
دو تا شکل ضمیمه کردم خیلی خوبه . از مانشتی ها گرفتم
(03 بهمن 1392 11:46 ب.ظ)masoud67 نوشته شده توسط: [ -> ] (03 بهمن 1392 11:13 ب.ظ)El@he نوشته شده توسط: [ -> ]اینکه چه ارتباطی بین غیرقطعی و مبهم بودن یک زبان وجود داره؟ آیا ممکنه یه زبانی غیرقطعی باشه اما مبهم نباشه و برعکس، یعنی مبهم نباشه ولی غیرقطعی باشه؟ این ۲تا اصلا ربطی به هم ندارند؟
خودم حس میکنم هیچ ارتباطی بینشون نیست! یعنی ممکنه یه زبان غیرقطعی باشه اما مبهم نباشه.
اینکه چه ارتباطی بین غیرقطعی و مبهم بودن یک زبان وجود داره؟
جواب :
مورد اول : ابهام موضوعی در رابطه با گرامر و زبان هست ولی عدم قطعیت موضوعی مرتبط با ماشینه .
مورد دوم: زبان ها دو دسته هستند ، ذاتا مبهم و غیرمبهم
مورد سوم: گرامر ها یا مبهم و غیر مبهم هستند
اگر زبان ذاتا مبهم باشه، پس تمام ماشین هاش غیرقطعی و تمام گرامرهاش مبهم هستند.
نتیجه: زبانی مبهم نیست که بشه یه گرامر یا ماشین قطعی براش ساخت
اگر زبانی مبهم نباشه، حتما حداقل یک گرامر غیرمبهم و یک ماشین غیرقطعی براش هست.
نکته: ممکنه برای زبان غیر مبهم گرامر مبهم باشه ولی این ابهام قابل رفعه. و یا حتی میتونیم براش ماشین غیرقطعی بکشیم ولی این عدم قطعیت قابل رفعه.
پس
- مبهم بودن گرامر و غیرقطعی بودن ماشین هیچ دلیلی بر مبهم بودن زبان نیست.
- مبهم بودن زبان دلیل بر غیرقطعی بودن ماشین و مبهم بودن گرامرشه
به قول کتاب پوران: آفت ابهام بسیار قوی تر از عدم قطعیت است. یعنی قطعیت را میشه یه خاکی به سر کرد ولی وقتی ابهام باشه هیچ کاری نمیشه کرد
مثلا زبان منظم ذاتا مبهم نیست ولی گرامرهای منظم میتونن مبهم باشن اما این ابهام قابل رفعه.
مثلا گرامر LLK یک زبان غیرمبهمه و گرامرهاش هم نمیتونه مبهم باشه
دو تا شکل ضمیمه کردم خیلی خوبه . از مانشتی ها گرفتم
ممنون از جواب کاملتون. سوال من بیشتر روی زبان های مبهم و ماشین های غیرقطعی بود. ارتباط بین گرامر و زبان مبهم رو مشکلی ندارم.
"اگر زبانی ذاتا مهبم باشه، تمام ماشین هایش غیرقطعی هستند."
یعنی دارید یه ارتباطی بین زبان های مبهم با ماشین های غیرقطعی برقرار میکنید؟ من حس میکنم ربطی به هم نداشته باشن.
از این جمله نمیشه نتیجه گرفت که اگر زبانی مبهم نباشد، ماشینشش غیرقطعی نیست؟
(04 بهمن 1392 12:11 ق.ظ)El@he نوشته شده توسط: [ -> ]"اگر زبانی ذاتا مهبم باشه، تمام ماشین هایش غیرقطعی هستند."
یعنی دارید یه ارتباطی بین زبان های مبهم با ماشین های غیرقطعی برقرار میکنید؟ من حس میکنم ربطی به هم نداشته باشن.
از این جمله نمیشه نتیجه گرفت که اگر زبانی مبهم نباشد، ماشینشش غیرقطعی نیست؟
اینها ارتباط دارند. وقتی زبانی ذاتا مبهم باشه یعنی هیچ گرامر غیرمبهمی براش نیست. یعنی تمام گرامرهای این زبان مبهم هستند و این مبهم بودن باعث میشه ماشینی که براش میسازیم غیرقطعی باشه
[tex]a^n b^n c^m \cup a^n b^m c^m[/tex]
یک گرامر ذاتا مبهم که هیچ گرامر غیرمبهمی براش نیست و هیچ DPDA هم براش نمیشه رسم کرد .
اگر زبانی مبهم نباشه ، فقط میشه نتیجه گرفت که حتما یک ماشین قطعی براش هست. اما نمیشه گفت تمام ماشینهاش قطعی هستند. چون میشه برای این زبان غیرمبهم گرامر مبهم و ماشین غیرقطعی کشید
[tex]\lambda : S\rightarrow A|\lambda , A\rightarrow \lambda[/tex]
گرامر زبان بالا مبهمه ولی خود زبان که لاندا هست مبهم نیست. یعنی ما میتونیم حداقل یک گرامر غیرمبهم براش بنویسیم
سوال فلسفی شما:
از این جمله نمیشه نتیجه گرفت که اگر زبانی مبهم نباشد، ماشینشش غیرقطعی نیست؟
زبانی مبهم نباشه حداقل یک ماشینش غیرقطعی است .
(04 بهمن 1392 12:21 ق.ظ)masoud67 نوشته شده توسط: [ -> ] (04 بهمن 1392 12:11 ق.ظ)El@he نوشته شده توسط: [ -> ]"اگر زبانی ذاتا مهبم باشه، تمام ماشین هایش غیرقطعی هستند."
یعنی دارید یه ارتباطی بین زبان های مبهم با ماشین های غیرقطعی برقرار میکنید؟ من حس میکنم ربطی به هم نداشته باشن.
از این جمله نمیشه نتیجه گرفت که اگر زبانی مبهم نباشد، ماشینشش غیرقطعی نیست؟
اینها ارتباط دارند. وقتی زبانی ذاتا مبهم باشه یعنی هیچ گرامر غیرمبهمی براش نیست. یعنی تمام گرامرهای این زبان مبهم هستند و این مبهم بودن باعث میشه ماشینی که براش میسازیم غیرقطعی باشه
[tex]a^n b^n c^m \cup a^n b^m c^m[/tex]
یک گرامر ذاتا مبهم که هیچ گرامر غیرمبهمی براش نیست و هیچ DPDA هم براش نمیشه رسم کرد .
اگر زبانی مبهم نباشه ، فقط میشه نتیجه گرفت که حتما یک ماشین قطعی براش هست. اما نمیشه گفت تمام ماشینهاش قطعی هستند. چون میشه برای این زبان غیرمبهم گرامر مبهم و ماشین غیرقطعی کشید
[tex]\lambda : S\rightarrow A|\lambda , A\rightarrow \lambda[/tex]
گرامر زبان بالا مبهمه ولی خود زبان که لاندا هست مبهم نیست. یعنی ما میتونیم حداقل یک گرامر غیرمبهم براش بنویسیم
سوال فلسفی شما:
از این جمله نمیشه نتیجه گرفت که اگر زبانی مبهم نباشد، ماشینشش غیرقطعی نیست؟
زبانی مبهم نباشه حداقل یک ماشینش غیرقطعی است .
"یک گرامر ذاتا مبهم که هیچ DPDA هم براش نمیشه رسم کرد . "
اما مثلا زبان زیر یه زبان مبهم نیست چون یه گرامر غیرمبهم میشه واسش در نظر گرفت که واسه هررشته ای، فقط یک اشتقاق داشته باشه. اما ماشینش غیرقطعیه.
a^n b^n U a^n b^2n
این زبان مبهم نیست اما هیچ ماشین قطعی ای هم واسش نیست!
(04 بهمن 1392 12:36 ق.ظ)El@he نوشته شده توسط: [ -> ]"یک گرامر ذاتا مبهم که هیچ DPDA هم براش نمیشه رسم کرد . "
اما مثلا زبان زیر یه زبان مبهم نیست چون یه گرامر غیرمبهم میشه واسش در نظر گرفت که واسه هررشته ای، فقط یک اشتقاق داشته باشه. اما ماشینش غیرقطعیه.
a^n b^n U a^n b^2n
این زبان مبهم نیست اما هیچ ماشین قطعی ای هم واسش نیست!
شما دارید عکس اون قضیه رو مثال میزنید
قضیه اینه :زبانهای قطعی لزوما غیرمبهم هستند اما عکسش همیشه درست نیست یعنی هر زبان غیرمبهمی لزوما قطعی نیست
چون زبانهای قطعی یه زیر مجموعه از غیرمبهم ها هستند