فرم نرمال گریباخ

در علوم کامپیوتر و نظریه زبان صوری، یک گرامر مستقل از متن را در فرم نرمال گریباخ (به انگلیسی: Greibach normal form) می‌گویند اگر سمت راست تمام قواعد تولید آن با یک نماد پایانی شروع شود و به طور اختیاری با بعضی متغیرها دنبال شود. یک فرم نادقیق، یک استثناء در این محدودیت قالب را می‌پذیرد و به رشته تهی (اپسیلون، ε) اجازه می‌دهد تا یک عضو از زبان توصیف شده باشد. این فرم نرمال توسط شِیلا گریباخ بنا نهاده شد و نام او را بر آن نهادند. به طور دقیقتر، یک گرامر مستقل از متن در یک فرم نرمال گریباخ می‌باشد اگر، تمام قواعد تولید آن به فرم زیر باشند:

${\displaystyle {A}}$ ${\displaystyle \longrightarrow }$ ${\displaystyle {a}}$${\displaystyle {A_{1}}{A_{2}}\ldots {A_{n}}}$

یا

${\displaystyle {S}}$ ${\displaystyle \longrightarrow }$${\displaystyle \varepsilon }$

که ${\displaystyle {A}}$ یک نماد غیرپایانی، ${\displaystyle {a}}$ یک نماد پایانی و ${\displaystyle {A_{1}}{A_{2}}\ldots {A_{n}}}$ یک دنباله (احتمالاً تهی) از نمادهای غیر پایانی است که شامل نماد غیر پایانی شروع نیست، ${\displaystyle {S}}$ نماد غیر پایانی شروع و ${\displaystyle \varepsilon }$ رشته تهی است.

این گرامر بازگشت چپ ندارد.

هر گرامر مستقل از متن قابل تبدیل به یک گرامر معادل در فرم نرمال گریباخ می‌باشد. ساختارهای متنوعی موجود است. بعضی از این ساختارها فرم دوم قانون را مجاز نمی‌کنند و نمی‌توان گرامرهای مستقل از متنی که می‌توانند رشته تهی تولید کنند را تبدیل کرد. برای چنین ساختاری، اندازهٔ گرامر ساخته شده در حالت کلی برابر با ${\displaystyle {)}}$ ${\displaystyle {n^{4}}}$ ${\displaystyle {(}}$ ${\displaystyle {O}}$است و اگر هیچ اشتقاقی از زبان اصلی شامل یک کاراکتر غیر پایانی تنها نباشد برابر ${\displaystyle {)}}$ ${\displaystyle {n^{3}}}$ ${\displaystyle {(}}$ ${\displaystyle {O}}$ است، که ${\displaystyle {n}}$ اندازهٔ گرامر اصلی است. این تبدیل می‌تواند مورد استفاده قرار گیرد تا ثابت کند که هر زبان مستقل از متن را می‌توان به وسیلهٔ یک ماشین پشته‌ای غیر قطعی پذیرفت.

اگر یک گرامر در فرم نرمال گریباخ و یک رشتهٔ مشتق پذیر با طول ${\displaystyle {n}}$ در این گرامر داده شده باشد، هر تحلیلگر بالا به پایین در عمق ${\displaystyle {n}}$ متوقف خواهد شد.

جستارهای وابسته

• فرم بکوس-نائور
• فرم نرمال چامسکی

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Greibach normal form». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۸ دی ۱۳۹۳.