(۱۱ دى ۱۳۹۰ ۱۲:۲۶ ق.ظ)Masoud05 نوشته شده توسط:  بنظر منم یه زبان مستقل از متن نامعینه! و با ۱ پشته ولی بصورت نامعین میشه اونو درستش کرد یعنی اول u رو تو پشته بزاریم و با توجه به خاصیت نامعین بودن ماشین w و معکوسش رو تشخیص بدیم و پشته رو از w و معکوسش خالی کنیم تا u داخلش باشه بعدش طول u , v رو بررسی کنیم .
خوشحال میشم اگه اشتباه میکنم‌، راهنماییم کنید .

وقتی از معکوسش پشته را خالی کردیم،چطور میخواین مرز بین u , v و WWR رو شناسایی کنید؟

(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط:  ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
$L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}$

سلام
شاید تحلیلم درست نباشه و نکاتی رو ندونم ولی اینی که شما نوشتید به نظرم منظمه.
دلیل:
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.
حالا وقتی همه اینها که منظمند با هم الحاق بشوند. پس کلش میشه منظم.
اما در مورد اینکه اندازه u از v بیشتره که می تونیم با استفاده از یک DFA or NFA این کار رو انجام دهیم که این هم بیانگر منظم بودن این زبان است
امیدوارم درست استنباط کرده باشم

اگه امکان داره در مورد این زبان هم بحث کنید.
(به نظر من این زبان حتی منظم هم هست ولی پارسه گفته این زبان مستقل از متن نیست.)
$L=\left \{{W\epsilon {(a,b,c)^{*}}‌: N^{_{a}}(W)= N^{_{b}}(W)= N^{_{c}}(W)} \right \}\cap \left \{ \left( abc \right )^{*} \right \}$

---

(۳۰ آذر ۱۳۹۰ ۱۱:۱۳ ق.ظ)پشتکار نوشته شده توسط:  سلام
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.

سلام.دوست عزیز.
پس با این استدلال شما زبان WW^R هم منظمه دیگه.که اینطور نیست و این زبان منظم نیست و مستقل از متنه.

نقل قول:

(۳۰ آذر ۱۳۹۰ ۱۱:۱۳ ق.ظ)پشتکار نوشته شده توسط:  سلام
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.

سلام.دوست عزیز.
پس با این استدلال شما زبان WW^R هم منظمه دیگه.که اینطور نیست و این زبان منظم نیست و مستقل از متنه.

به نظرتون صحبتهای من اشتباهه؟
مگه زبانهای منظم این قواعد رو ندارند.
میدونم که درست گفتید، ولی استدلالهای منم که اشتباه نیستند. مگر زبانهای منظم به الحاق یا معکوس بسته نباشند.
خیلی دوست دارم کسی این گیر منو برطرف کنه

(۳۰ آذر ۱۳۹۰ ۱۱:۲۶ ق.ظ)Mojtaba نوشته شده توسط:  اگه امکان داره در مورد این زبان هم بحث کنید.
(به نظر من این زبان حتی منظم هم هست ولی پارسه گفته این زبان مستقل از متن نیست.)
$L=\left \{{W\epsilon {(a,b,c)^{*}}‌: N^{_{a}}(W)= N^{_{b}}(W)= N^{_{c}}(W)} \right \}\cap \left \{ \left( abc \right )^{*} \right \}$

---

این زبان مستقل از متن نیست:
مثالشم:
a^n b^n c^n

---

(۱۱ دى ۱۳۹۰ ۰۶:۵۷ ب.ظ)Masoud05 نوشته شده توسط:  برای همینم گفتم نامعینه دیگه .

منظورم اینه که چطور با یک پشته میتونید بفهمید که U>=V?

در مورد زبان اول . برای بررسی u>v ما یه پشته احتیاج داریم و برای بررسی wwr یک پشته‌ی دیگه .
در مورد زبان دوم . اگر درست نوشته باشین به نظر منظم میاد . شاید استدلال پارسه اینه که اشتراک یه زبان منظم با یه زبان حساس به متن‌، حساس به متنه .

(۳۰ آذر ۱۳۹۰ ۰۱:۴۵ ب.ظ)Bache Mosbat نوشته شده توسط:  در مورد زبان اول . برای بررسی u>v ما یه پشته احتیاج داریم و برای بررسی wwr یک پشته‌ی دیگه .
در مورد زبان دوم . اگر درست نوشته باشین به نظر منظم میاد . شاید استدلال پارسه اینه که اشتراک یه زبان منظم با یه زبان حساس به متن‌، حساس به متنه .

