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

سلام
سوال!
گرامر مستقل از متن در چه صورتی قابل پیاده سازی با پشته در حالت خالی شدن پشته هست؟
در مورد پذیرش با حالت فاینال چطور؟

(10 بهمن 1392 05:08 ب.ظ)e.sharmi نوشته شده توسط: [ -> ]سلام
سوال!
گرامر مستقل از متن در چه صورتی قابل پیاده سازی با پشته در حالت خالی شدن پشته هست؟
در مورد پذیرش با حالت فاینال چطور؟

من یه سایه روشنهایی از این مسئله میدونم که خیلی دقیق نیست ولی شاید کمک کنه
واسه PDA های در حالت خالی و پایانی ، هردو را میتونیم به هم تبدیل کنیم و از این باب مشکلی نداریم
ولی وقتی DPDA میخواهیم بسازیم، دیگه این تبدیل وجود نداره وباید بر اساس زبان تصمیم گرفت
البته یه قانونی بود که ظاهرا مربوط به همین میشه که اگر رشته ای از زبان مستقل ، زیر رشته ای از رشته ی دیگر زبان نباشه ، میتونیم DPDA با خالی شدن پشته بنویسیم
مثلا این رشته با خالی شدن پشته امکانش نیست a^n b^n a^m b^m چون مثلا رشته aabb میتونه زیر رشته aabbaaabbb باشه
ولی در مورد DPDA با حالت پایانی باید زبان گرامر قطعی باشه تا بشه براش نوشت
مثلا a^n b^n a^m b^m را میشه با با DPDA پایانی نوشت
ولی a^n b^n a^m b^2m را نمیشه نوشت

n, mهای بالا همشون بزرگتر مساوی صفر هستند. فرمول نویسی مشکل داشت نتونستم با Tex بنویسم

منم این نکته رو تو نود درصد پارسه خوندم که برای هر npda یک npda معادل وجود دارد که در آن پشته در حالت پذیرش خالی باشد .
و تنها زبان های مستقل از متن معینی که هیچ رشته عضو زبان پیشوند رشته دیگر نباشد یک dpda معادل وجود دارد که در آن پشته در حالت پذیرش خالی باشد مثالشم که زدن.

سوال نظریه سال 83 رو یه نگاه بندازید.
یک سوال که ربانی داده ، گزینه 4 ام گفته پشته با حالت خالی شدن داره که غلطه.
پاسخی که من دارم گفته شده چون *L ، هم رشته لامبدا هم غیر لامبدا داره نمیشه براش DPDA با حالت خالی شدن پشته نوشت.
اینو میتونید توضیح بدید چرا ؟
یعنی چون لامبدا پیشوند هر رشته ای میتونه باشه ، پس نمیشه با حالت خالی شدن پشته براش DPDA نوشت؟
به طور خاص همون تشخیص از روی گرامر منظورم بود که لطف کردید توضیح دادید.
------------------------------------------------------------------------------------
در مورد اون مواردی که هر دوی شما توضیح دادید ، چیزی که من میدونم ، که البته در تایید خرف های شماست ، اینه :
معادل هر NPDA با حالت پایانی یک NPDA با حالت خالی شدن پشته وجود داره و بلعکس.
معادل هر DPDA با حالت پذیرش با پشته خالی یک DPDA با حالت فاینال وجود داره. ولی نه بلعکس.
در صورتی که هیچ رشته زبان پیشوند رشته دیگری نباشه ، میشه اونو با حالت خالی شدن پشته نوشت.

سلام. فکر کنم توی ارسالهای قدیمی مانشت درموردش صحبت شده بود. اونجا هم یه بحثی روی بستار ستاره شده بود که در اون حالت به مشکل میخوره.

