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

سوال درباره معکوس یک زبان منظم

ارسال:
  

sepid پرسیده:

سوال درباره معکوس یک زبان منظم

۱/آیا علتی داره که معکوس یک زبان از روی NFAاون ساخته میشه و متممش از روی DFA اون؟
تو اثباتش تو لینز و تو جزوه سید جوادی اینجوری اثبات کرده.
۲/رابطه تعداد حالات یک اتومات مینیمال و معکوسش چیست؟
دومی جزو سوالای علوم کامپیوتر ولی نمیدونم چه سالی .
دوستان اگر کسی سوالش رو داره بزاره لطفا!
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

hatami پاسخ داده:

سوال درباره معکوس یک زبان منظم

معکوس یک زبان در صورتی است که حالات پایانی dfa اولیه را به حالت شروع تبدیل کنید که امکان داره چندین حالت شروع داشته باشه پس بهتره از nfa استفاده کنی ولی برای متمم باید همان حالات پایانی dfa اولیه را به حالات غیر پایانی و حالات غیر پایانی را به حالات پایانی تبدیل کنی پس برای بهتر شدن زمان اجرا می‌توان از همان dfa استفاده کرد.trap را یادت نره.
و در مورد سوال دومتون رابطشو دیدم ولی اثباتشو بلد نیستم

ارسال:
  

sepid پاسخ داده:

RE: سوال درباره معکوس یک زبان منظم

(۰۲ بهمن ۱۳۸۹ ۰۲:۰۱ ق.ظ)hatami84 نوشته شده توسط:  معکوس یک زبان در صورتی است که حالات پایانی dfa اولیه را به حالت شروع تبدیل کنید که امکان داره چندین حالت شروع داشته باشه پس بهتره از nfa استفاده کنی ولی برای متمم باید همان حالات پایانی dfa اولیه را به حالات غیر پایانی و حالات غیر پایانی را به حالات پایانی تبدیل کنی پس برای بهتر شدن زمان اجرا می‌توان از همان dfa استفاده کرد.trap را یادت نره.


با NFA کار کردن زمان کمتری می بره چون DFA معادل یک NFA تعداد حالاتش بیشتر هست.
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

ف.ش پاسخ داده:

RE: سوال درباره معکوس یک زبان منظم

منظورتون این رابطه است؟ [tex]m(L)\leq 2^{m(L^{R})}[/tex]
دلیلش اینه
[tex]L=L^{R}^{R}[/tex]
یعنی هر رابطه ای که برای L از روی [tex]L^{R}[/tex]
مینویسیم باید برای [tex]L^{R}[/tex] هم از روی L بشه نوشت و اگه به جای [tex]\leq[/tex]

،[tex]\geq[/tex] داشتیم دیگه این رابطه برای [tex]m(L^{R})[/tex] برقرار نبود.

ارسال:
  

jaroon پاسخ داده:

RE: سوال درباره معکوس یک زبان منظم

(۰۲ بهمن ۱۳۸۹ ۰۸:۳۲ ق.ظ)afagh1389 نوشته شده توسط:  منظورتون این رابطه است؟ [tex]m(L)\leq 2^{m(L^{R})}[/tex]
دلیلش اینه
[tex]L=L^{R}^{R}[/tex]
یعنی هر رابطه ای که برای L از روی [tex]L^{R}[/tex]
مینویسیم باید برای [tex]L^{R}[/tex] هم از روی L بشه نوشت و اگه به جای [tex]\leq[/tex]

،[tex]\geq[/tex] داشتیم دیگه این رابطه برای [tex]m(L^{R})[/tex] برقرار نبود.

میشه عمومی‌تر توضیج بدی؟ من اولین باره این رابطه رو میبینم/
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

hatami پاسخ داده:

سوال درباره معکوس یک زبان منظم

بله منظورم همین رابطه است ولی دلیلشو هنوز متوجه نشدم میشه بیشتر توضیح بدید یا با یک مثال بزنید

۰
ارسال:
  

ف.ش پاسخ داده:

RE: سوال درباره معکوس یک زبان منظم

