نظریه گریباخ

تعاریف

با دادن مجموعه ∑ که معمولاً الفبا نامیده می‌شود، مجموعه نامحدود از همه زنجیره‌هایی که از اعضای مجموعه ∑ ساخته می‌شوند، با *∑ نشان داده می‌شود. یک زبان رسمی یک زیر مجموعه از *∑ است. اگر L1 و L2 زبان‌های رسمی هستند، نتایج محصول آن‌ها L1L2 به عنوان مجموعه {w1w2: w1 ∈ L1 ,w2 ∈ L2} از به هم پیوستگی زنجیره w1 از L1 با زنجیره w2 از L2، تعریف می‌شود. اگر L زبان رسمی است و a نمادی از ∑ باشد، خارج قسمت آن‌ها L/a به عنوان مجموعه {w: wa ∈ L} از همه زنجیره‌های که می‌تواند از اعضای L با اضافه کردن تعریف می‌شود. شیوه‌های مختلفی از نظریه زبان‌های رسمی معروفند که یک زبان رسمی را به وسیله توصیفی معین مثل گرامر رسمی یا دستگاه وضعیت – معین، نشان می‌دهند.
برای مثال با استفاده از الفبا {۰٬۱٬۲٬۳٬۴٬۵٬۶٬۷٬۸٬۹} = ∑، مجموعه *∑ شامل همه (تصاویر اعشاری) اعداد طبیعی، با راهنمایی صفرهای مجاز، و زنجیره خالی، به عنوان ε نشان داده می‌شود مجموعه Ldiu3 همه اعداد طبیعی قابل تقسیم بر ۳ زبان رسمی نامحدودی بالای ∑ است و به طور معینی بوسیله گرامر با قاعده زیر با نماد شروع S0 توصیف می‌شود: S0:
S0→ε |0 S0 |1 S2 |2 S2 |2 S1 |3 S0 |4 S2 |5 S1 |6 S0 |7 S2 |8 S1 |9 S0
S1→ 0 S1 |1 S0 |2 S2 |32 S1 |4 S0 |5 S2 |6 S1 |7 S0 |8 S2 |9 S1
S2→ 0 S2 |1 S1 |2 S0 |3 S2 |4 S1 |5 S0 |6 S2 |7 S1 |8 S0 |9 S2
مثال‌های زبان‌های محدود { ε,۱٬۲} و {G,2,4,6,8} هستند و نتایج آن‌ها {۰٬۲٬۴٬۶٬۸} { ε,۱٬۲} همان اعداد را تا ۲۸ می‌دهد. خارج قسمت مجموعه اولین اعداد تا ۱۰۰ با نماد ۲٬۴٬۷ بدین ترتیب زبان { ε,۱٬۳٬۴٬۶٬۹}. {} و { ε} را می‌دهد.

بیان رسمی نظریه

نظریه گریباخ مستقل از شیوه خاص توصیف یک زبان رسمی است. این نظریه فقط مجموعه C از زبان‌های رسمی بالای بر الفبای {#}∪∑ را در نظر می‌گیرد. همانند: - هر زبانی در C توصیفی معین دارد.
- هر زبان با قاعده بر {#}∪∑ در C است.
- با توصیف زبان‌های L1 , L2 عضو C و توصیف زبان با قاعده R عضو C، تعریفی از نتایج L1R و L2R، اجتماع L1∪L2 می‌توانند عملاً محاسبه شوند و
- برای هر عضو زبان L∈C یا *∑⊇L هر چند *∑=L باشد غیرقابل حل است.
فرض کنیم P هر زیر مجموعه با اهمیت از C باشد که شامل همه مجموعه‌های با قاعده روی {#}∪∑ است دو با هر نماد تنها در {#}∪∑ به زیر خارج قسمت نزدیک است. پس سؤال دربارهٔ این که L عضو P است، با توصیف داده شده یک زبان L عضو C است غیرقابل حل است.
اثبات:
فرض کنیم *∑⊇M مثل همان M∈C، اما M∉P. اما هر L∈C با *∑⊇L , (M#∑*)∪∑*(#L) = φ(L) را تعریف می‌کند. از تعریف L، تعریف (φ(L عملاً محاسبه می‌شود.
پس *∑=L اگر و فقط اگر φ(L)∈P باشد.
- اگر *∑=L، پس φ(L)=∑*#∑*، یک زبان با قاعده و بنابراین در P است.
- دیگر این که، یک Wϵ∑*\L وجود دارد و خارج قسمت (φ(L)/(#W هم ارز با M است؛ بنابراین با تکرار اعمال ویژگی بستار Closure – خارج قسمت φ(l)∈p علامت این است که M=φ(L)/(#W)∈P که با تعریف M تناقض دارد؛ بنابراین اگر عضویت در P برای (φ(L از توصیف آن، قطعی است بنابراین L’S با *∑ از تعریف آن که با تعریف C در تناقض است، برابر است.

کاربردها

با استفاده از نظریه گریباخ، می‌توان نشان داد که مسائل زیر غیرقابل حل هستند:
- آیا با گرامر مستقل از متن، یک زبان با قاعده توصیف می‌شود؟
اثبات: نوع زبان‌های مستقل از متن و مجموعه زبان‌های با قاعده، به ترتیب به ویژگی‌های C و P بالا می‌پردازد. (متقاعد می‌کند)
- آیا یک زبان مستقل از متن به طور ذاتی مبهم است؟
اثبات: نوع زبان‌های مستقل از متن و مجموعه زبان‌های مستقل از متن که به طور ذاتی مبهم نیستند، به ترتیب به ویژگی‌های C و P بالای می‌پردازد. (متقاعد می‌کند).
- آیا یک گرامر حساس به متن، یک زبان مستقل از متن را توصیف می‌کند؟
هم چنین ببینید گرامر مستقل از متن # در سطح پایین‌تر یا بالاتر سلسله مراتب چامسکی بودن.

یادداشت‌ها

۱- این موضوع به (1979) Ulmana Hopcradt اشاره دارد: P⊆C نیاز به شمولیت همه این زبان‌های با قاعده دارد.
۲- اگر L∈P پس Lla∈P برای هر {#}∪∑∋a
۳- وجود یک چنین M قلافدارهایی برای نیاز مبهم با اهمیت بودن P مورد نیاز است.
زبان‌های با قاعده، مستقل از متن هستند: گرامر مستقل از متن # زیر کلاس نزدیک به زبان‌های مستقل از متن با توجه به اتحاد و به هم پیوستگی (حتی کلی) هستند: گرامر مستقل از متن # ویژگی‌های بستار برابر با *∑ برای زبان‌های متن آزاد غیرقابل حل هستند. گرامر# شمولیت، زبان‌های با قاعده تحت خارج قسمت (حتی کلی) به هم نزدیک هستند، زبان # ویژگی‌های بستار