تالار گفتمان مانشت
راه تستی برای شناسایی زبان dpda از npda چیست ؟ - نسخه‌ی قابل چاپ

راه تستی برای شناسایی زبان dpda از npda چیست ؟ - bahar - 04 آذر ۱۳۸۹ ۰۴:۱۲ ب.ظ

آیا راه تستی جدای از اون دوشرط که توی کتاب لینز برای شناسایی این که یکه زبان مستقل از متن dpda هست یا نه وجود داره ؟&(q,a,b)بیش از یکه عضو نداشته باشن و &(q,lambda,b) خالی نیست آنگاه &(q,c,b)خالی باشد

راه تستی برای شناسایی زبان dpda از npda چیست ؟ - sepid - 04 آذر ۱۳۸۹ ۰۸:۰۶ ب.ظ

فک نکنم روش تستی داشته باشه.
ولی گاهی از روی شکل زبان میشه فهمید.
مثال:
زبان {a^nb^n}اجتماع {a^nb^2n} رو در نظر بگیر
این زبان به این علت که ماشین با دیدن هرa به طور قطعی نمیتونه تصمیم بگیره که باید دو تا صفر در پشته بزاره یا یکی در نتیجه مستقل از متن معین نیست.
یا زبان {a^nb^mc^k:n=m or m=k}
فرض کنیم با دیدنa عناصری وارد پشته شدند، حال با دیدن اولین b ماشین دو تصمیم مینواند بگیرد یا اینکه این b رو با aهای قبلی تطبیق بده یا اینکه به ازای هر b عناصری وارد پشته کند تا با c تطبیق داده بشه پس زبان مستقل از متن معین نیست.