زمان کنونی: ۲۸ آذر ۱۳۹۷, ۰۹:۵۸ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

a^n b^mc^l , n>5,m<4,l>1 منظمه؟

ارسال:
  

f.b پرسیده:

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فرد چرا مستقل نیست؟

۰
ارسال:
  

Jooybari پاسخ داده:

منظمه؟

برای قسمت الف:
[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] حالت پایانیمونه.

۰
ارسال:
  

Ali-B پاسخ داده:

RE: منظمه؟

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

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

۰
ارسال:
  

f.b پاسخ داده:

منظمه؟

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

۰
ارسال:
  

Jooybari پاسخ داده:

منظمه؟

اگه 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 پاسخ داده:

منظمه؟

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

۰
ارسال:
  

Jooybari پاسخ داده:

منظمه؟

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

۰
ارسال:
  

csharpisatechnology پاسخ داده:

a^n b^mc^l , n>5,m<4,l>1 منظمه؟

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  آیا زبان W1W2 منظمه؟ masoud67 ۱۶ ۳,۱۳۹ ۲۳ دى ۱۳۹۲ ۰۱:۵۸ ب.ظ
آخرین ارسال: ali.329
  چرا زبان uww^Rv منظمه؟ حل شد zimenswall ۸ ۱,۸۸۲ ۰۸ مهر ۱۳۹۲ ۰۵:۳۸ ب.ظ
آخرین ارسال: zimenswall
  چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد zimenswall ۶ ۱,۴۶۹ ۲۲ شهریور ۱۳۹۲ ۰۱:۴۹ ق.ظ
آخرین ارسال: zimenswall
  چرا زبان { (u w v w^R v} منظمه؟ حل شد zimenswall ۲ ۹۲۸ ۲۱ شهریور ۱۳۹۲ ۰۹:۲۶ ب.ظ
آخرین ارسال: zimenswall
  چرا زبان { (a^n w b^n w^R c^n u} منظمه؟ حل شد zimenswall ۰ ۶۶۴ ۲۱ شهریور ۱۳۹۲ ۰۸:۱۴ ب.ظ
آخرین ارسال: zimenswall
  چرا زبان {u v w | u = w^R } منظمه؟ حل شد zimenswall ۰ ۷۳۵ ۲۱ شهریور ۱۳۹۲ ۰۸:۱۳ ب.ظ
آخرین ارسال: zimenswall
  چطور هم منظمه و مستقل از متن dfsefes ۵ ۱,۶۸۲ ۲۷ دى ۱۳۹۱ ۰۱:۱۲ ق.ظ
آخرین ارسال: csharpisatechnology
  چرا این زبان منظمه؟ باقیمانده تعداد aبرbبشه ۳ miladdn13 ۳ ۱,۱۴۷ ۱۹ مهر ۱۳۹۰ ۱۱:۱۱ ب.ظ
آخرین ارسال: sasanlive
Question کدوم منظمه؟ popp ۱۱ ۲,۰۷۳ ۰۹ شهریور ۱۳۹۰ ۰۹:۴۷ ب.ظ
آخرین ارسال: Masoud05
  چرا این زبان منظمه؟؟ zr2358 ۱۸ ۵,۳۲۵ ۱۴ بهمن ۱۳۸۹ ۰۴:۰۲ ب.ظ
آخرین ارسال: ف.ش

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close