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

سلام دوستان
یه سوال در رابطه با زبان های منظم و مستقل از متن دارم
در مورد زبان های منظم باید تنها یک متغییر در سمت راست قانون تولید باشه درسته؟ در این صورت اگر گرامری دارای ۲ تا متغییر در سمت راست بود باید بگیم که منظم نیست درسته؟

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

اگر اون زبان رو بتونی با pda یا dpda طراحی کنی مستقل از متنه و اگه نتونی مستقل از متن نیست، مثلا وقتی که برای پیاده سازی به بیش از یک پشته نیاز داریم
مثال: [tex]a^{n}b^{n}c^{n}[/tex]

برای اثباتش هم میشه از لم پامپینگ استفاده کرد.

این رو هم اضافه کنم که زبانهای مستقل از متن مثل زبانهای منظم نیستن که طبق یک قانون خاص (فقط یک متغیر سمت راست) بشه از روی قیافه اونها حدس زد، برای مستقل از متن باید حداقل در ذهنتون سعی کنید اون رو با push down طراحی کنید. اگه راهی برای طراحی اون پیدا شد که هیچی، نشد میشه گفت زبان منظم نیست.

اگر بتونی برای یک زبان DFA یا NFA رسم کنی اون زبان منظم هست.

سلام.اولین ارسالم به مانشت رو اینجا انجام میدم.علاوه بر توضیحان بالا من اضافه میکنم که:
به نظرمن گاهی از طریق رسم pda میفهمیم مستقل از متنه و گاهی هم از این طریق که در نهایت پشته خالی باشه که به نظر من در صورتی که زبانی رو داشته باشیم از ظاهر زبان اگر تمرین خوب کرده باشیم میشه تشخیص داد که استفاده از پشته اش خالی میشه در نهایت
مثلا a^n b^n رو در نظر داشته باشین که با خواندن a در پشته A قرار میدیم و با خوندن ورودی از پشتهAرا برمیداریم پس پشته خالی شد این راحتتره تا رسمه PDA
میتونین این موضوع رو در مورد مثالهای زیر هم بفهمین:
a^n b c^n یا a^n b^m c^m d^n ودر مورد این مثال این تصور اشتباهه که در پشته وقتی به d میرسیم دیگه به a دسترسی نداریم چون bوc گذاشنها و برداشتهاشون در استک رو پشت سرهم انجام دادن و بعد از هر c که Aگذاشتیم سریعd میاد و ماAرا برمیداریم پس dبه aدسترسی داره و برای ایندو هم Bرا میگذاریم و برمیداریم پس پشته خالی میشه.
مثالی که گفتم از کتاب اکبری است این دقیقا همون چیزیست کهBEHDAD فرمودن