۰
subtitle
ارسال: #۱
  
راه تستی برای شناسایی زبان dpda از npda چیست ؟
آیا راه تستی جدای از اون دوشرط که توی کتاب لینز برای شناسایی این که یکه زبان مستقل از متن dpda هست یا نه وجود داره ؟&(q,a,b)بیش از یکه عضو نداشته باشن و &(q,lambda,b) خالی نیست آنگاه &(q,c,b)خالی باشد
۰
ارسال: #۲
  
راه تستی برای شناسایی زبان dpda از npda چیست ؟
فک نکنم روش تستی داشته باشه.
ولی گاهی از روی شکل زبان میشه فهمید.
مثال:
زبان {a^nb^n}اجتماع {a^nb^2n} رو در نظر بگیر
این زبان به این علت که ماشین با دیدن هرa به طور قطعی نمیتونه تصمیم بگیره که باید دو تا صفر در پشته بزاره یا یکی در نتیجه مستقل از متن معین نیست.
یا زبان {a^nb^mc^k:n=m or m=k}
فرض کنیم با دیدنa عناصری وارد پشته شدند، حال با دیدن اولین b ماشین دو تصمیم مینواند بگیرد یا اینکه این b رو با aهای قبلی تطبیق بده یا اینکه به ازای هر b عناصری وارد پشته کند تا با c تطبیق داده بشه پس زبان مستقل از متن معین نیست.
ولی گاهی از روی شکل زبان میشه فهمید.
مثال:
زبان {a^nb^n}اجتماع {a^nb^2n} رو در نظر بگیر
این زبان به این علت که ماشین با دیدن هرa به طور قطعی نمیتونه تصمیم بگیره که باید دو تا صفر در پشته بزاره یا یکی در نتیجه مستقل از متن معین نیست.
یا زبان {a^nb^mc^k:n=m or m=k}
فرض کنیم با دیدنa عناصری وارد پشته شدند، حال با دیدن اولین b ماشین دو تصمیم مینواند بگیرد یا اینکه این b رو با aهای قبلی تطبیق بده یا اینکه به ازای هر b عناصری وارد پشته کند تا با c تطبیق داده بشه پس زبان مستقل از متن معین نیست.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close