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

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
  آیا زبان uvwv^R منظمه؟ حل شد zimenswall ۷ ۳,۷۸۴ ۲۹ مهر ۱۳۹۲ ۰۱:۲۵ ق.ظ
آخرین ارسال: ایزدی
  چرا زبان 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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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