۰
subtitle
ارسال: #۱
a^n b^mc^l , n>5,m<4,l>1 منظمه؟
a^n b^mc^l
n>5,m<4,l>1
ایا منظم است؟حل تمرین لینز نوشته منظم نیست
a^n
nفرد چرا مستقل نیست؟
n>5,m<4,l>1
ایا منظم است؟حل تمرین لینز نوشته منظم نیست
a^n
nفرد چرا مستقل نیست؟
۰
ارسال: #۲
منظمه؟
برای قسمت الف:
برای قسمت ب:
[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_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]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_1,a)=q_0[/tex]
که حالت [tex]q_0[/tex] حالت شروع و حالت [tex]q_{1}[/tex] حالت پایانیمونه.
[tex]\delta (q_1,a)=q_0[/tex]
۰
ارسال: #۳
RE: منظمه؟
۰
۰
ارسال: #۵
منظمه؟
اگه n اول باشه فکر نکنم منظم و مستقل از متن باشه. از لم تزریق استفاده میکنیم:
فرض کنین a^m رشته پذیرفته شده از این زبان باشه یعنی m اول و فرد باشه.
رشته رو ب فرم uvxyz میشکنیم به شرطی که [tex]t=|vy|[/tex] بزرگتر یا مساوی یک و اندازه |vxy| کوچکتر یا مساوی m باشه. در این صورت داریم:
میتونیم مقدار i رو برابر m+1 درنظر بگیریم. پس داریم:
فرض کنین 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 اول نیست.[tex]uv^ixy^iz=a^{m (i-1)t};1\leq t\leq m[/tex]
میتونیم مقدار 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]
پس مستقل زبانمون از متن نیست.
[tex]uv^{m 1}xy^{m 1}z=a^{m(t 1)} \notin L ;1\leq t\leq m[/tex]
۰
ارسال: #۶
منظمه؟
بازم تشکر
uv^ixy^iz=a^m+(i-1)t :۱<t<m
این رو متوجه نشدم که قسمت بعد مساوی توان aچطور به دست اومد
واینکه طبق چه چیزی مقدار i رو m+1 و انتخاب کردید؟
uv^ixy^iz=a^m+(i-1)t :۱<t<m
این رو متوجه نشدم که قسمت بعد مساوی توان aچطور به دست اومد
واینکه طبق چه چیزی مقدار i رو m+1 و انتخاب کردید؟
۰
ارسال: #۷
منظمه؟
v و y یه تعداد a هستن که اندازه |vy| رو t در نظر گرفتیم. پس وقتی به توان i برسه تعداد aها به همون شکل زیاد میشه. اگه i رو ۲ بگیریم به اندازه t به تعداد aها اضافه میشه. اگه i رو ۳ بگیریم به اندازه ۲t به تعداد aها اضافه میشه.
برای i یه مقدار درنظر گرفتیم تا توان a عدد اول نشه. میشه m+1 نوشت، میشه ۲m+1 نوشت و...
برای i یه مقدار درنظر گرفتیم تا توان a عدد اول نشه. میشه m+1 نوشت، میشه ۲m+1 نوشت و...
۰
ارسال: #۸
a^n b^mc^l , n>5,m<4,l>1 منظمه؟
واسه هر دوشون میشه DFA = Deterministic Finite Automata رسم کرد که جناب jooybari تابع انتقالش رو نوشت.
پس حتما منظم هستند.(هر زبون منظم حما مستقل از متن هم هست یعنی میشه براش PDA یا ماشین پشته ای رسم کرد ولی ممکنه یه زبون مستقل باشه ولی منظم نباشه)
پس حتما منظم هستند.(هر زبون منظم حما مستقل از متن هم هست یعنی میشه براش PDA یا ماشین پشته ای رسم کرد ولی ممکنه یه زبون مستقل باشه ولی منظم نباشه)
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close