۰
subtitle
ارسال: #۱
  
زبان CF هست یا نه؟ {|L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{+},|U|>=|V
ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]
۰
ارسال: #۲
  
RE: زبان CF هست یا نه؟
(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط: ایا زبان زیر مستقل از متن هست یا نه؟بنظر منم یه زبان مستقل از متن نامعینه! و با ۱ پشته ولی بصورت نامعین میشه اونو درستش کرد یعنی اول u رو تو پشته بزاریم و با توجه به خاصیت نامعین بودن ماشین w و معکوسش رو تشخیص بدیم و پشته رو از w و معکوسش خالی کنیم تا u داخلش باشه بعدش طول u , v رو بررسی کنیم .
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]
خوشحال میشم اگه اشتباه میکنم، راهنماییم کنید .
ارسال: #۳
  
RE: زبان CF هست یا نه؟
(۱۱ دى ۱۳۹۰ ۱۲:۲۶ ق.ظ)Masoud05 نوشته شده توسط: بنظر منم یه زبان مستقل از متن نامعینه! و با ۱ پشته ولی بصورت نامعین میشه اونو درستش کرد یعنی اول u رو تو پشته بزاریم و با توجه به خاصیت نامعین بودن ماشین w و معکوسش رو تشخیص بدیم و پشته رو از w و معکوسش خالی کنیم تا u داخلش باشه بعدش طول u , v رو بررسی کنیم .
خوشحال میشم اگه اشتباه میکنم، راهنماییم کنید .
وقتی از معکوسش پشته را خالی کردیم،چطور میخواین مرز بین u , v و WWR رو شناسایی کنید؟
۰
ارسال: #۴
  
RE: زبان CF هست یا نه؟
(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط: ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]
سلام
شاید تحلیلم درست نباشه و نکاتی رو ندونم ولی اینی که شما نوشتید به نظرم منظمه.
دلیل:
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.
حالا وقتی همه اینها که منظمند با هم الحاق بشوند. پس کلش میشه منظم.
اما در مورد اینکه اندازه u از v بیشتره که می تونیم با استفاده از یک DFA or NFA این کار رو انجام دهیم که این هم بیانگر منظم بودن این زبان است
امیدوارم درست استنباط کرده باشم
۰
ارسال: #۵
  
RE: زبان CF هست یا نه؟
اگه امکان داره در مورد این زبان هم بحث کنید.
(به نظر من این زبان حتی منظم هم هست ولی پارسه گفته این زبان مستقل از متن نیست.)
[tex]L=\left \{{W\epsilon {(a,b,c)^{*}}: N^{_{a}}(W)= N^{_{b}}(W)= N^{_{c}}(W)} \right \}\cap \left \{ \left( abc \right )^{*} \right \}[/tex]
پس با این استدلال شما زبان WW^R هم منظمه دیگه.که اینطور نیست و این زبان منظم نیست و مستقل از متنه.
(به نظر من این زبان حتی منظم هم هست ولی پارسه گفته این زبان مستقل از متن نیست.)
[tex]L=\left \{{W\epsilon {(a,b,c)^{*}}: N^{_{a}}(W)= N^{_{b}}(W)= N^{_{c}}(W)} \right \}\cap \left \{ \left( abc \right )^{*} \right \}[/tex]
(۳۰ آذر ۱۳۹۰ ۱۱:۱۳ ق.ظ)پشتکار نوشته شده توسط: سلامسلام.دوست عزیز.
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.
پس با این استدلال شما زبان WW^R هم منظمه دیگه.که اینطور نیست و این زبان منظم نیست و مستقل از متنه.
ارسال: #۶
  
RE: زبان CF هست یا نه؟
نقل قول:(۳۰ آذر ۱۳۹۰ ۱۱:۱۳ ق.ظ)پشتکار نوشته شده توسط: سلامسلام.دوست عزیز.
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.
پس با این استدلال شما زبان WW^R هم منظمه دیگه.که اینطور نیست و این زبان منظم نیست و مستقل از متنه.
به نظرتون صحبتهای من اشتباهه؟
مگه زبانهای منظم این قواعد رو ندارند.
میدونم که درست گفتید، ولی استدلالهای منم که اشتباه نیستند. مگر زبانهای منظم به الحاق یا معکوس بسته نباشند.
خیلی دوست دارم کسی این گیر منو برطرف کنه
ارسال: #۷
  
