ارسال: #۱

۱۹ دى ۱۳۹۰, ۰۱:۰۸ ق.ظ

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

منظمه؟

برای قسمت الف:

$\delta (q_0,a)=q_1$

$\delta (q_1,a)=q_2$

$\delta (q_2,a)=q_3$

$\delta (q_3,a)=q_4$

$\delta (q_4,a)=q_5$

$\delta (q_5,a)=q_6$

$\delta (q_6,a)=q_6$

$\delta (q_6,b)=q_7$

$\delta (q_6,c)=q_{10}$

$\delta (q_7,b)=q_{8}$

$\delta (q_7,c)=q_{10}$

$\delta (q_8,b)=q_{9}$

$\delta (q_8,c)=q_{10}$

$\delta (q_9,c)=q_{10}$

$\delta (q_{10},c)=q_{11}$

$\delta (q_{11},c)=q_{11}$

که حالت

$q_0$ حالت شروع و حالت

$q_{11}$ حالت پایانیمونه.

برای قسمت ب:

$\delta (q_0,a)=q_1$

$\delta (q_1,a)=q_0$

که حالت

$q_0$ حالت شروع و حالت

$q_{1}$ حالت پایانیمونه.

ارسال: #۳

۱۹ دى ۱۳۹۰, ۰۱:۲۸ ق.ظ

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 میشکنیم به شرطی که

$t=|vy|$ بزرگتر یا مساوی یک و اندازه |vxy| کوچکتر یا مساوی m باشه. در این صورت داریم:

$uvxyz=a^m\in L$

$uv^ixy^iz=a^{m (i-1)t};1\leq t\leq m$

باید ثابت کنیم که رشته

$uv^ixy^iz$ عضو L نیست. به عبارت دیگر m+(i-1)t اول نیست.
میتونیم مقدار i رو برابر m+1 درنظر بگیریم. پس داریم:

$m (m 1-1)t=m mt=m(t 1);1\leq t\leq m$

که عبارت فوق طول رشتمونه. پس:

$uvxyz=a^m \in L$

$uv^{m 1}xy^{m 1}z=a^{m(t 1)} \notin L ;1\leq t\leq m$

پس مستقل زبانمون از متن نیست.

ارسال: #۶

۱۹ دى ۱۳۹۰, ۰۶:۵۱ ب.ظ

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
	کدوم منظمه؟	popp	۱۱	۵,۳۰۰	۰۹ شهریور ۱۳۹۰ ۰۹:۴۷ ب.ظ آخرین ارسال: Masoud05

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

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

منظمه؟

RE: منظمه؟

منظمه؟

منظمه؟

منظمه؟

منظمه؟

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

Can I see some ID?

Feeling left out?

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

Feeling left out?