تالار گفتمان مانشت

ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]

(30 آذر 1390 11:06 ق.ظ)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 این کار رو انجام دهیم که این هم بیانگر منظم بودن این زبان است
امیدوارم درست استنباط کرده باشم

اگه امکان داره در مورد این زبان هم بحث کنید.
(به نظر من این زبان حتی منظم هم هست ولی پارسه گفته این زبان مستقل از متن نیست.)
[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]

---

(30 آذر 1390 11:13 ق.ظ)پشتکار نوشته شده توسط: [ -> ]سلام
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.

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

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

(30 آذر 1390 01:45 ب.ظ)Bache Mosbat نوشته شده توسط: [ -> ]در مورد زبان اول . برای بررسی u>v ما یه پشته احتیاج داریم و برای بررسی wwr یک پشته‌ی دیگه .
در مورد زبان دوم . اگر درست نوشته باشین به نظر منظم میاد . شاید استدلال پارسه اینه که اشتراک یه زبان منظم با یه زبان حساس به متن‌، حساس به متنه .

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

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

(30 آذر 1390 11:06 ق.ظ)Mojtaba نوشته شده توسط: [ -> ]ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]

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

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

(30 آذر 1390 04:54 ب.ظ)Bache Mosbat نوشته شده توسط: [ -> ]مسلمه این زبان نه مستقل از متن هست نه منظم! اگر عضو * (a,b) بودن منظم بود!

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

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

نقل قول:

(30 آذر 1390 11:13 ق.ظ)پشتکار نوشته شده توسط: [ -> ]سلام
بدلیل اینکه u,w,v همه گی متعلق به a,b پلاس هستند پس منظمند.
بدلیل اینکه زبانهای منظم نسبت به معکوس بشته اند پس معکوس w هم منظمه و زبان منظم هم نسبت به الحاق بسته است.

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

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

(30 آذر 1390 09:33 ب.ظ)پشتکار نوشته شده توسط: [ -> ]به نظرتون صحبتهای من اشتباهه؟
مگه زبانهای منظم این قواعد رو ندارند.
میدونم که درست گفتید، ولی استدلالهای منم که اشتباه نیستند. مگر زبانهای منظم به الحاق یا معکوس بسته نباشند.
خیلی دوست دارم کسی این گیر منو برطرف کنه

بله . حرف شما در صورتی صحیحه که وابستگی بین اجزاش نباشه . مثلا طبق صحبت شما a^nb^n هم منظمه . ولی این وابستگی کارو خراب می کنه .
اگر w یه زبون بود . و w^r اینورس یه زبان دیگه منظم بودن! یعنی هر کدوم مستقل از هم باشن .

---

(30 آذر 1390 07:50 ب.ظ)Mojtaba نوشته شده توسط: [ -> ]خیلی ممنون از اینه وقت گذاشتید و به این سوال جواب دادید.
من یک npda برای این زبان کشیدم (ضمیمه کردم) و با این احتمال گفتم که این زبان مستقل از متنه .لطفا اگه میشه دوستان یگ نگاهی بکنند و اگه ایرادی داره بهم بگن و اگه درست هست پس معلومه که این زبان مستقل از متنه.
قبلا از هماری های تمام دوستان کمال قدردانی را می نمایم.

من منظورتون رو از c نمی فهمم . یعنی شما یه جدا کننده وارد می کنین؟ این کار مجازه؟ جایی دیدین تو npda?

مگه تو W Wr استدلالمون این نیست که ماشین با استفاده از عدم قطعیت خود میت.نه نقطه وسط ورودی رو با آزمایش و خطا‌، حدس بزنه؟
پس تو این مورد هم بدون جدا کننده میتونه U و V رو جدا کنه.و با یک پشته میشه طراحی بشه پس مستقل از متنه!

(30 آذر 1390 11:06 ق.ظ)Mojtaba نوشته شده توسط: [ -> ]ایا زبان زیر مستقل از متن هست یا نه؟
لطفا با ذکر دلیل جواب بدین.
(نظر من اینه که مستقل از متنه ولی کتاب پارسه گفته که مستقل از متن نیست)
[tex]L={UWW^{R}V:U,V,W\epsilon {(a,b)}^{ },|U|>=|V|}[/tex]

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

(11 دى 1390 12:26 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]بنظر منم یه زبان مستقل از متن نامعینه! و با ۱ پشته ولی بصورت نامعین میشه اونو درستش کرد یعنی اول u رو تو پشته بزاریم و با توجه به خاصیت نامعین بودن ماشین w و معکوسش رو تشخیص بدیم و پشته رو از w و معکوسش خالی کنیم تا u داخلش باشه بعدش طول u , v رو بررسی کنیم .
خوشحال میشم اگه اشتباه میکنم‌، راهنماییم کنید .

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