قوانین بی‌فایده

قوانین بی فایده ،در علم کامپیوتر نظری، به ویژه در نظریه زبان رسمی، از دستور زبان رسمی آن دسته از قواعد تولید نماد هستند که غیرقابل دسترسی یا غیر مولد هستند به طوری که می‌توان هرگز به کار گرفته نشوند.

تعریف

با توجه به گرامر مستقل از متن ، نماد غیرپایانی x تولید کننده یا مولد نامیده می‌شود به طوریکه برای بعضی از رشته‌های w از نمادهای پایانی وجود داشته باشد اشتقاق X ⇒^* w . نماد پایانی X قابل دسترسی نامیده می‌شود اگر برای بعضی از رشته‌های α و β از نمادهای پایانی وجود داشته باشد اشتقاق S ⇒^* αXβ که در آن S نشان دهنده نماد شروع گرامر است . قانونی با نماد غیرقابل دسترس یا غیرمولد در سمت چپ آن ، می‌تواند از گرامر بدون تغییر دادن زبان پذیرفته شده ( با نام مستعار تولید ) حذف گردد . به همین ترتیب ، یک جایگزین حاوی چنین نمادی را می‌توان از سمت راست یک قانون ، بدون تغییر زبان حذف کرد .

چنین قوانین و جایگزین‌هایی را بی‌فایده می‌نامیم.

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

مثال‌ها

با تخصیص نمادهای غیر پایانی و پایانی ، به ترتیب به حروف بزرگ و کوچک، در گرامر منظم زیر با نماد شروع S داریم:

S → Bb | Cc | Ee

B → Bb | b

C → Cc | c

D → Bd | Cd | d

E → Ee

نماد غیرپایانی D (که برای سهولت با رنگ قرمز نشان داده شده) غیرقابل دسترس است و E (سبز) غیرمولد است. از این رو، حذف دو قانون آخر، زبان پذیرفته شده توسط گرامر را تغییر نمی‌دهد، همانطور که حذف جایگزین "| Ee" از سمت راست قانون S نیز گرامر را تغییر نمی‌دهد.

پاک کردن قوانین بی فایده

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

آیکن و مورفی الگوریتم fixpoint ی برای تشخیص اینکه کدام نمادهای غیرپایانی از یک گرامر درخت منظم داده شده غیرمولد هستند ارائه دادند .

منابع

• ویکی‌پدیای انگلیسی