(10 بهمن 1392 07:12 ب.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. فکر کنم توی ارسالهای قدیمی مانشت درموردش صحبت شده بود. اونجا هم یه بحثی روی بستار ستاره شده بود که در اون حالت به مشکل میخوره.

ممنون.
الان جواب سوالمو نمیشه کوتاه بگید؟
پست های انجمن زیاده نمیدونم کجا پیداش کنم

(10 بهمن 1392 08:04 ب.ظ)e.sharmi نوشته شده توسط: [ -> ]

(10 بهمن 1392 07:12 ب.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. فکر کنم توی ارسالهای قدیمی مانشت درموردش صحبت شده بود. اونجا هم یه بحثی روی بستار ستاره شده بود که در اون حالت به مشکل میخوره.

ممنون.
الان جواب سوالمو نمیشه کوتاه بگید؟
پست های انجمن زیاده نمیدونم کجا پیداش کنم

یادم نمیاد فقط میدونم روی زبانهایی که بستار ستاره میخوردن بحث شده بود.

(10 بهمن 1392 05:08 ب.ظ)e.shrm نوشته شده توسط: [ -> ]سلام
سوال!
گرامر مستقل از متن در چه صورتی قابل پیاده سازی با پشته در حالت خالی شدن پشته هست؟
در مورد پذیرش با حالت فاینال چطور؟

سلام

برای هر زبان مستقل از متن یک npda با پذیرش در حالت نهایی و پشته خالی وجود دارد و بالعکس
برای هر زبان مستقل از متن قطعی یک pda قطعی یا dpda با پذیرش در حالت نهایی وجود دارد و بالعکس
برای هر زبان مستقل از متن قطعی لزوما pda قطعی با پذیرش در حالت پشته خالی وجود ندارد و برای اینکه برای یک زبان مستقل از متن قطعی pda قطعی با پذیرش در حالت پشته خالی وجود داشته باشه باید در زبان هیچ رشته ای پیشوند رشته ی دیگری نباشد یعنی خاصیت prefix property برقرار باشد
دلیلش: اگر رشته های x وxy عضو زبان مستقل از متن قطعی L باشند اگر بخواهیم pda قطعی با پذیرش در حالت پشته خالی طراحی کنیم وقتی رشته x بعنوان پیشوند رشته xy مصرف شود پشته خالی می شود و دیگه ماشین نمی تونه به حرکتش ادامه دهد(گیر می کند)
PDA قطعی با پذیرش در حالت نهایی و pda قطعی با پذیرش در حالت پشته خالی معادل نیستند و قدرت اولی بیشتره

(15 بهمن 1392 05:58 ب.ظ)sara_omd نوشته شده توسط: [ -> ]

(10 بهمن 1392 05:08 ب.ظ)e.shrm نوشته شده توسط: [ -> ]سلام
سوال!
گرامر مستقل از متن در چه صورتی قابل پیاده سازی با پشته در حالت خالی شدن پشته هست؟
در مورد پذیرش با حالت فاینال چطور؟

سلام

برای هر زبان مستقل از متن یک npda با پذیرش در حالت نهایی و پشته خالی وجود دارد و بالعکس
برای هر زبان مستقل از متن قطعی یک pda قطعی یا dpda با پذیرش در حالت نهایی وجود دارد و بالعکس
برای هر زبان مستقل از متن قطعی لزوما pda قطعی با پذیرش در حالت پشته خالی وجود ندارد و برای اینکه برای یک زبان مستقل از متن قطعی pda قطعی با پذیرش در حالت پشته خالی وجود داشته باشه باید در زبان هیچ رشته ای پیشوند رشته ی دیگری نباشد یعنی خاصیت prefix property برقرار باشد
دلیلش: اگر رشته های x وxy عضو زبان مستقل از متن قطعی L باشند اگر بخواهیم pda قطعی با پذیرش در حالت پشته خالی طراحی کنیم وقتی رشته x بعنوان پیشوند رشته xy مصرف شود پشته خالی می شود و دیگه ماشین نمی تونه به حرکتش ادامه دهد(گیر می کند)
PDA قطعی با پذیرش در حالت نهایی و pda قطعی با پذیرش در حالت پشته خالی معادل نیستند و قدرت اولی بیشتره

مرسی . لطف کردید

من یه چیزی رو متوجه نمیشم وقتی میگن نمیشه زبان رو با خالی شدن پشته طراحی کنیم یعنی در یه مرحله پشته خالی شده ولی هنوز از ورودی مونده؟

(15 بهمن 1392 08:05 ب.ظ)maryam.raz نوشته شده توسط: [ -> ]من یه چیزی رو متوجه نمیشم وقتی میگن نمیشه زبان رو با خالی شدن پشته طراحی کنیم یعنی در یه مرحله پشته خالی شده ولی هنوز از ورودی مونده؟

شما فرض کن یه زبان مستقل از متن قطعی هم رشته ی aرو می پذیره و هم رشته ی abرو که به اینجور رشته ها می گن پیشوندی
اگه بخوایم ماشین با حالت خالی شدن پشته براش طراحی کنیم باید وقتی رشته ی a مصرف شد پشته را خالی کنیم تا رشته ی a پذیرفته شود و در این صورت با توجه به اینکه زبان از نوع قطعی است و با a نمی شود دو حرکت داشت برای تولید رشته ی ab هم باید از همین مسیر استفاده کنیم اما از اونجایی که بعد از مصرف رشته ی a پشته را خالی کردیم دیگه نمی تونیم با b حرکت داشته باشیم و ماشین گیر میکند.

(16 بهمن 1392 09:16 ق.ظ)sara_omd نوشته شده توسط: [ -> ]

(15 بهمن 1392 08:05 ب.ظ)maryam.raz نوشته شده توسط: [ -> ]من یه چیزی رو متوجه نمیشم وقتی میگن نمیشه زبان رو با خالی شدن پشته طراحی کنیم یعنی در یه مرحله پشته خالی شده ولی هنوز از ورودی مونده؟

شما فرض کن یه زبان مستقل از متن قطعی هم رشته ی aرو می پذیره و هم رشته ی abرو که به اینجور رشته ها می گن پیشوندی
اگه بخوایم ماشین با حالت خالی شدن پشته براش طراحی کنیم باید وقتی رشته ی a مصرف شد پشته را خالی کنیم تا رشته ی a پذیرفته شود و در این صورت با توجه به اینکه زبان از نوع قطعی است و با a نمی شود دو حرکت داشت برای تولید رشته ی ab هم باید از همین مسیر استفاده کنیم اما از اونجایی که بعد از مصرف رشته ی a پشته را خالی کردیم دیگه نمی تونیم با b حرکت داشته باشیم و ماشین گیر میکند.

فکرکنم متوجه شدم یعنی چون وقتی سر پشته a هست اونوقت مجبوریم یه حرکت تحت لامبرا داشته باشیم که پشته خالی شه یه حرکت هم تحت ورودی b ، که اینجوری غیر قطعی میشه درسته؟
ممنون از توضیح خوبت

(16 بهمن 1392 03:17 ب.ظ)maryam.raz نوشته شده توسط: [ -> ]

(16 بهمن 1392 09:16 ق.ظ)sara_omd نوشته شده توسط: [ -> ]

(15 بهمن 1392 08:05 ب.ظ)maryam.raz نوشته شده توسط: [ -> ]من یه چیزی رو متوجه نمیشم وقتی میگن نمیشه زبان رو با خالی شدن پشته طراحی کنیم یعنی در یه مرحله پشته خالی شده ولی هنوز از ورودی مونده؟

شما فرض کن یه زبان مستقل از متن قطعی هم رشته ی aرو می پذیره و هم رشته ی abرو که به اینجور رشته ها می گن پیشوندی
اگه بخوایم ماشین با حالت خالی شدن پشته براش طراحی کنیم باید وقتی رشته ی a مصرف شد پشته را خالی کنیم تا رشته ی a پذیرفته شود و در این صورت با توجه به اینکه زبان از نوع قطعی است و با a نمی شود دو حرکت داشت برای تولید رشته ی ab هم باید از همین مسیر استفاده کنیم اما از اونجایی که بعد از مصرف رشته ی a پشته را خالی کردیم دیگه نمی تونیم با b حرکت داشته باشیم و ماشین گیر میکند.

فکرکنم متوجه شدم یعنی چون وقتی سر پشته a هست اونوقت مجبوریم یه حرکت تحت لامبرا داشته باشیم که پشته خالی شه یه حرکت هم تحت ورودی b ، که اینجوری غیر قطعی میشه درسته؟
ممنون از توضیح خوبت

درسته چون اگه هر دو حرکت رو داشته باشیم غیرقطعی میشه وبا یه حرکت هم که نمیشه چون وقتی پشته رو واسه رشته ی a خالی کردیم دیگه نمی تونیم با b حرکت داشته باشیم و ماشین گیر می کنه