سوال از تشخیص زبان غیرمنظم a^n b^l a^k , n!=K+l

سوال از تشخیص زبان غیرمنظم a^n b^l a^k , n!=K+l - نسخه‌ی قابل چاپ

سوال از تشخیص زبان غیرمنظم a^n b^l a^k , n!=K+l - mahdokht91 - 26 مهر ۱۳۹۱ ۰۱:۲۶ ب.ظ

سلام . لطفا این سوال رو توضیح بدین . ممنون
[tex]a^nb^la^k,\: k\ne n l[/tex]

سوال از تشخیص زبان غیرمنظم - azad_ahmadi - 26 مهر ۱۳۹۱ ۰۳:۱۰ ب.ظ

سلام.
برای اثبات نامنظم بودن زبان می تونیم از لم تزریق استفاده کنیم. برای کنکور نیازی به استفاده از لم تزریق و اثباتش نیست،
تو این سوال (قسمت b) توجه کن که زبان "نامحدود" و "طول aهای انتهایی به طول aوbهای ابتدایی وابسته ست"، پس همین امر باعث میشه زبان نامنظم باشه.
----------------------------------------------
اگه زبانی تعداد رشته هاش محدود باشه، زبان منظم خواهد بود، اگه نامحدود شمارش پذیر هم باشه باز منظم خواهد بود.
اما این سوال نامحدود است.
----------------------------------------------
جواب این سوال زبان مستقل از متن است.
----------------------------------------------
موفق باشی.

سوال از تشخیص زبان غیرمنظم - esi - 26 مهر ۱۳۹۱ ۰۴:۳۲ ب.ظ

تو قسمت b شما باید تعداد n تا a و تعداد l تا b رو بشمارید تا بتونید مساله رو حل کنید که مسالمه به علت بی حافظه بودن ماشین متناهی شما نمی تونید این کارو انجام بدید. البته برای اثبات دقیقش باید از لم تزریق استفاده کنید اما به صورت تجربی هم میشه تا حدودی حدس زد. کلا باید تو نظریه زبان تمرین زیاد حل کنید تا بتونید تمامی زبان ها رو تو ذهنتون تجسم کنید و ببینید می تونید براش آتاماتای مناسبشو پیدا کنید یا نه ؟
در کل مشابه حرفای دوستمون آزاد یه سرانگشتی میشه گفت که باید طول رشته محدود باشه زبان حتما منظمه اما نه همیشه مثلا *a یا *b یا سیگما استار محدود نیست اما منظمه ، اما مسلمه باید بین رشته های پیشوند و پسوند وابستگی قابل شمارش وجود نداشته باشه . اما برای اثبات دقیق برای برخی مسائل پیچیده مسلما باید از لم تزریق استفاده کنید .

RE: سوال از تشخیص زبان غیرمنظم - mahdokht91 - 26 مهر ۱۳۹۱ ۰۶:۴۷ ب.ظ

(۲۶ مهر ۱۳۹۱ ۰۳:۱۰ ب.ظ)azad_ahmadi نوشته شده توسط: سلام.

اگه زبانی تعداد رشته هاش محدود باشه، زبان منظم خواهد بود، اگه نامحدود شمارش پذیر هم باشه باز منظم خواهد بود.
اما این سوال نامحدود است.

ممنون . واقعا جوابتون مشکلم رو تو این سوال و بعضی سوال های دیگه حل کرد.

(۲۶ مهر ۱۳۹۱ ۰۴:۳۲ ب.ظ)esi نوشته شده توسط: تو قسمت b شما باید تعداد n تا a و تعداد l تا b رو بشمارید تا بتونید مساله رو حل کنید که مسالمه به علت بی حافظه بودن ماشین متناهی شما نمی تونید این کارو انجام بدید

ممنون از جوابتون . خیلی خوب به کاربرد حافظه ماشین متناهی در حل اینگونه مسائل اشاره کردین . در متن درس خونده بودم ولی به کاربردش برنخورده بودم .

RE: سوال از تشخیص زبان غیرمنظم - azad_ahmadi - 03 آبان ۱۳۹۱ ۱۲:۰۵ ق.ظ

(۰۲ آبان ۱۳۹۱ ۰۲:۵۵ ب.ظ)somaye_tex نوشته شده توسط:
(26 مهر ۱۳۹۱ ۰۳:۱۰ ب.ظ)azad_ahmadi نوشته شده توسط: سلام.
برای اثبات نامنظم بودن زبان می تونیم از لم تزریق استفاده کنیم. برای کنکور نیازی به استفاده از لم تزریق و اثباتش نیست،
تو این سوال (قسمت b) توجه کن که زبان "نامحدود" و "طول aهای انتهایی به طول aوbهای ابتدایی وابسته ست"، پس همین امر باعث میشه زبان نامنظم باشه.
----------------------------------------------
اگه زبانی تعداد رشته هاش محدود باشه، زبان منظم خواهد بود، اگه نامحدود شمارش پذیر هم باشه باز منظم خواهد بود.
اما این سوال نامحدود است.
----------------------------------------------
جواب این سوال زبان مستقل از متن است.
----------------------------------------------
موفق باشی.

اینو از کجا آوردین؟؟؟؟؟؟؟؟؟/////////

خب سادست. ببینید، مثلا زبانی با الفبای a، که طول رشته هاش mod 3 باشه. این زبان منظم هست ولی نامحدود و شمارش پذیر.
چرا که mod 3 یا برابر ۰، یابرابر ۱، یا برابر ۲ هست. پس زبان نامحدود ولی شمارش پذیر، و درنتیجه منظم خواهد بود.
موفق باشی.

RE: سوال از تشخیص زبان غیرمنظم - somaye_tex - 04 آبان ۱۳۹۱ ۱۱:۵۳ ب.ظ

(۰۳ آبان ۱۳۹۱ ۱۲:۰۵ ق.ظ)azad_ahmadi نوشته شده توسط:
(02 آبان ۱۳۹۱ ۰۲:۵۵ ب.ظ)somaye_tex نوشته شده توسط:
(26 مهر ۱۳۹۱ ۰۳:۱۰ ب.ظ)azad_ahmadi نوشته شده توسط: سلام.
برای اثبات نامنظم بودن زبان می تونیم از لم تزریق استفاده کنیم. برای کنکور نیازی به استفاده از لم تزریق و اثباتش نیست،
تو این سوال (قسمت b) توجه کن که زبان "نامحدود" و "طول aهای انتهایی به طول aوbهای ابتدایی وابسته ست"، پس همین امر باعث میشه زبان نامنظم باشه.
----------------------------------------------
اگه زبانی تعداد رشته هاش محدود باشه، زبان منظم خواهد بود، اگه نامحدود شمارش پذیر هم باشه باز منظم خواهد بود.
اما این سوال نامحدود است.
----------------------------------------------
جواب این سوال زبان مستقل از متن است.
----------------------------------------------
موفق باشی.

اینو از کجا آوردین؟؟؟؟؟؟؟؟؟/////////

خب سادست. ببینید، مثلا زبانی با الفبای a، که طول رشته هاش mod 3 باشه. این زبان منظم هست ولی نامحدود و شمارش پذیر.
چرا که mod 3 یا برابر ۰، یابرابر ۱، یا برابر ۲ هست. پس زبان نامحدود ولی شمارش پذیر، و درنتیجه منظم خواهد بود.
موفق باشی.

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