تالار گفتمان مانشت
a^n b^mc^l , n>5,m<4,l>1 منظمه؟ - نسخه‌ی قابل چاپ

a^n b^mc^l , n>5,m<4,l>1 منظمه؟ - f.b - 19 دى ۱۳۹۰ ۰۱:۰۸ ق.ظ

a^n b^mc^l
n>5,m<4,l>1
ایا منظم است؟حل تمرین لینز نوشته منظم نیست
a^n
nفرد چرا مستقل نیست؟

RE: منظمه؟ - Ali-B - 19 دى ۱۳۹۰ ۰۱:۲۸ ق.ظ

(۱۹ دى ۱۳۹۰ ۰۱:۰۸ ق.ظ)f.b نوشته شده توسط:  a^n b^mc^l
n>5,m<4,l>1
ایا منظم است؟حل تمرین لینز نوشته منظم نیست
a^n
nفرد چرا مستقل نیست؟

هر دو منظم هستند.

منظمه؟ - Jooybari - 19 دى ۱۳۹۰ ۰۵:۰۵ ق.ظ

برای قسمت الف:
[tex]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_1,a)=q_2[/tex]
[tex]\delta (q_2,a)=q_3[/tex]
[tex]\delta (q_3,a)=q_4[/tex]
[tex]\delta (q_4,a)=q_5[/tex]
[tex]\delta (q_5,a)=q_6[/tex]
[tex]\delta (q_6,a)=q_6[/tex]
[tex]\delta (q_6,b)=q_7[/tex]
[tex]\delta (q_6,c)=q_{10}[/tex]
[tex]\delta (q_7,b)=q_{8}[/tex]
[tex]\delta (q_7,c)=q_{10}[/tex]
[tex]\delta (q_8,b)=q_{9}[/tex]
[tex]\delta (q_8,c)=q_{10}[/tex]
[tex]\delta (q_9,c)=q_{10}[/tex]
[tex]\delta (q_{10},c)=q_{11}[/tex]
[tex]\delta (q_{11},c)=q_{11}[/tex]
که حالت [tex]q_0[/tex] حالت شروع و حالت [tex]q_{11}[/tex] حالت پایانیمونه.


برای قسمت ب:
[tex]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_1,a)=q_0[/tex]
که حالت [tex]q_0[/tex] حالت شروع و حالت [tex]q_{1}[/tex] حالت پایانیمونه.

منظمه؟ - f.b - 19 دى ۱۳۹۰ ۰۲:۰۶ ب.ظ

اگر در مثال دوم n اول باشد مستقل نیست؟

منظمه؟ - Jooybari - 19 دى ۱۳۹۰ ۰۳:۴۳ ب.ظ

اگه n اول باشه فکر نکنم منظم و مستقل از متن باشه. از لم تزریق استفاده میکنیم:
فرض کنین a^m رشته پذیرفته شده از این زبان باشه یعنی m اول و فرد باشه.
رشته رو ب فرم uvxyz میشکنیم به شرطی که [tex]t=|vy|[/tex] بزرگتر یا مساوی یک و اندازه |vxy| کوچکتر یا مساوی m باشه. در این صورت داریم:
[tex]uvxyz=a^m\in L[/tex]
[tex]uv^ixy^iz=a^{m (i-1)t};1\leq t\leq m[/tex]
باید ثابت کنیم که رشته [tex]uv^ixy^iz[/tex] عضو L نیست. به عبارت دیگر m+(i-1)t اول نیست.
میتونیم مقدار i رو برابر m+1 درنظر بگیریم. پس داریم:
[tex]m (m 1-1)t=m mt=m(t 1);1\leq t\leq m[/tex]
که عبارت فوق طول رشتمونه. پس:
[tex]uvxyz=a^m \in L[/tex]
[tex]uv^{m 1}xy^{m 1}z=a^{m(t 1)} \notin L ;1\leq t\leq m[/tex]
پس مستقل زبانمون از متن نیست.

منظمه؟ - f.b - 19 دى ۱۳۹۰ ۰۶:۵۱ ب.ظ

بازم تشکر
uv^ixy^iz=a^m+(i-1)t ‌ :۱<t<m
این رو متوجه نشدم که قسمت بعد مساوی توان aچطور به دست اومد
واینکه طبق چه چیزی مقدار i رو m+1 و انتخاب کردید؟

منظمه؟ - Jooybari - 19 دى ۱۳۹۰ ۰۷:۱۲ ب.ظ

v و y یه تعداد a هستن که اندازه |vy| رو t در نظر گرفتیم. پس وقتی به توان i برسه تعداد a‌ها به همون شکل زیاد میشه. اگه i رو ۲ بگیریم به اندازه t به تعداد a‌ها اضافه میشه. اگه i رو ۳ بگیریم به اندازه ۲t به تعداد a‌ها اضافه میشه.
برای i یه مقدار درنظر گرفتیم تا توان a عدد اول نشه. میشه m+1 نوشت، میشه ۲m+1 نوشت و...

a^n b^mc^l , n>5,m<4,l>1 منظمه؟ - csharpisatechnology - 01 آذر ۱۳۹۱ ۰۲:۲۷ ق.ظ

واسه هر دوشون میشه DFA = Deterministic Finite Automata رسم کرد که جناب jooybari تابع انتقالش رو نوشت.
پس حتما منظم هستند.(هر زبون منظم حما مستقل از متن هم هست یعنی میشه براش PDA یا ماشین پشته ای رسم کرد ولی ممکنه یه زبون مستقل باشه ولی منظم نباشه)