یعنی شما دارین در مورد زبان اول این مطلب را میرسونین که با یک پشته نمی توان این زبان را تشکیل داد.چرا؟
(اتفاقا با یک پشته میتونیم این کار را بکنیم البته به نظر من برای اون یک npda داریم ولی Dpda نداریم)

منظور شما اینه که با npda دیگه لزومی برای جدا کننده وجود نداره . این به شرطیه که u , v کنارش وجود نداشت یا شرط نداشتن . ولی وقتی u و v وجود دارن و شرط هم دارن باید یک جدا کننده وجود داشته باشه . پس با یه پشته حل نمی شه .
حالا دوستان دیگه نظر بدن! نظر من این بود .
ببینین چیزی که کار رو خراب می کنه عدم وجود جدا کننده و شرط روی u و v هست .

(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط:  ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
$L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}$

به نظر من منظمه .. ببینید کافی است فقط دو تا حرف پشت سر هم مشابه پیدا کنید و اون‌ها را به w و W^R نسبت بدید .. بقیه شو هم به U و V نسبت بدید... یه جوری که |U|>=|V|

مسلمه این زبان نه مستقل از متن هست نه منظم! اگر عضو * (a,b) بودن منظم بود!

(۳۰ آذر ۱۳۹۰ ۰۴:۵۴ ب.ظ)Bache Mosbat نوشته شده توسط:  مسلمه این زبان نه مستقل از متن هست نه منظم! اگر عضو * (a,b) بودن منظم بود!

سلام.
خیلی ممنون از اینه وقت گذاشتید و به این سوال جواب دادید.
من یک npda برای این زبان کشیدم (ضمیمه کردم) و با این احتمال گفتم که این زبان مستقل از متنه .لطفا اگه میشه دوستان یگ نگاهی بکنند و اگه ایرادی داره بهم بگن و اگه درست هست پس معلومه که این زبان مستقل از متنه.
قبلا از هماری های تمام دوستان کمال قدردانی را می نمایم.

سلام مرسی از سوالت . دقیقا سوالت تو ذهن من بود .
مستقل از متن نیست منظم هم نیست اما دلیلشو درست نمی فهمم چرا ؟ خواهشا بیشتر توضیح بدهید .

برای همینم گفتم نامعینه دیگه .

(۳۰ آذر ۱۳۹۰ ۱۱:۰۶ ق.ظ)Mojtaba نوشته شده توسط:  ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
$L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}$

اگر به جای |U|>=|V|‌، عبارت |U|<=|V| یا |U|=|V| به کار رفته بود میتونستیم براش npda به طریق زیر ترسیم کنیم که مستقل از متن میشد.
اما من نتونستم برای شرط |U|>=|V| ماشینی ترسیم کنم.
دوستانی که نظرشون مبنی بر مستقل از متن بودن این زبانه، اگر مقدوره ماشین زیرو تغییر بدن یا حداقل بگن کدوم قسمت اصلاح بشه‌، مستقل از متن میشه؟

$\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 \}$

تا اینجا مربوط میشه به چک کردن wwR
از اینجا به بعد هم مال |U|<=|V|
$\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 \}$

من فکر میکنم بتونم ماشین پشته ای غیرقطعی برای این زبان رسم کنم که قوانینش به صورت زیر هستند اما قبل از اینکه ماشینش رو بگم یه اشتباهی که دوستان مکررا توی قوانین ماشینشون تکرار کردن رو تذکر بدم وقتی طول جملات زبان برای ما اهمیت داره لزومی نداره وقتی a رو میخونید حتما a روی پشته بزارید و وقتی b رو می خونید b بزارید فقط کافیه یه علامت بزارید روی پشته
ماشین از سه قسمت تشکیل میشه
۱) خواندن رشته U
۲) خواندن رشته WWR
۳) خواندن رشته V
در ضمن در ماشینهای پشته ای فرض بر این هست که اگر ماشین در یک حالت غیرنهایی توقف کنه پس رشته پذیرفته نیست
برای قسمت اول به صورت زیر قوانین رو مینویسیم)
$\delta \left( q0,a,z \right )=(q1,1z), \delta (q0,b,z)=(q1,1z)$
$\delta (q1,a,1)=(q1,11), \delta (q1,b,1)=(q1,11)$
گذر از قسمت اول به دوم
$\delta (q1,\lambda ,1)=(q2,1)$
قسمت دوم
$\delta (q2,a,1)=(q3,1),\delta (q3,a,1)=(q5,1)$