RE: زبان CF هست یا نه؟
(۳۰ آذر ۱۳۹۰ ۱۱:۲۶ ق.ظ)Mojtaba نوشته شده توسط: اگه امکان داره در مورد این زبان هم بحث کنید.
(به نظر من این زبان حتی منظم هم هست ولی پارسه گفته این زبان مستقل از متن نیست.)
[tex]L=\left \{{W\epsilon {(a,b,c)^{*}}: N^{_{a}}(W)= N^{_{b}}(W)= N^{_{c}}(W)} \right \}\cap \left \{ \left( abc \right )^{*} \right \}[/tex]
این زبان مستقل از متن نیست:
مثالشم:
a^n b^n c^n
(۱۱ دى ۱۳۹۰ ۰۶:۵۷ ب.ظ)Masoud05 نوشته شده توسط: برای همینم گفتم نامعینه دیگه .
منظورم اینه که چطور با یک پشته میتونید بفهمید که U>=V?
۰
ارسال: #۸
  
زبان CF هست یا نه؟
در مورد زبان اول . برای بررسی u>v ما یه پشته احتیاج داریم و برای بررسی wwr یک پشتهی دیگه .
در مورد زبان دوم . اگر درست نوشته باشین به نظر منظم میاد . شاید استدلال پارسه اینه که اشتراک یه زبان منظم با یه زبان حساس به متن، حساس به متنه .
در مورد زبان دوم . اگر درست نوشته باشین به نظر منظم میاد . شاید استدلال پارسه اینه که اشتراک یه زبان منظم با یه زبان حساس به متن، حساس به متنه .
ارسال: #۹
  
RE: زبان CF هست یا نه؟
(۳۰ آذر ۱۳۹۰ ۰۱:۴۵ ب.ظ)Bache Mosbat نوشته شده توسط: در مورد زبان اول . برای بررسی u>v ما یه پشته احتیاج داریم و برای بررسی wwr یک پشتهی دیگه .یعنی شما دارین در مورد زبان اول این مطلب را میرسونین که با یک پشته نمی توان این زبان را تشکیل داد.چرا؟
در مورد زبان دوم . اگر درست نوشته باشین به نظر منظم میاد . شاید استدلال پارسه اینه که اشتراک یه زبان منظم با یه زبان حساس به متن، حساس به متنه .
(اتفاقا با یک پشته میتونیم این کار را بکنیم البته به نظر من برای اون یک npda داریم ولی Dpda نداریم)
۰
ارسال: #۱۰
  
زبان CF هست یا نه؟
منظور شما اینه که با npda دیگه لزومی برای جدا کننده وجود نداره . این به شرطیه که u , v کنارش وجود نداشت یا شرط نداشتن . ولی وقتی u و v وجود دارن و شرط هم دارن باید یک جدا کننده وجود داشته باشه . پس با یه پشته حل نمی شه .
حالا دوستان دیگه نظر بدن! نظر من این بود .
ببینین چیزی که کار رو خراب می کنه عدم وجود جدا کننده و شرط روی u و v هست .
حالا دوستان دیگه نظر بدن! نظر من این بود .
ببینین چیزی که کار رو خراب می کنه عدم وجود جدا کننده و شرط روی u و v هست .
۰
ارسال: #۱۱
  
RE: زبان CF هست یا نه؟
(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط: ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]
به نظر من منظمه .. ببینید کافی است فقط دو تا حرف پشت سر هم مشابه پیدا کنید و اونها را به w و W^R نسبت بدید .. بقیه شو هم به U و V نسبت بدید... یه جوری که |U|>=|V|
۰
ارسال: #۱۲
  
زبان CF هست یا نه؟
مسلمه این زبان نه مستقل از متن هست نه منظم! اگر عضو * (a,b) بودن منظم بود!
ارسال: #۱۳
  
