سلام دوستان سوالی در مورد مفهوم زبان های منظم
چرا زبان{a^nb^n} در صورتی که بزرگتر مساوی از صفر باشه منظم نیست
ببینید یه دلیل مفهومی خوب میخوام من اینو میدونم که منظم نیست اما از کسی
که میدونه میخوام برام کامل توضیح بده ترجیحا با مثال
زبان های منظم حافظه ندارند ولی برای این زبان ما به حافظه احتیاج داریم که تعداد a ها رو نگه داره!
بینید زمانی که مقدار n=0 هست در واقع عبارت ۱ را داریم که به راحتی قابل درک هست و یک عبارت منظم هست.
اما برای مقادیر n>=1 به ترتیب خواهیم داشت
....ab, aabb, aaabbb, aaaabbbb
در نتیجه، همانطور که لونا‌ی عزیز گفتند، برای رسم،به حافظه ای نیاز داریم که تعداد تکرار های a را نگه داشته و b را به همان تعداد تکرار کند.
یکی از مهمترین محدودیتهای زبانهای منظم اینه که حافظه ندارند. زبانهایی که لازمه تعداد تکرارهای مشخصی را حفظ کنند مانند این زبان منظم نیست. در واقع شما نمی توانید هیچ اتاماتای معینی برایشان رسم کنید.
چنانچه بتونید خوب آتاماتا بکشید برای زبانها به راحتی می توانید مشخص کنید که زبان چه نوعی است. که این هم بیش از هر چیز دیگه احتیاج به تمرین دارد.
ممنون از راهنمایی همه دوستان عزیز!!!
اما خوب نمیشه یه وضعیت Q1 ایجاد کنیم و دوتا حلقه براش بزاریم و با a,b برچسب بزنیم همین وضعیت نهایی هم باشه
همین ماشین این زبان رو بپذیره اما خوب این ماشین رشته هایی که a,b مساوی هم نباشند رو می پذیره
آیا این میتونه دلیل بر این باشه که ماشین مربوط به این زبان نیست.
زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بود و نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.
میخوام نتیجه بگیرم که اگر تستی دادند به این صورت اگه ما یه مثال نقض پیدا کنیم درسته دیگه اره.
مطلب دیگه ای تو یه کتاب خوندم این بود وابستگی بین تعداد a,bها وجود نداشته باشه که اینجا هست
بله. ماشینی که شما برای این زبان طراحی کردید( یک وضعیت که همان هم نهایی باشه) ماشین این زبان نیست چون این زبان روی الفبای a,b تمامی رشته ها، بدون وابستگی به تعداد، را می پذیرد.
حافظه هم تقریبا همین معنا را می دهد. ماشینی که a^3 را می پذیرد، همانی که شما گفتید، دارای حافظه محدود است به طول ۳/ ولی چون تعداد n نامشخص و می تواند بی نهایت باشد شما نمی تونید همچین ماشین معینی را بکشید. دقت کنید حتی اگر زبان a^1000b^1000 بود چون n محدود است منظم است و شما می تونید چنین ماشینی را بکشید. حتی اگر در تعریف زبان a^nb^n محدودیتی مانند n<1000 تعریف شده باشد هم می توان ماشینی کشید. چون تشخیص این زبان با آنکه نیاز به حافظه دارد ولی حافظه نامحدود لازم ندارد.
ممنون کاملا فهمیدم
(۲۸ شهریور ۱۳۸۹ ۰۱:۴۵ ب.ظ)javadjj نوشته شده توسط: زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بودو نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.مشکل اندازه n نیست، مشکل عدم وجود حافظه در زبانهای منظمه که نمیتونه تعداد aها رو نگه داره تا bها رو هم به همون اندازه قبول کنه! اگه تو تستها یه عدد خیلی خیلی بزرگ مشخص هم به جای n بدن اون زبان منظمه (حتی اگه استفاده از اون تعداد حالت در ماشینمون غیرمعقول باشه)
در واقع حافظه در حد "هیچ" هستش نه "کم"!
(۲۹ شهریور ۱۳۸۹ ۱۲:۱۱ ب.ظ)Soheil نوشته شده توسط:(28 شهریور ۱۳۸۹ ۰۱:۴۵ ب.ظ)javadjj نوشته شده توسط: زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بودو نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.مشکل اندازه n نیست، مشکل عدم وجود حافظه در زبانهای منظمه که نمیتونه تعداد aها رو نگه داره تا bها رو هم به همون اندازه قبول کنه! اگه تو تستها یه عدد خیلی خیلی بزرگ مشخص هم به جای n بدن اون زبان منظمه (حتی اگه استفاده از اون تعداد حالت در ماشینمون غیرمعقول باشه)
در واقع حافظه در حد "هیچ" هستش نه "کم"!
بله فکر کنم شما درست می گویید. ماشین منظم هیچ حافظه ای نداره و تعداد حالتها در واقع افزایش تعداد پردازش روی رشته است و نه ایجاد حافظه محدود!
امروز تو کتاب لینز خوندم a^nb^l:l<>n منظم نیست یکی دلیلشو بگه لطفه
چون احتیاج به حافظه داره! که حالت l=n رو قبول نکنه!
به خاطر اینکه گفته n#l و ما نمیتونیم براش محدودیت ایجاد کنیم که n برابر l نشه. اگر شرط رو برداریم
این همون a^nb^l منهای a^nb^n است که زبان اول منظم ولی زبان دوم منظم نیست.
اگر l عدد ثابتی بود میتوانستیم به عنوان یک تله حالت n=عدد ثابت = ۵ را به عنوان حالت عدم پذیرش لحاظ کنیم اما چون ثابت نیست نمیتوانیم .
(۱۷ مهر ۱۳۸۹ ۰۷:۳۲ ب.ظ)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 حتما نامنظمه و اشتراک ۲ زبان منظم نمیتونه نامنظم باشه پس زبان مورد بحث نامنظم است
بد گفتم ولی چند بار بخونیش متوجه میشی
[/u]