صفحه‌ها: ۱ ۲
برای همینم گفتم نامعینه دیگه .
(۳۰ آذر ۱۳۹۰ ۱۱:۲۶ ق.ظ)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?
(۱۱ دى ۱۳۹۰ ۰۶:۵۸ ب.ظ)reyhaneh64 نوشته شده توسط:اما زبان اول از نظر من نه تنها مستقل از متنه بلکه منظم هم هست( یخاطر اون اشتراکه )(30 آذر ۱۳۹۰ ۱۱:۲۶ ق.ظ)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?
برای اونم اگه w, معکوسش در پشته نباشه کاری نداره به تعداد v از پشته کاراکتر خارج میکنیم( یا پشته خالی میشه یا هنوز عضو داره --> بالای پشته علامت مخصوص قرار نداره )
(۱۱ دى ۱۳۹۰ ۱۲:۲۶ ق.ظ)Masoud05 نوشته شده توسط:(30 آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط: ایا زبان زیر مستقل از متن هست یا نه؟بنظر منم یه زبان مستقل از متن نامعینه! و با ۱ پشته ولی بصورت نامعین میشه اونو درستش کرد یعنی اول u رو تو پشته بزاریم و با توجه به خاصیت نامعین بودن ماشین w و معکوسش رو تشخیص بدیم و پشته رو از w و معکوسش خالی کنیم تا u داخلش باشه بعدش طول u , v رو بررسی کنیم .
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]
خوشحال میشم اگه اشتباه میکنم، راهنماییم کنید .
کسی برای این زبان نظر دیگه ای نداره
(۱۱ دى ۱۳۹۰ ۰۶:۵۸ ب.ظ)reyhaneh64 نوشته شده توسط:(30 آذر ۱۳۹۰ ۱۱:۲۶ ق.ظ)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
[tex]\left( abc \right )^{*}[/tex]
رو با [tex]\left \{ a,b,c \right \}^{*}[/tex]
اشتباه گرفتم.
اصلاح میکنم،مثالی که زدم اشتباه بود.
[tex]\left( abc \right )^{*}[/tex]
شامل:
رشته های abcabcabc....
که منظمه.
زبان دیگه هم:میدونیم که مستقل از متن نیست و حساس به متنه.
به نظر میاد اگر اشتراک بگیریم، همون زبان منظم تولید میشه.
(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)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]
من فکر میکنم بتونم ماشین پشته ای غیرقطعی برای این زبان رسم کنم که قوانینش به صورت زیر هستند اما قبل از اینکه ماشینش رو بگم یه اشتباهی که دوستان مکررا توی قوانین ماشینشون تکرار کردن رو تذکر بدم وقتی طول جملات زبان برای ما اهمیت داره لزومی نداره وقتی 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 حالت نهایی است
اگر سوالی داشتین درخدمتم
(۱۲ دى ۱۳۹۰ ۰۵:۲۰ ب.ظ)lsamimi نوشته شده توسط: من فکر میکنم بتونم ماشین پشته ای غیرقطعی برای این زبان رسم کنم که قوانینش به صورت زیر هستند اما قبل از اینکه ماشینش رو بگم یه اشتباهی که دوستان مکررا توی قوانین ماشینشون تکرار کردن رو تذکر بدم وقتی طول جملات زبان برای ما اهمیت داره لزومی نداره وقتی a رو میخونید حتما a روی پشته بزارید و وقتی b رو می خونید b بزارید فقط کافیه یه علامت بزارید روی پشتهدرسته، اما اینجا نباید مرز بین WWR از U ,V تشحیص داده بشه؟؟؟
اگر با هر ورودی a و b یک علامت تو پشته بذاریم چطور میشه wwR رو تشخیص داد.
شما در واقع به جای اینکه با هر ورودی، علامت به پشته اضافه کنید، در عوض، یک علامت یکسان تو پشته، پوش کردین، و state رو تغییر دادین.
(۱۲ دى ۱۳۹۰ ۰۵:۲۰ ب.ظ)lsamimi نوشته شده توسط: ماشین از سه قسمت تشکیل میشهبا ماشینی که ذکر کردین،فرضا رشته bbabbaa که باید توسط زبان پذیرفته بشه، اما در حالت غیر نهایی q1 یا q3 متوقف میشه و پذیرفته نیست.
۱) خواندن رشته U
۲) خواندن رشته WWR
۳) خواندن رشته V
در ضمن در ماشینهای پشته ای فرض بر این هست که اگر ماشین در یک حالت غیرنهایی توقف کنه پس رشته پذیرفته نیست
شایدم اشتباه مراحلشو پیش میرم.
میشه مراحل اشتقاقشو کوتاه ذکر کنید.
خوب برای همین میگیم ماشین پشته ای غیرقطعی
ماشین پشته ای غیرقطعی خودش مرز رشته‌ها را حدس می زند
در واقع اگر از بین اشتقاقهای متفاوت برای یک رشته یکی به حالت نهایی بیانجامد ماشین غیرقطعی آن رشته را می پذیرد پس برای ماشین بالا کافیست من یک اشتقاق را برای مثال شما نشان دهم
[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]
و چون ماشین به حالت نهایی میرسه و رشته کامل خونده شده پس پذیرفته است
مرسی، اشکالم برطرف شد
یه سوال دیگه:
اگر 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]
فکر کنم باید یه تغییراتی به قسمت سوم داده بشه
راستش من در نوشتن ماشین در قسمت دوم یه بی دقتی کردم در این مورد عذر میخوام باید به جای قانون:
[tex]\delta (q4,a,1)=(q5,1)[/tex]
قانون زیر رو می نوشتم
[tex]\delta (q4,b,1)=(q5,1)[/tex]
دلیلش اینه که ما با خوندن یه حرف b از حالت q2 به q4 وارد میشیم و باید در q4 هم یک b دیگر بخونیم که b دوم درواقع wR می باشد فکر کنم اینطوری مشکل اون جمله ای هم که مثال زدید حل میشه
با تغییری که ذکر کردین، این رشته هم به فاینال میرسه اما جز زبان نیست.
abbaabbaa
(۱۴ دى ۱۳۹۰ ۰۴:۴۸ ب.ظ)reyhaneh64 نوشته شده توسط: با تغییری که ذکر کردین، این رشته هم به فاینال میرسه اما جز زبان نیست.
abbaabbaa
خب این رشته که جز زبانه
u=abbaa
w=b
wR=b
v=aa
سلام خواهرم برادرم
آخرش برای زبانی که U>=V هست نتیجه چی شد؟ مستقل از متن است ؟
من با جواب آقا مسعود کاملا موافقم. یه تعداد a و b توی پشته به ازای رشته ورودی u میگیریم (در حالت اول). بعد میگیم اگه رشتمون و پشتمون یکجوربود به حالت دوم برو و چیزی پوش نکن. به ازای هر a,b از پشته یه حرف a یا b پاپ کن.
حالت دومون جوابه. چون حداقل تعداد w یه حرفه و چون نامعینه تمام حالاتو میشمره. اگه تعداد uها کمتر بود به $ میرسه و طبیعتاً قفل میکنه.
زبان دوم هم اگه قسمت سمت راست رو نداشت و یا زبان منهای اون قسمت شده بود حساس به متن بود. مطمئنین درست نوشتین؟ چون *(abc) مشخصه که منظمه.