RE: زبان CF هست یا نه؟
(۳۰ آذر ۱۳۹۰ ۰۴:۵۴ ب.ظ)Bache Mosbat نوشته شده توسط: مسلمه این زبان نه مستقل از متن هست نه منظم! اگر عضو * (a,b) بودن منظم بود!سلام.
خیلی ممنون از اینه وقت گذاشتید و به این سوال جواب دادید.
من یک npda برای این زبان کشیدم (ضمیمه کردم) و با این احتمال گفتم که این زبان مستقل از متنه .لطفا اگه میشه دوستان یگ نگاهی بکنند و اگه ایرادی داره بهم بگن و اگه درست هست پس معلومه که این زبان مستقل از متنه.
قبلا از هماری های تمام دوستان کمال قدردانی را می نمایم.
۰
ارسال: #۱۴
  
زبان CF هست یا نه؟
سلام مرسی از سوالت . دقیقا سوالت تو ذهن من بود .
مستقل از متن نیست منظم هم نیست اما دلیلشو درست نمی فهمم چرا ؟ خواهشا بیشتر توضیح بدهید .
مستقل از متن نیست منظم هم نیست اما دلیلشو درست نمی فهمم چرا ؟ خواهشا بیشتر توضیح بدهید .
۰
۰
ارسال: #۱۶
  
RE: زبان CF هست یا نه؟
(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط: ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]
اگر به جای |U|>=|V|، عبارت |U|<=|V| یا |U|=|V| به کار رفته بود میتونستیم براش npda به طریق زیر ترسیم کنیم که مستقل از متن میشد.
اما من نتونستم برای شرط |U|>=|V| ماشینی ترسیم کنم.
دوستانی که نظرشون مبنی بر مستقل از متن بودن این زبانه، اگر مقدوره ماشین زیرو تغییر بدن یا حداقل بگن کدوم قسمت اصلاح بشه، مستقل از متن میشه؟
[tex]\delta \left( q0,a,z \right )=\left \{ \left( q0,az \right )\right \} , \delta \left( q0,b,z \right )=\left \{ \left( q0,bz \right )\right \},\delta \left( q0,a,a \right )=\left \{ \left( q0,aa \right ), \left (q1,\lambda \right )\right \},\delta \left( q0,b,b \right )=\left \{ \left( q0,bb \right ), \left (q1,\lambda \right )\right \},\delta \left( q0,a,b \right )=\left \{ \left( q0,ab \right )\right \},\delta \left( q0,b,a \right )=\left \{ \left( q0,ba \right )\right \},\delta \left( q1,a,a \right )=\left \{ \left( q1,\lambda \right )\right \},\delta \left( q1,b,b \right )=\left \{ \left( q1,\lambda \right )\right \}[/tex]
تا اینجا مربوط میشه به چک کردن wwR
از اینجا به بعد هم مال |U|<=|V|
[tex]\delta \left( q1,a,b \right )=\left \{ \left( q2,\lambda \right )\right \}, \delta \left( q1,b,a \right )=\left \{ \left( q2,\lambda \right )\right \}, \delta \left( q2,a,a \right )=\left \{ \left( q2,\lambda \right )\right \}, \delta \left( q2,a,b \right )=\left \{ \left( q2,\lambda \right )\right \}, \delta \left( q2,b,a \right )=\left \{ \left( q2,\lambda \right )\right \}, \delta \left( q2,b,b \right )=\left \{ \left( q2,\lambda \right )\right \}, \delta \left( q2,a,z \right )=\left \{ \left( q_{f},z\right )\right \}, \delta \left( q2,b,z \right )=\left \{ \left( q_{f},z \right )\right \}, \delta \left( q2,\lambda ,z \right )=\left \{ \left( q_{f},z \right )\right \}[/tex]
۰
ارسال: #۱۷
  
