DFA مینیمال

اگر

$m(L)$ تعداد حالات dFA مینیمال متناظر با زبان

$L\subseteq (0,1)^{*}$ باشد‌، کدام گزاره همواره درست است؟

۱/

$m(L)=m(L^{R})$

۲/

$m(L)\geq 2^{m(L^{R})}$

۳/

$m(L)\leq 2^{m(L^{R})}$

۴/

$m(L)\leq min (m(L),m(L^{R}))$

جواب شده گزینه‌ی ۳

دلیل رد هر یک از گزینه‌ها چیه؟؟؟؟
چه جوری رو این جور سوالا باید فکر کنی.. Huh

ممنون

ارسال: #۲

۲۲ دى ۱۳۹۰, ۰۳:۰۲ ب.ظ

مازیار صفایی پاسخ داده:

RE: DFA مینیمال

(۲۲ دى ۱۳۹۰ ۱۱:۵۶ ق.ظ)homa نوشته شده توسط: اگر $m(L)$ تعداد حالات dFA مینیمال متناظر با زبان $L\subseteq (0,1)^{*}$ باشد‌، کدام گزاره همواره درست است؟

۱/ $m(L)=m(L^{R})$

۲/ $m(L)\geq 2^{m(L^{R})}$

۳/ $m(L)\leq 2^{m(L^{R})}$

۴/ $m(L)\leq min (m(L),m(L^{R}))$

جواب شده گزینه‌ی ۳

دلیل رد هر یک از گزینه‌ها چیه؟؟؟؟
چه جوری رو این جور سوالا باید فکر کنی..
ممنون

این سوال مربوط به کدام کنکور بوده؟!

به نظر من هر کدام از اینها رو نمی شه با یک یا دو مثال رد کرد. نظریه یک درس تئوریه که برای هرکدامش کلی اثبات و دلیل وجود داره
من این سوال رو که دیدم کلی اینترنت رو چرخ زدم تا به یک مقاله رسیدم که در قسمتی از اون این مساله رو عنوان کرده.

اصل مقاله ای هم پیدا کردم می ذارم.
فقط بگید این مال کدوم کنکور بوده؟! خیلی خدا نشناسن ها! Sad

فایل‌(های) پیوست شده

mfcs07.pdf
اندازه فایل: ۳۵۶/۵۶ KB

ارسال: #۳

۲۲ دى ۱۳۹۰, ۰۴:۰۳ ب.ظ

homa پاسخ داده:

RE: DFA مینیمال

نقل قول: این سوال مربوط به کدام کنکور بوده؟!

برای علوم کامپیوتر ۸۵ بوده..

بابت مقاله و وقتی که گذاشتی ممنونم آقای باد Rolleyes

...

تو کنکور یه همچین سوالایی اگه ندیده باشی تا حالا چه جوری میشه حل کرد! Huh

!!!!!

ارسال: #۴

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

mfXpert پاسخ داده:

DFA مینیمال

دوستان این سوال چیز عجیب و غریبی رو مطرح نکرده و اون قدرها هم سخت نیست.وقتی یه DFA مینیمال برای پذیرش زبان L طراحی می کنید و از روی همین ماشین‌، ماشین پذیرنده معکوس L رو در میارید ،ممکنه ماشین پذیرنده معکوس L دیگه قطعی نباشه و باید اول تبدیل به قطعی بشه و بعد حالاتش مینیمال بشه.حالا توی تبدیل از ماشین غیر قطعی به قطعی تعداد حالات ماشین قطعی در بدترین حالت به دو به توان m می رسه( فرض کنید m تعداد حالات ماشین غیر قطعی باشه).یعنی تعداد حالات به صورت نمایی رشد می کنه.حالا اگر تمام این چیزایی که گفتم رو در نظر بگیرید و به صورت به رابطه بنویسید میشه همون گزینه ۲

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	رسم dfa برای زبان زیر (تمرین ۶ کتاب لینز فصل دوم )	MBe	۱۰	۹,۶۱۲	۲۳ آبان ۱۳۹۵ ۱۲:۲۷ ق.ظ آخرین ارسال: signal_micro
	DFA	amir777	۱	۱,۴۱۲	۱۷ دى ۱۳۹۴ ۰۱:۰۵ ق.ظ آخرین ارسال: gunnersregister
	Dfa سوال پنجم فصل چهارم پوران	Baranmalihe	۱	۱,۶۴۰	۱۰ دى ۱۳۹۴ ۱۲:۰۰ ق.ظ آخرین ارسال: Jooybari
	سوال بهینه کرد DFA سال ۸۵ مهندسی کامپیوتر	iCanDoIt	۱	۲,۱۰۸	۰۹ آذر ۱۳۹۴ ۱۰:۵۹ ب.ظ آخرین ارسال: saberz
	مجموعه های ادغام ناپذیر در بهینه کردن تعداد وضعیت های DFA	iCanDoIt	۱	۱,۷۶۱	۲۳ مهر ۱۳۹۴ ۰۷:۱۲ ب.ظ آخرین ارسال: مهرگان
	مینیمال reduction کردن DFA	joyebright	۳	۲,۷۹۴	۰۵ مرداد ۱۳۹۴ ۰۱:۰۴ ق.ظ آخرین ارسال: Jooybari
	شمارش تعداد state های ماشین DFA	mostafa2012	۱۰	۱۵,۴۲۲	۱۳ بهمن ۱۳۹۳ ۱۲:۱۷ ب.ظ آخرین ارسال: fatemeh69
	بدست آوردن عبارت منظم یک dfa	mostafa2012	۸	۶,۷۶۹	۰۳ بهمن ۱۳۹۳ ۰۲:۲۴ ق.ظ آخرین ارسال: Jooybari
	زبان منظم، DFA، حافظه، به خاطر آوردن!	Ametrine	۷	۶,۲۵۷	۲۹ دى ۱۳۹۳ ۱۱:۴۰ ب.ظ آخرین ارسال: Ametrine
	تبدیل nfa به dfa	alirezafchh	۱	۲,۴۷۴	۰۸ دى ۱۳۹۳ ۱۲:۴۷ ق.ظ آخرین ارسال: fatemeh69

DFA مینیمال

DFA مینیمال

RE: DFA مینیمال

RE: DFA مینیمال

DFA مینیمال

Can I see some ID?

Feeling left out?

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

Feeling left out?