۱
subtitle
ارسال: #۱
سوال ۵۴ سال ۹۱
من اصلا اینو نمیفهمم 
۲
ارسال: #۲
RE: سوال ۵۴ سال ۹۱
این سوال یه کوچولو جدیده یعنی نمونه ش قبلا نبوده
برای این سوال شما باید عملیات تقسیم از راست و تقسیم از چپ رو خوب بلد باشید
وقتی می گه دو رشته ی x,y به شرطی هم ارزند که با ازای هر z ای عضو زبان xz با yz برابر باشه
یعنی این که اگه از زبان تقسیم از چپ x بگیریم با وقتی که از زبان تقسیم از چپ y می گیریم باید مساوی باشه
به عبارت دیگه
[tex]x^{-1}L=y^{-1}L[/tex]
خب ما باید برای حل این سوال از L یه بار تقسیم از چپ a بگیریم یه بار تقسیم از چجپ b
بعد یه بار aa و یه بار ab, bb, ba ,aaa,aab, ....و...
و همین طور این کارو ادامه بدیم تا جایی که بدونیم دیگه هیچ چیز جدیدی بدست نمیاد
منتها چون سوال کنکوریه ما فقط تسیم از چپ اون رشته هایی رو حساب می کنیم که تو گزینه ها اومده یعنی:
[tex](a)^{-1}(ab aab)^{\ast}=b(ab aab)^{\ast} ab(ab aab)^{\ast}[/tex]
[tex]b^{-1}(ab aab)^{\ast}=\phi[/tex]
[tex](ab)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](\lambda)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](aab)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](aa)^{-1}(ab aab)^{\ast}=b(ab aab)^{\ast}[/tex]
پس کلاس های هم ارزی لاندا و ab و aab یکسان هستند و وقتی می گه کلاس های هم ارزی L رو بنویسید فقط باید اونایی که متفاوت ستن رو بنویسیم.
پس می شه گزینه ۳
برای این سوال شما باید عملیات تقسیم از راست و تقسیم از چپ رو خوب بلد باشید
وقتی می گه دو رشته ی x,y به شرطی هم ارزند که با ازای هر z ای عضو زبان xz با yz برابر باشه
یعنی این که اگه از زبان تقسیم از چپ x بگیریم با وقتی که از زبان تقسیم از چپ y می گیریم باید مساوی باشه
به عبارت دیگه
[tex]x^{-1}L=y^{-1}L[/tex]
خب ما باید برای حل این سوال از L یه بار تقسیم از چپ a بگیریم یه بار تقسیم از چجپ b
بعد یه بار aa و یه بار ab, bb, ba ,aaa,aab, ....و...
و همین طور این کارو ادامه بدیم تا جایی که بدونیم دیگه هیچ چیز جدیدی بدست نمیاد
منتها چون سوال کنکوریه ما فقط تسیم از چپ اون رشته هایی رو حساب می کنیم که تو گزینه ها اومده یعنی:
[tex](a)^{-1}(ab aab)^{\ast}=b(ab aab)^{\ast} ab(ab aab)^{\ast}[/tex]
[tex]b^{-1}(ab aab)^{\ast}=\phi[/tex]
[tex](ab)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](\lambda)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](aab)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](aa)^{-1}(ab aab)^{\ast}=b(ab aab)^{\ast}[/tex]
پس کلاس های هم ارزی لاندا و ab و aab یکسان هستند و وقتی می گه کلاس های هم ارزی L رو بنویسید فقط باید اونایی که متفاوت ستن رو بنویسیم.
پس می شه گزینه ۳
ارسال: #۳
RE: سوال ۵۴ سال ۹۱
(۲۸ دى ۱۳۹۳ ۰۷:۳۴ ب.ظ)fatemeh69 نوشته شده توسط: این سوال یه کوچولو جدیده یعنی نمونه ش قبلا نبوده
برای این سوال شما باید عملیات تقسیم از راست و تقسیم از چپ رو خوب بلد باشید
وقتی می گه دو رشته ی x,y به شرطی هم ارزند که با ازای هر z ای عضو زبان xz با yz برابر باشه
یعنی این که اگه از زبان تقسیم از چپ x بگیریم با وقتی که از زبان تقسیم از چپ y می گیریم باید مساوی باشه
به عبارت دیگه
[tex]x^{-1}L=y^{-1}L[/tex]
خب ما باید برای حل این سوال از L یه بار تقسیم از چپ a بگیریم یه بار تقسیم از چجپ b
بعد یه بار aa و یه بار ab, bb, ba ,aaa,aab, ....و...
و همین طور این کارو ادامه بدیم تا جایی که بدونیم دیگه هیچ چیز جدیدی بدست نمیاد
منتها چون سوال کنکوریه ما فقط تسیم از چپ اون رشته هایی رو حساب می کنیم که تو گزینه ها اومده یعنی:
[tex](a)^{-1}(ab aab)^{\ast}=b(ab aab)^{\ast} ab(ab aab)^{\ast}[/tex]
[tex]b^{-1}(ab aab)^{\ast}=\phi[/tex]
[tex](ab)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](\lambda)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](aab)^{-1}(ab aab)^{\ast}=\lambda(ab aab)^{\ast}[/tex]
[tex](aa)^{-1}(ab aab)^{\ast}=b(ab aab)^{\ast}[/tex]
پس کلاس های هم ارزی لاندا و ab و aab یکسان هستند و وقتی می گه کلاس های هم ارزی L رو بنویسید فقط باید اونایی که متفاوت ستن رو بنویسیم.
پس می شه گزینه ۳
ممنوووون خیلییییییی لطف کردین
۱
ارسال: #۵
RE: سوال ۵۴ سال ۹۱
یه روش دیگه ش هم اینه که اگه دست به dfa کمینه کشیدنتون خوبه
اول dfa کمینه بکشید بعد به تعداد state ها کلاس هم ارزی دازید
اصلا کلاس های هم ارزی یه زبان همون state های dfa کمینه ش هستند
و این که اسم اون کلاس هم ارزی چیه اسمش اون مسیریه که از start تا رسیدن به اون state طی می شه
مثلا از start با لاندا یا با ab یا با aab می ریم به start پس این سه تا یه کلاس هم ارزی هستند و اسم کلاس state start همون لاندا یا ab یا aab است
از start با a می ریم به state1 پس اسم state1 همون a است. مثلا رشته های aaba , aba ,... هم تو این کلاس هستند
از start با aa می ریم به state2 پس اسم state2 همون aa است. مثلا رشته های aabaa , abaaa,.. هم تو این کلاس هستند
از start با aaa می ریم به state3 پس اسم state3 همون aaa است. مثلا رشته های bb, ba,, abaaa ,b,.... هم تو این کلاس هستند
dfa کمینه آن ۴ تا state دارد پس ۴ تا کلاس هم ارزی دارد و کلاس های هم ارزی ش هم همونایی هستند که تو
زینه ۳ ذکر شده
اول dfa کمینه بکشید بعد به تعداد state ها کلاس هم ارزی دازید
اصلا کلاس های هم ارزی یه زبان همون state های dfa کمینه ش هستند
و این که اسم اون کلاس هم ارزی چیه اسمش اون مسیریه که از start تا رسیدن به اون state طی می شه
مثلا از start با لاندا یا با ab یا با aab می ریم به start پس این سه تا یه کلاس هم ارزی هستند و اسم کلاس state start همون لاندا یا ab یا aab است
از start با a می ریم به state1 پس اسم state1 همون a است. مثلا رشته های aaba , aba ,... هم تو این کلاس هستند
از start با aa می ریم به state2 پس اسم state2 همون aa است. مثلا رشته های aabaa , abaaa,.. هم تو این کلاس هستند
از start با aaa می ریم به state3 پس اسم state3 همون aaa است. مثلا رشته های bb, ba,, abaaa ,b,.... هم تو این کلاس هستند
dfa کمینه آن ۴ تا state دارد پس ۴ تا کلاس هم ارزی دارد و کلاس های هم ارزی ش هم همونایی هستند که تو
زینه ۳ ذکر شده
۰
ارسال: #۷
RE: سوال ۵۴ سال ۹۱
![[تصویر: 327737_2uyx5siqppup.jpg]](https://img.manesht.ir/327737_2uyx5siqppup.jpg)
۰
ارسال: #۸
RE: سوال ۵۴ سال ۹۱
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close