$\delta (q2,b,1)=(q4,1),\delta (q4,a,1)=(q5,1)$

گذر از قسمت دوم به سوم
$\delta (q5,\lambda ,1)=(q6,1)$

قسمت سوم
$\delta (q6,a,1)=(q7,\lambda ), \delta (q6,b,1)=(q7,\lambda )$

$\delta (q7,a,1)=(q7,\lambda ), \delta (q7,b,1)=(q7,\lambda ), \delta (q7,\lambda ,1)=(q7,\lambda )$

$\delta (q7,\lambda ,z)=(q8,z)$

فرض ما براین است که q8 حالت نهایی است
اگر سوالی داشتین درخدمتم

(۱۲ دى ۱۳۹۰ ۰۵:۲۰ ب.ظ)lsamimi نوشته شده توسط:  من فکر میکنم بتونم ماشین پشته ای غیرقطعی برای این زبان رسم کنم که قوانینش به صورت زیر هستند اما قبل از اینکه ماشینش رو بگم یه اشتباهی که دوستان مکررا توی قوانین ماشینشون تکرار کردن رو تذکر بدم وقتی طول جملات زبان برای ما اهمیت داره لزومی نداره وقتی a رو میخونید حتما a روی پشته بزارید و وقتی b رو می خونید b بزارید فقط کافیه یه علامت بزارید روی پشته

درسته، اما اینجا نباید مرز بین WWR از U ,V تشحیص داده بشه؟؟؟
اگر با هر ورودی a و b یک علامت تو پشته بذاریم چطور میشه wwR رو تشخیص داد.

شما در واقع به جای اینکه با هر ورودی، علامت به پشته اضافه کنید، در عوض، یک علامت یکسان تو پشته‌، پوش کردین، و state رو تغییر دادین.

(۱۲ دى ۱۳۹۰ ۰۵:۲۰ ب.ظ)lsamimi نوشته شده توسط:  ماشین از سه قسمت تشکیل میشه
۱) خواندن رشته U
۲) خواندن رشته WWR
۳) خواندن رشته V
در ضمن در ماشینهای پشته ای فرض بر این هست که اگر ماشین در یک حالت غیرنهایی توقف کنه پس رشته پذیرفته نیست

با ماشینی که ذکر کردین،فرضا رشته bbabbaa که باید توسط زبان پذیرفته بشه، اما در حالت غیر نهایی q1 یا q3 متوقف میشه و پذیرفته نیست.
شایدم اشتباه مراحلشو پیش میرم.
میشه مراحل اشتقاقشو کوتاه ذکر کنید.

خوب برای همین میگیم ماشین پشته ای غیرقطعی
ماشین پشته ای غیرقطعی خودش مرز رشته‌ها را حدس می زند
در واقع اگر از بین اشتقاقهای متفاوت برای یک رشته یکی به حالت نهایی بیانجامد ماشین غیرقطعی آن رشته را می پذیرد پس برای ماشین بالا کافیست من یک اشتقاق را برای مثال شما نشان دهم

$(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)$

و چون ماشین به حالت نهایی میرسه و رشته کامل خونده شده پس پذیرفته است

مرسی‌، اشکالم برطرف شد
یه سوال دیگه:
اگر npda یه زبانیو پذیرش کنه، نباید رشته ای که عضو زبان نیستو بپذیره و به حالت پایانی بره؟
فرضا
این رشته:
babbabb عضو زبان نیست
اما با طی مراحل زیر به فاینال میرسه:

$\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 ),$

فکر کنم باید یه تغییراتی به قسمت سوم داده بشه

راستش من در نوشتن ماشین در قسمت دوم یه بی دقتی کردم در این مورد عذر میخوام باید به جای قانون:
$\delta (q4,a,1)=(q5,1)$

قانون زیر رو می نوشتم
$\delta (q4,b,1)=(q5,1)$
دلیلش اینه که ما با خوندن یه حرف 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) مشخصه که منظمه.