زبان CF هست یا نه؟
من فکر میکنم بتونم ماشین پشته ای غیرقطعی برای این زبان رسم کنم که قوانینش به صورت زیر هستند اما قبل از اینکه ماشینش رو بگم یه اشتباهی که دوستان مکررا توی قوانین ماشینشون تکرار کردن رو تذکر بدم وقتی طول جملات زبان برای ما اهمیت داره لزومی نداره وقتی a رو میخونید حتما a روی پشته بزارید و وقتی b رو می خونید b بزارید فقط کافیه یه علامت بزارید روی پشته
ماشین از سه قسمت تشکیل میشه
۱) خواندن رشته U
۲) خواندن رشته WWR
۳) خواندن رشته V
در ضمن در ماشینهای پشته ای فرض بر این هست که اگر ماشین در یک حالت غیرنهایی توقف کنه پس رشته پذیرفته نیست
برای قسمت اول به صورت زیر قوانین رو مینویسیم)
[tex]\delta \left( q0,a,z \right )=(q1,1z), \delta (q0,b,z)=(q1,1z)[/tex]
[tex]\delta (q1,a,1)=(q1,11), \delta (q1,b,1)=(q1,11)[/tex]
گذر از قسمت اول به دوم
[tex]\delta (q1,\lambda ,1)=(q2,1)[/tex]
قسمت دوم
[tex]\delta (q2,a,1)=(q3,1),\delta (q3,a,1)=(q5,1)[/tex]
[tex]\delta (q2,b,1)=(q4,1),\delta (q4,a,1)=(q5,1)[/tex]
گذر از قسمت دوم به سوم
[tex]\delta (q5,\lambda ,1)=(q6,1)[/tex]
قسمت سوم
[tex]\delta (q6,a,1)=(q7,\lambda ), \delta (q6,b,1)=(q7,\lambda )[/tex]
[tex]\delta (q7,a,1)=(q7,\lambda ), \delta (q7,b,1)=(q7,\lambda ), \delta (q7,\lambda ,1)=(q7,\lambda )[/tex]
[tex]\delta (q7,\lambda ,z)=(q8,z)[/tex]
فرض ما براین است که q8 حالت نهایی است
اگر سوالی داشتین درخدمتم
ماشین از سه قسمت تشکیل میشه
۱) خواندن رشته U
۲) خواندن رشته WWR
۳) خواندن رشته V
در ضمن در ماشینهای پشته ای فرض بر این هست که اگر ماشین در یک حالت غیرنهایی توقف کنه پس رشته پذیرفته نیست
برای قسمت اول به صورت زیر قوانین رو مینویسیم)
[tex]\delta \left( q0,a,z \right )=(q1,1z), \delta (q0,b,z)=(q1,1z)[/tex]
[tex]\delta (q1,a,1)=(q1,11), \delta (q1,b,1)=(q1,11)[/tex]
گذر از قسمت اول به دوم
[tex]\delta (q1,\lambda ,1)=(q2,1)[/tex]
قسمت دوم
[tex]\delta (q2,a,1)=(q3,1),\delta (q3,a,1)=(q5,1)[/tex]
[tex]\delta (q2,b,1)=(q4,1),\delta (q4,a,1)=(q5,1)[/tex]
گذر از قسمت دوم به سوم
[tex]\delta (q5,\lambda ,1)=(q6,1)[/tex]
قسمت سوم
[tex]\delta (q6,a,1)=(q7,\lambda ), \delta (q6,b,1)=(q7,\lambda )[/tex]
[tex]\delta (q7,a,1)=(q7,\lambda ), \delta (q7,b,1)=(q7,\lambda ), \delta (q7,\lambda ,1)=(q7,\lambda )[/tex]
[tex]\delta (q7,\lambda ,z)=(q8,z)[/tex]
فرض ما براین است که q8 حالت نهایی است
اگر سوالی داشتین درخدمتم
ارسال: #۱۸
  
RE: زبان CF هست یا نه؟
(۱۲ دى ۱۳۹۰ ۰۵:۲۰ ب.ظ)lsamimi نوشته شده توسط: من فکر میکنم بتونم ماشین پشته ای غیرقطعی برای این زبان رسم کنم که قوانینش به صورت زیر هستند اما قبل از اینکه ماشینش رو بگم یه اشتباهی که دوستان مکررا توی قوانین ماشینشون تکرار کردن رو تذکر بدم وقتی طول جملات زبان برای ما اهمیت داره لزومی نداره وقتی a رو میخونید حتما a روی پشته بزارید و وقتی b رو می خونید b بزارید فقط کافیه یه علامت بزارید روی پشتهدرسته، اما اینجا نباید مرز بین WWR از U ,V تشحیص داده بشه؟؟؟
اگر با هر ورودی a و b یک علامت تو پشته بذاریم چطور میشه wwR رو تشخیص داد.
شما در واقع به جای اینکه با هر ورودی، علامت به پشته اضافه کنید، در عوض، یک علامت یکسان تو پشته، پوش کردین، و state رو تغییر دادین.
(۱۲ دى ۱۳۹۰ ۰۵:۲۰ ب.ظ)lsamimi نوشته شده توسط: ماشین از سه قسمت تشکیل میشهبا ماشینی که ذکر کردین،فرضا رشته bbabbaa که باید توسط زبان پذیرفته بشه، اما در حالت غیر نهایی q1 یا q3 متوقف میشه و پذیرفته نیست.
۱) خواندن رشته U
۲) خواندن رشته WWR
۳) خواندن رشته V
در ضمن در ماشینهای پشته ای فرض بر این هست که اگر ماشین در یک حالت غیرنهایی توقف کنه پس رشته پذیرفته نیست
شایدم اشتباه مراحلشو پیش میرم.
میشه مراحل اشتقاقشو کوتاه ذکر کنید.
۰
ارسال: #۱۹
  
