۰
subtitle
ارسال: #۱
سوال از تشخیص زبان غیرمنظم a^n b^l a^k , n!=K+l
سلام . لطفا این سوال رو توضیح بدین . ممنون
[tex]a^nb^la^k,\: k\ne n l[/tex]
[tex]a^nb^la^k,\: k\ne n l[/tex]
۰
ارسال: #۲
سوال از تشخیص زبان غیرمنظم
سلام.
برای اثبات نامنظم بودن زبان می تونیم از لم تزریق استفاده کنیم. برای کنکور نیازی به استفاده از لم تزریق و اثباتش نیست،
تو این سوال (قسمت b) توجه کن که زبان "نامحدود" و "طول aهای انتهایی به طول aوbهای ابتدایی وابسته ست"، پس همین امر باعث میشه زبان نامنظم باشه.
----------------------------------------------
اگه زبانی تعداد رشته هاش محدود باشه، زبان منظم خواهد بود، اگه نامحدود شمارش پذیر هم باشه باز منظم خواهد بود.
اما این سوال نامحدود است.
----------------------------------------------
جواب این سوال زبان مستقل از متن است.
----------------------------------------------
موفق باشی.
برای اثبات نامنظم بودن زبان می تونیم از لم تزریق استفاده کنیم. برای کنکور نیازی به استفاده از لم تزریق و اثباتش نیست،
تو این سوال (قسمت b) توجه کن که زبان "نامحدود" و "طول aهای انتهایی به طول aوbهای ابتدایی وابسته ست"، پس همین امر باعث میشه زبان نامنظم باشه.
----------------------------------------------
اگه زبانی تعداد رشته هاش محدود باشه، زبان منظم خواهد بود، اگه نامحدود شمارش پذیر هم باشه باز منظم خواهد بود.
اما این سوال نامحدود است.
----------------------------------------------
جواب این سوال زبان مستقل از متن است.
----------------------------------------------
موفق باشی.
ارسال: #۳
RE: سوال از تشخیص زبان غیرمنظم
(۲۶ مهر ۱۳۹۱ ۰۳:۱۰ ب.ظ)azad_ahmadi نوشته شده توسط: سلام.ممنون . واقعا جوابتون مشکلم رو تو این سوال و بعضی سوال های دیگه حل کرد.
اگه زبانی تعداد رشته هاش محدود باشه، زبان منظم خواهد بود، اگه نامحدود شمارش پذیر هم باشه باز منظم خواهد بود.
اما این سوال نامحدود است.
(۲۶ مهر ۱۳۹۱ ۰۴:۳۲ ب.ظ)esi نوشته شده توسط: تو قسمت b شما باید تعداد n تا a و تعداد l تا b رو بشمارید تا بتونید مساله رو حل کنید که مسالمه به علت بی حافظه بودن ماشین متناهی شما نمی تونید این کارو انجام بدید
ممنون از جوابتون . خیلی خوب به کاربرد حافظه ماشین متناهی در حل اینگونه مسائل اشاره کردین . در متن درس خونده بودم ولی به کاربردش برنخورده بودم .
۰
ارسال: #۴
سوال از تشخیص زبان غیرمنظم
تو قسمت b شما باید تعداد n تا a و تعداد l تا b رو بشمارید تا بتونید مساله رو حل کنید که مسالمه به علت بی حافظه بودن ماشین متناهی شما نمی تونید این کارو انجام بدید. البته برای اثبات دقیقش باید از لم تزریق استفاده کنید اما به صورت تجربی هم میشه تا حدودی حدس زد. کلا باید تو نظریه زبان تمرین زیاد حل کنید تا بتونید تمامی زبان ها رو تو ذهنتون تجسم کنید و ببینید می تونید براش آتاماتای مناسبشو پیدا کنید یا نه ؟
در کل مشابه حرفای دوستمون آزاد یه سرانگشتی میشه گفت که باید طول رشته محدود باشه زبان حتما منظمه اما نه همیشه مثلا *a یا *b یا سیگما استار محدود نیست اما منظمه ، اما مسلمه باید بین رشته های پیشوند و پسوند وابستگی قابل شمارش وجود نداشته باشه . اما برای اثبات دقیق برای برخی مسائل پیچیده مسلما باید از لم تزریق استفاده کنید .
در کل مشابه حرفای دوستمون آزاد یه سرانگشتی میشه گفت که باید طول رشته محدود باشه زبان حتما منظمه اما نه همیشه مثلا *a یا *b یا سیگما استار محدود نیست اما منظمه ، اما مسلمه باید بین رشته های پیشوند و پسوند وابستگی قابل شمارش وجود نداشته باشه . اما برای اثبات دقیق برای برخی مسائل پیچیده مسلما باید از لم تزریق استفاده کنید .
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close