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

DFA مینیمال

ارسال:
  

homa پرسیده:

DFA مینیمال

اگر [tex]m(L)[/tex] تعداد حالات dFA مینیمال متناظر با زبان [tex]L\subseteq (0,1)^{*}[/tex] باشد‌، کدام گزاره همواره درست است؟

۱/[tex]m(L)=m(L^{R})[/tex]

۲/[tex]m(L)\geq 2^{m(L^{R})}[/tex]

۳/ [tex]m(L)\leq 2^{m(L^{R})}[/tex]

۴/ [tex]m(L)\leq min (m(L),m(L^{R}))[/tex]

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

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

۰
ارسال:
  

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

RE: DFA مینیمال

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

۱/[tex]m(L)=m(L^{R})[/tex]

۲/[tex]m(L)\geq 2^{m(L^{R})}[/tex]

۳/ [tex]m(L)\leq 2^{m(L^{R})}[/tex]

۴/ [tex]m(L)\leq min (m(L),m(L^{R}))[/tex]

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

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

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

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

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


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

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

ارسال:
  

homa پاسخ داده:

RE: DFA مینیمال

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

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

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

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

۰
ارسال:
  

mfXpert پاسخ داده:

DFA مینیمال

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  شمارش تعداد state های ماشین DFA mostafa2012 ۱۰ ۴,۱۱۴ ۱۳ بهمن ۱۳۹۳ ۱۲:۱۷ ب.ظ
آخرین ارسال: fatemeh69
  بدست آوردن عبارت منظم یک dfa mostafa2012 ۸ ۱,۷۰۳ ۰۳ بهمن ۱۳۹۳ ۰۲:۲۴ ق.ظ
آخرین ارسال: Jooybari
Question زبان منظم، DFA، حافظه، به خاطر آوردن! Ametrine ۷ ۱,۶۰۶ ۲۹ دى ۱۳۹۳ ۱۱:۴۰ ب.ظ
آخرین ارسال: Ametrine
  تبدیل nfa به dfa alirezafchh ۱ ۱,۲۲۳ ۰۸ دى ۱۳۹۳ ۱۲:۴۷ ق.ظ
آخرین ارسال: fatemeh69
Question توضیح شیوه تبدیل NFA به DFA براساس این شکل s_t_6 ۲ ۲,۳۳۶ ۲۴ مرداد ۱۳۹۳ ۱۲:۳۵ ب.ظ
آخرین ارسال: fatemeh69
  گراف dfa این زبان چه شکلیست s_t_6 ۵ ۱,۱۱۸ ۰۳ مرداد ۱۳۹۳ ۱۲:۳۳ ق.ظ
آخرین ارسال: Aliteh
  فرق FSA و DFA joyebright ۳ ۶۷۷ ۰۲ اردیبهشت ۱۳۹۳ ۰۹:۲۳ ب.ظ
آخرین ارسال: hosshah
  جدول حالت یک DFA Talnetir ۴ ۷۹۲ ۲۴ اسفند ۱۳۹۲ ۰۷:۴۵ ب.ظ
آخرین ارسال: Jooybari
Question رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز g_monireh ۵ ۱,۸۴۷ ۲۹ اردیبهشت ۱۳۹۲ ۰۲:۰۲ ب.ظ
آخرین ارسال: g_monireh
  رسم dfa برای این سوال؟ post98 ۴ ۱,۲۴۸ ۲۳ فروردین ۱۳۹۲ ۰۹:۲۴ ب.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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