زبان CF هست یا نه؟
خوب برای همین میگیم ماشین پشته ای غیرقطعی
ماشین پشته ای غیرقطعی خودش مرز رشتهها را حدس می زند
در واقع اگر از بین اشتقاقهای متفاوت برای یک رشته یکی به حالت نهایی بیانجامد ماشین غیرقطعی آن رشته را می پذیرد پس برای ماشین بالا کافیست من یک اشتقاق را برای مثال شما نشان دهم
[tex](q0,bbabbaa,z)\Rightarrow (q1,babbaa,1z)\Rightarrow (q1,abbaa,11z)\Rightarrow (q1,bbaa,111z)\Rightarrow (q2,bbaa,111z)\Rightarrow (q4,baa,111z)\Rightarrow (q5,aa,111z)\Rightarrow (q6,aa,111z)\Rightarrow (q7,a,11z)\Rightarrow (q7,\lambda ,1z)\Rightarrow (q7,\lambda ,z)\Rightarrow (q8,\lambda ,z)[/tex]
و چون ماشین به حالت نهایی میرسه و رشته کامل خونده شده پس پذیرفته است
ماشین پشته ای غیرقطعی خودش مرز رشتهها را حدس می زند
در واقع اگر از بین اشتقاقهای متفاوت برای یک رشته یکی به حالت نهایی بیانجامد ماشین غیرقطعی آن رشته را می پذیرد پس برای ماشین بالا کافیست من یک اشتقاق را برای مثال شما نشان دهم
[tex](q0,bbabbaa,z)\Rightarrow (q1,babbaa,1z)\Rightarrow (q1,abbaa,11z)\Rightarrow (q1,bbaa,111z)\Rightarrow (q2,bbaa,111z)\Rightarrow (q4,baa,111z)\Rightarrow (q5,aa,111z)\Rightarrow (q6,aa,111z)\Rightarrow (q7,a,11z)\Rightarrow (q7,\lambda ,1z)\Rightarrow (q7,\lambda ,z)\Rightarrow (q8,\lambda ,z)[/tex]
و چون ماشین به حالت نهایی میرسه و رشته کامل خونده شده پس پذیرفته است
۰
ارسال: #۲۰
  
RE: زبان CF هست یا نه؟
مرسی، اشکالم برطرف شد
یه سوال دیگه:
اگر npda یه زبانیو پذیرش کنه، نباید رشته ای که عضو زبان نیستو بپذیره و به حالت پایانی بره؟
فرضا
این رشته:
babbabb عضو زبان نیست
اما با طی مراحل زیر به فاینال میرسه:
[tex]\delta \left( q0,b,z \right )=\left( q1,1z \right ), \delta \left( q1,a,1 \right )=\left( q1,11 \right ), \delta \left( q1,b,1 \right )=\left( q1,11 \right ), \delta \left( q1,\lambda ,1 \right )=\left( q2,1 \right ), \delta \left( q2,b,1 \right )=\left( q4,1 \right ), \delta \left( q4,a,1 \right )=\left( q5,1 \right ), \delta \left( q5,\lambda ,1 \right )=\left( q6,1 \right ), \delta \left( q6,b,1 \right )=\left( q7,\lambda \right ), \delta \left( q7,\lambda,1 \right )=\left( q7,\lambda \right ), \delta \left( q7,\lambda ,z \right )=\left( q8,z \right ),[/tex]
فکر کنم باید یه تغییراتی به قسمت سوم داده بشه
یه سوال دیگه:
اگر npda یه زبانیو پذیرش کنه، نباید رشته ای که عضو زبان نیستو بپذیره و به حالت پایانی بره؟
فرضا
این رشته:
babbabb عضو زبان نیست
اما با طی مراحل زیر به فاینال میرسه:
[tex]\delta \left( q0,b,z \right )=\left( q1,1z \right ), \delta \left( q1,a,1 \right )=\left( q1,11 \right ), \delta \left( q1,b,1 \right )=\left( q1,11 \right ), \delta \left( q1,\lambda ,1 \right )=\left( q2,1 \right ), \delta \left( q2,b,1 \right )=\left( q4,1 \right ), \delta \left( q4,a,1 \right )=\left( q5,1 \right ), \delta \left( q5,\lambda ,1 \right )=\left( q6,1 \right ), \delta \left( q6,b,1 \right )=\left( q7,\lambda \right ), \delta \left( q7,\lambda,1 \right )=\left( q7,\lambda \right ), \delta \left( q7,\lambda ,z \right )=\left( q8,z \right ),[/tex]
فکر کنم باید یه تغییراتی به قسمت سوم داده بشه
ارسال: #۲۱
  
