نکات تستی کنکور نظریه زبانها - زبانهای مستقل از متن

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

برای هر گرامر مستقل از متن الگوریتمی وجود دارد که به ازای هر رشته w عضو گرامر در زمانی O(|w|^3) تجزیه ای برای آن پیدا کند. مثلا بوسیله الگوریتم CYK.

زبانهای مستقل از متن الگوریتم تشخیص تهی بودن و الگوریتم داشتن لاندا و الگوریتم برابر لاندا بودن را دارند.

زبانهای مستقل الگوریتم برابر بودن دو زبان را ندارند.

در گرامر ساده توجه شود که هیچ زوج (a,A) ای تکرار نباید بشوند.

الگوریتم تشخیص عضویت برای گرامرهای ساده O(w|) است.

گرامرهای ساده مبهم نیستند.

گرامر زبانهای منظم(نه گرامر منظم) میتواند مبهم باشد ولی زبانهای منظم نمیتوانند ذاتا مبهم باشند.

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

حذف قانون لاندا ممکن است موجب تولید قانون یکه شود ولی حذف قوانین یکه باعث ایجاد قانون لاندا نمیشود.

حذف قوانین بیفایده باعث کاهش پیچیدگی میشود.

هر زبان مستقل از متنی که لاندا ندارد را میتوان هم به فرم نرمال گریباخ برد و هم به فرم نرمال چامسکی.

گرامرهای ساده زیر مجموعه فرم نرمال گریباخ هستند.

چیزهایی که باید از کتاب خوانده شود: گرامرهای مستقل از متن. اشتقاق سمت چپ ترین و سمت راست ترین. درخت اشتقاق. تجزیه. جستجوی کامل. گرامر ساده(s-grammer). گرامر مبهم و زبان ذاتا مبهم.قانون جایگزینی. قوانین مفید و حذف قوانین بی فایده. قوانین لاندا و حذف لاندا. قوانین یکه(واحد) و حذف قوانین واحد. پیچیدگی گرامر. فرم نرمال چامسکی. فرم نرمال گریباخ. تبدیل گرامرها به فرم نرمال گریباخ و چامسکی. الگوریتم تجزیه CYK.