۰
subtitle
ارسال: #۱
  
سوال درباره معکوس یک زبان منظم
۱/آیا علتی داره که معکوس یک زبان از روی NFAاون ساخته میشه و متممش از روی DFA اون؟
تو اثباتش تو لینز و تو جزوه سید جوادی اینجوری اثبات کرده.
۲/رابطه تعداد حالات یک اتومات مینیمال و معکوسش چیست؟
دومی جزو سوالای علوم کامپیوتر ولی نمیدونم چه سالی .
دوستان اگر کسی سوالش رو داره بزاره لطفا!
تو اثباتش تو لینز و تو جزوه سید جوادی اینجوری اثبات کرده.
۲/رابطه تعداد حالات یک اتومات مینیمال و معکوسش چیست؟
دومی جزو سوالای علوم کامپیوتر ولی نمیدونم چه سالی .
دوستان اگر کسی سوالش رو داره بزاره لطفا!
۰
ارسال: #۲
  
سوال درباره معکوس یک زبان منظم
معکوس یک زبان در صورتی است که حالات پایانی dfa اولیه را به حالت شروع تبدیل کنید که امکان داره چندین حالت شروع داشته باشه پس بهتره از nfa استفاده کنی ولی برای متمم باید همان حالات پایانی dfa اولیه را به حالات غیر پایانی و حالات غیر پایانی را به حالات پایانی تبدیل کنی پس برای بهتر شدن زمان اجرا میتوان از همان dfa استفاده کرد.trap را یادت نره.
و در مورد سوال دومتون رابطشو دیدم ولی اثباتشو بلد نیستم
و در مورد سوال دومتون رابطشو دیدم ولی اثباتشو بلد نیستم
ارسال: #۳
  
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] برقرار نبود.
دلیلش اینه
[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] برقرار نبود.
ارسال: #۵
  
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] برقرار نبود.
میشه عمومیتر توضیج بدی؟ من اولین باره این رابطه رو میبینم/
۰
ارسال: #۶
  
سوال درباره معکوس یک زبان منظم
بله منظورم همین رابطه است ولی دلیلشو هنوز متوجه نشدم میشه بیشتر توضیح بدید یا با یک مثال بزنید
۰
ارسال: #۷
  
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]
اما سایر گزینهها که مثلا به جای >=، <= بود درست در نمیاد خودتون عدد بدین متوجه میشید که رابطه از یک طرف جواب میده نه مثل بالا از دو طرف.
[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]
اما سایر گزینهها که مثلا به جای >=، <= بود درست در نمیاد خودتون عدد بدین متوجه میشید که رابطه از یک طرف جواب میده نه مثل بالا از دو طرف.
۰
ارسال: #۸
  
سوال درباره معکوس یک زبان منظم
این رابطه بین تعداد وضعیتهای اتوماتای یک زبان و معکوسشه. سوال علوم کامپیوتره ۸۵/
بیشتر از این چیزی به ذهنم نمیرسه که بگم .....
بیشتر از این چیزی به ذهنم نمیرسه که بگم .....
۰
ارسال: #۹
  
RE: سوال درباره معکوس یک زبان منظم
خوب خودم جواب سوالم رو فهمیدم!
علت اینکه از DFA برای متمم کردن یک زبان استفاده میشه این هست که در یک NFA اینکه از یک وضعیت میشه با یک حرف میشه به چند تا وضعیت رفت حالا اگر یکیشون نهایی باشه و اون یکی غیرنهایی مشکل سازه!
و همچنین وجود یالهای لاندا البته اون یال لاندایی که بین حالت نهایی و غیرنهایی وجود داره.
مثالش هم اینه:
میبینیم که حرف a عضو این زبان هست پس نباید عضو متممش باشه ولی وقتی که بخواهیم متمم رو از رو NFA بسازیم aهم عضو متممش میشه.
به نظر من اولویت با NFA هست برای به دست اووردن معکوس یا متمم چون که تعداد حالات کمتری نسبت به DFA معادل داره.
ولی برای متمم چون NFA جواب غلط میده پس مجبوریم از DFA استفاده کنیم.
علت اینکه از DFA برای متمم کردن یک زبان استفاده میشه این هست که در یک NFA اینکه از یک وضعیت میشه با یک حرف میشه به چند تا وضعیت رفت حالا اگر یکیشون نهایی باشه و اون یکی غیرنهایی مشکل سازه!
و همچنین وجود یالهای لاندا البته اون یال لاندایی که بین حالت نهایی و غیرنهایی وجود داره.
مثالش هم اینه:
میبینیم که حرف a عضو این زبان هست پس نباید عضو متممش باشه ولی وقتی که بخواهیم متمم رو از رو NFA بسازیم aهم عضو متممش میشه.
به نظر من اولویت با NFA هست برای به دست اووردن معکوس یا متمم چون که تعداد حالات کمتری نسبت به DFA معادل داره.
ولی برای متمم چون NFA جواب غلط میده پس مجبوریم از DFA استفاده کنیم.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close