دلیلش رو نمیدونم ولی فقط همین گزینه بود که ۲ طرفه میشد حلش کرد.
[tex]m(L)=7 , m(L^{R})=3 \to \ 7\leq 2^{3}[/tex]

[tex]m(L^{R})=3 , m(L)=7 \rightarrow 3\leq 2^{7}[/tex]

اما سایر گزینه‌ها که مثلا به جای >=‌، <= بود درست در نمیاد خودتون عدد بدین متوجه میشید که رابطه از یک طرف جواب میده نه مثل بالا از دو طرف.

۰
ارسال:
  

ف.ش پاسخ داده:

سوال درباره معکوس یک زبان منظم

این رابطه بین تعداد وضعیتهای اتوماتای یک زبان و معکوسشه. سوال علوم کامپیوتره ۸۵/
بیشتر از این چیزی به ذهنم نمیرسه که بگم .....

۰
ارسال:
  

sepid پاسخ داده:

RE: سوال درباره معکوس یک زبان منظم

خوب خودم جواب سوالم رو فهمیدم!
علت اینکه از DFA برای متمم کردن یک زبان استفاده میشه این هست که در یک NFA اینکه از یک وضعیت میشه با یک حرف میشه به چند تا وضعیت رفت حالا اگر یکیشون نهایی باشه و اون یکی غیرنهایی مشکل سازه!
و همچنین وجود یالهای لاندا البته اون یال لاندایی که بین حالت نهایی و غیرنهایی وجود داره.
مثالش هم اینه:



میبینیم که حرف a عضو این زبان هست پس نباید عضو متممش باشه ولی وقتی که بخواهیم متمم رو از رو NFA بسازیم aهم عضو متممش میشه.
به نظر من اولویت با NFA هست برای به دست اووردن معکوس یا متمم چون که تعداد حالات کمتری نسبت به DFA معادل داره.
ولی برای متمم چون NFA جواب غلط میده پس مجبوریم از DFA استفاده کنیم.
مشاهده‌ی وب‌سایت کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  راهنمایی درباره مقطع کارشناسی ارشد HamidReza1 ۰ ۱,۰۶۲ ۱۴ اسفند ۱۴۰۱ ۱۰:۴۰ ب.ظ
آخرین ارسال: HamidReza1
  تصمیم گیری مهم درباره مکان سرور سایت admin ۴ ۴,۸۴۶ ۲۸ دى ۱۴۰۰ ۰۳:۵۹ ب.ظ
آخرین ارسال: mahsa3323
  انتخاب موضوع پروژه درباره سیستم عامل آیلا ۱۸ ۲۰,۰۶۲ ۱۳ دى ۱۴۰۰ ۰۵:۴۱ ب.ظ
آخرین ارسال: Cimia
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۶,۰۳۲ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  سوال درباره بیوانفورماتیک شریف Ella ۴ ۱۰,۴۳۹ ۲۴ فروردین ۱۳۹۹ ۱۰:۳۹ ب.ظ
آخرین ارسال: ilas
  گرامر منظم Sanazzz ۶ ۷,۰۰۹ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
  درباره سطح دانشگاه شاهدروزانه و شبانه امیرکبیر واحد گرمسار tondar.sal ۳ ۵,۰۹۲ ۱۸ شهریور ۱۳۹۷ ۰۴:۳۷ ب.ظ
آخرین ارسال: tondar.sal
  کمک درباره دانشگاه فارابی قم Gamatria ۶ ۸,۲۰۱ ۱۹ تیر ۱۳۹۷ ۱۰:۱۰ ب.ظ
آخرین ارسال: Happiness.72
  تعداد صف کمکی برای معکوس کردن صف rad.bahar ۱ ۲,۷۸۹ ۰۹ تیر ۱۳۹۷ ۱۲:۴۰ ق.ظ
آخرین ارسال: Mr.R3ZA
  سوال درباره کنترل ترافیک شبکه zorro ۱ ۳,۴۲۷ ۰۸ تیر ۱۳۹۷ ۰۳:۲۶ ب.ظ
آخرین ارسال: Amir V

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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