۱/آیا علتی داره که معکوس یک زبان از روی NFAاون ساخته میشه و متممش از روی DFA اون؟
تو اثباتش تو لینز و تو جزوه سید جوادی اینجوری اثبات کرده.
۲/رابطه تعداد حالات یک اتومات مینیمال و معکوسش چیست؟
دومی جزو سوالای علوم کامپیوتر ولی نمیدونم چه سالی .
دوستان اگر کسی سوالش رو داره بزاره لطفا!
معکوس یک زبان در صورتی است که حالات پایانی dfa اولیه را به حالت شروع تبدیل کنید که امکان داره چندین حالت شروع داشته باشه پس بهتره از nfa استفاده کنی ولی برای متمم باید همان حالات پایانی dfa اولیه را به حالات غیر پایانی و حالات غیر پایانی را به حالات پایانی تبدیل کنی پس برای بهتر شدن زمان اجرا می‌توان از همان dfa استفاده کرد.trap را یادت نره.
و در مورد سوال دومتون رابطشو دیدم ولی اثباتشو بلد نیستم
منظورتون این رابطه است؟ [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] برقرار نبود.
بله منظورم همین رابطه است ولی دلیلشو هنوز متوجه نشدم میشه بیشتر توضیح بدید یا با یک مثال بزنید
دلیلش رو نمیدونم ولی فقط همین گزینه بود که ۲ طرفه میشد حلش کرد.
[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]
اما سایر گزینه‌ها که مثلا به جای >=، <= بود درست در نمیاد خودتون عدد بدین متوجه میشید که رابطه از یک طرف جواب میده نه مثل بالا از دو طرف.
(۰۲ بهمن ۱۳۸۹ ۰۸:۳۲ ق.ظ)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] برقرار نبود.
میشه عمومی‌تر توضیج بدی؟ من اولین باره این رابطه رو میبینم/
این رابطه بین تعداد وضعیتهای اتوماتای یک زبان و معکوسشه. سوال علوم کامپیوتره ۸۵/
بیشتر از این چیزی به ذهنم نمیرسه که بگم .....
(۰۲ بهمن ۱۳۸۹ ۰۲:۰۱ ق.ظ)hatami84 نوشته شده توسط: معکوس یک زبان در صورتی است که حالات پایانی dfa اولیه را به حالت شروع تبدیل کنید که امکان داره چندین حالت شروع داشته باشه پس بهتره از nfa استفاده کنی ولی برای متمم باید همان حالات پایانی dfa اولیه را به حالات غیر پایانی و حالات غیر پایانی را به حالات پایانی تبدیل کنی پس برای بهتر شدن زمان اجرا می‌توان از همان dfa استفاده کرد.trap را یادت نره.
با NFA کار کردن زمان کمتری می بره چون DFA معادل یک NFA تعداد حالاتش بیشتر هست.
خوب خودم جواب سوالم رو فهمیدم!
علت اینکه از DFA برای متمم کردن یک زبان استفاده میشه این هست که در یک NFA اینکه از یک وضعیت میشه با یک حرف میشه به چند تا وضعیت رفت حالا اگر یکیشون نهایی باشه و اون یکی غیرنهایی مشکل سازه!
و همچنین وجود یالهای لاندا البته اون یال لاندایی که بین حالت نهایی و غیرنهایی وجود داره.
مثالش هم اینه:
[attachment=327]
میبینیم که حرف a عضو این زبان هست پس نباید عضو متممش باشه ولی وقتی که بخواهیم متمم رو از رو NFA بسازیم aهم عضو متممش میشه.
به نظر من اولویت با NFA هست برای به دست اووردن معکوس یا متمم چون که تعداد حالات کمتری نسبت به DFA معادل داره.
ولی برای متمم چون NFA جواب غلط میده پس مجبوریم از DFA استفاده کنیم.