تالار گفتمان مانشت
ضروری زبان های منظم - نسخه‌ی قابل چاپ

ضروری زبان های منظم - javadjj - 27 شهریور ۱۳۸۹ ۰۵:۳۵ ب.ظ

سلام دوستان سوالی در مورد مفهوم زبان های منظم
چرا زبان{a^nb^n} در صورتی که بزرگتر مساوی از صفر باشه منظم نیست
ببینید یه دلیل مفهومی خوب میخوام من اینو میدونم که منظم نیست اما از کسی
که میدونه میخوام برام کامل توضیح بده ترجیحا با مثال

ضروری زبان های منظم - luna - 27 شهریور ۱۳۸۹ ۰۵:۴۰ ب.ظ

زبان های منظم حافظه ندارند ولی برای این زبان ما به حافظه احتیاج داریم که تعداد a ‌ها رو نگه داره!

ضروری زبان های منظم - Afra - 27 شهریور ۱۳۸۹ ۰۶:۵۷ ب.ظ

بینید زمانی که مقدار n=0 هست در واقع عبارت ۱ را داریم که به راحتی قابل درک هست و یک عبارت منظم هست.
اما برای مقادیر n>=1 به ترتیب خواهیم داشت
....ab, aabb, aaabbb, aaaabbbb

در نتیجه، همانطور که لونا‌ی عزیز گفتند، برای رسم،به حافظه ای نیاز داریم که تعداد تکرار های a را نگه داشته و b را به همان تعداد تکرار کند.

ضروری زبان های منظم - karostami - 27 شهریور ۱۳۸۹ ۰۸:۳۳ ب.ظ

یکی از مهمترین محدودیتهای زبانهای منظم اینه که حافظه ندارند. زبانهایی که لازمه تعداد تکرارهای مشخصی را حفظ کنند مانند این زبان منظم نیست. در واقع شما نمی توانید هیچ اتاماتای معینی برایشان رسم کنید.
چنانچه بتونید خوب آتاماتا بکشید برای زبانها به راحتی می توانید مشخص کنید که زبان چه نوعی است. که این هم بیش از هر چیز دیگه احتیاج به تمرین دارد.

ضروری زبان های منظم - javadjj - 28 شهریور ۱۳۸۹ ۰۱:۴۵ ب.ظ

ممنون از راهنمایی همه دوستان عزیز!!!
اما خوب نمیشه یه وضعیت Q1 ایجاد کنیم و دوتا حلقه براش بزاریم و با a,b برچسب بزنیم همین وضعیت نهایی هم باشه
همین ماشین این زبان رو بپذیره اما خوب این ماشین رشته هایی که a,b مساوی هم نباشند رو می پذیره
آیا این میتونه دلیل بر این باشه که ماشین مربوط به این زبان نیست.
زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بود و نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.
میخوام نتیجه بگیرم که اگر تستی دادند به این صورت اگه ما یه مثال نقض پیدا کنیم درسته دیگه اره.
مطلب دیگه ای تو یه کتاب خوندم این بود وابستگی بین تعداد a,b‌ها وجود نداشته باشه که اینجا هست

ضروری زبان های منظم - karostami - 29 شهریور ۱۳۸۹ ۰۱:۰۲ ق.ظ

بله. ماشینی که شما برای این زبان طراحی کردید( یک وضعیت که همان هم نهایی باشه) ماشین این زبان نیست چون این زبان روی الفبای a,b تمامی رشته ها، بدون وابستگی به تعداد، را می پذیرد.
حافظه هم تقریبا همین معنا را می دهد. ماشینی که a^3 را می پذیرد، همانی که شما گفتید، دارای حافظه محدود است به طول ۳/ ولی چون تعداد n نامشخص و می تواند بی نهایت باشد شما نمی تونید همچین ماشین معینی را بکشید. دقت کنید حتی اگر زبان a^1000b^1000 بود چون n محدود است منظم است و شما می تونید چنین ماشینی را بکشید. حتی اگر در تعریف زبان a^nb^n محدودیتی مانند n<1000 تعریف شده باشد هم می توان ماشینی کشید. چون تشخیص این زبان با آنکه نیاز به حافظه دارد ولی حافظه نامحدود لازم ندارد.