RE: زبان CF هست یا نه؟
راستش من در نوشتن ماشین در قسمت دوم یه بی دقتی کردم در این مورد عذر میخوام باید به جای قانون:
[tex]\delta (q4,a,1)=(q5,1)[/tex]
قانون زیر رو می نوشتم
[tex]\delta (q4,b,1)=(q5,1)[/tex]
دلیلش اینه که ما با خوندن یه حرف b از حالت q2 به q4 وارد میشیم و باید در q4 هم یک b دیگر بخونیم که b دوم درواقع wR می باشد فکر کنم اینطوری مشکل اون جمله ای هم که مثال زدید حل میشه
[tex]\delta (q4,a,1)=(q5,1)[/tex]
قانون زیر رو می نوشتم
[tex]\delta (q4,b,1)=(q5,1)[/tex]
دلیلش اینه که ما با خوندن یه حرف b از حالت q2 به q4 وارد میشیم و باید در q4 هم یک b دیگر بخونیم که b دوم درواقع wR می باشد فکر کنم اینطوری مشکل اون جمله ای هم که مثال زدید حل میشه
۰
ارسال: #۲۲
  
RE: زبان CF هست یا نه؟
با تغییری که ذکر کردین، این رشته هم به فاینال میرسه اما جز زبان نیست.
abbaabbaa
abbaabbaa
ارسال: #۲۳
  
RE: زبان CF هست یا نه؟
۰
ارسال: #۲۴
  
زبان CF هست یا نه؟
سلام خواهرم برادرم
آخرش برای زبانی که U>=V هست نتیجه چی شد؟ مستقل از متن است ؟
آخرش برای زبانی که U>=V هست نتیجه چی شد؟ مستقل از متن است ؟
۰
ارسال: #۲۵
  
زبان CF هست یا نه؟
من با جواب آقا مسعود کاملا موافقم. یه تعداد a و b توی پشته به ازای رشته ورودی u میگیریم (در حالت اول). بعد میگیم اگه رشتمون و پشتمون یکجوربود به حالت دوم برو و چیزی پوش نکن. به ازای هر a,b از پشته یه حرف a یا b پاپ کن.
حالت دومون جوابه. چون حداقل تعداد w یه حرفه و چون نامعینه تمام حالاتو میشمره. اگه تعداد uها کمتر بود به $ میرسه و طبیعتاً قفل میکنه.
زبان دوم هم اگه قسمت سمت راست رو نداشت و یا زبان منهای اون قسمت شده بود حساس به متن بود. مطمئنین درست نوشتین؟ چون *(abc) مشخصه که منظمه.
حالت دومون جوابه. چون حداقل تعداد w یه حرفه و چون نامعینه تمام حالاتو میشمره. اگه تعداد uها کمتر بود به $ میرسه و طبیعتاً قفل میکنه.
زبان دوم هم اگه قسمت سمت راست رو نداشت و یا زبان منهای اون قسمت شده بود حساس به متن بود. مطمئنین درست نوشتین؟ چون *(abc) مشخصه که منظمه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close