ضروری زبان های منظم - javadjj - 29 شهریور ۱۳۸۹ ۱۲:۰۶ ب.ظ

ممنون کاملا فهمیدم

RE: ضروری زبان های منظم - Soheil - 29 شهریور ۱۳۸۹ ۱۲:۱۱ ب.ظ

(۲۸ شهریور ۱۳۸۹ ۰۱:۴۵ ب.ظ)javadjj نوشته شده توسط:  زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بودو نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.
مشکل اندازه n نیست، مشکل عدم وجود حافظه در زبانهای منظمه که نمیتونه تعداد aها رو نگه داره تا bها رو هم به همون اندازه قبول کنه! اگه تو تستها یه عدد خیلی خیلی بزرگ مشخص هم به جای n بدن اون زبان منظمه (حتی اگه استفاده از اون تعداد حالت در ماشینمون غیرمعقول باشه)
در واقع حافظه در حد "هیچ" هستش نه "کم"!

RE: ضروری زبان های منظم - karostami - 29 شهریور ۱۳۸۹ ۱۰:۳۲ ب.ظ

(۲۹ شهریور ۱۳۸۹ ۱۲:۱۱ ب.ظ)Soheil نوشته شده توسط:  
(28 شهریور ۱۳۸۹ ۰۱:۴۵ ب.ظ)javadjj نوشته شده توسط:  زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بودو نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.
مشکل اندازه n نیست، مشکل عدم وجود حافظه در زبانهای منظمه که نمیتونه تعداد aها رو نگه داره تا bها رو هم به همون اندازه قبول کنه! اگه تو تستها یه عدد خیلی خیلی بزرگ مشخص هم به جای n بدن اون زبان منظمه (حتی اگه استفاده از اون تعداد حالت در ماشینمون غیرمعقول باشه)
در واقع حافظه در حد "هیچ" هستش نه "کم"!

بله فکر کنم شما درست می گویید. ماشین منظم هیچ حافظه ای نداره و تعداد حالتها در واقع افزایش تعداد پردازش روی رشته است و نه ایجاد حافظه محدود!

ضروری زبان های منظم - javadjj - 17 مهر ۱۳۸۹ ۰۷:۳۲ ب.ظ

امروز تو کتاب لینز خوندم a^nb^l:l<>n منظم نیست یکی دلیلشو بگه لطفه

ضروری زبان های منظم - luna - 17 مهر ۱۳۸۹ ۰۹:۰۲ ب.ظ

چون احتیاج به حافظه داره! که حالت l=n رو قبول نکنه!

ضروری زبان های منظم - ف.ش - ۱۷ مهر ۱۳۸۹ ۰۹:۱۲ ب.ظ

به خاطر اینکه گفته n#l و ما نمیتونیم براش محدودیت ایجاد کنیم که n برابر l نشه. اگر شرط رو برداریم

این همون a^nb^l منهای a^nb^n است که زبان اول منظم ولی زبان دوم منظم نیست.


اگر l عدد ثابتی بود میتوانستیم به عنوان یک تله حالت n=عدد ثابت = ۵ را به عنوان حالت عدم پذیرش لحاظ کنیم اما چون ثابت نیست نمیتوانیم .

RE: ضروری زبان های منظم - saria - 11 آبان ۱۳۸۹ ۰۴:۱۷ ب.ظ

(۱۷ مهر ۱۳۸۹ ۰۷:۳۲ ب.ظ)javadjj نوشته شده توسط:  امروز تو کتاب لینز خوندم a^nb^l:l<>n منظم نیست یکی دلیلشو بگه لطفه
خوب میتونی اینو با مثال حل کنی
اگه L منظم باشه پس ال بارهم منظمه
ال بار=a^nb^n
پس ال بار اشتراکش با L1=a^nb^l باید منظم باشه
a^nb^n اشتراکش با a^nb^l مساوی a^nb^n که در نتیجه چون میدونیم که
a^nb^n حتما نامنظمه و اشتراک ۲ زبان منظم نمیتونه نامنظم باشه پس زبان مورد بحث نامنظم است

بد گفتم ولی چند بار بخونیش متوجه میشیBig Grin[/u]