نظریه گریباخ

نظریه گریباخ (انگلیسی: Greibach's theorem)

در علوم کامپیوتری تئوری، مخصوصاً در نظریه زبان‌های رسمی نظریه گریباخ بیان می‌کند که خواص معینی از انواع زبان‌های رسمی، غیرقابل حل هستند. این موضوع بعد از دانشمند کامپیوتر شیلا گریباخ، که اولین بار آن را در سال ۱۹۶۳ ثابت کرده بود، نام گذاری شد.

تعاریف

با دادن مجموعه ∑ که معمولاً الفبا نامیده می‌شود، مجموعه نامحدود از همه زنجیره‌هایی که از اعضای م1L2 بجموعه ∑ ساخته می‌شوند، با *∑ نشان داده می‌شود. یک زبان رسمی یک زیر مجموعه از *∑ است. اگر L1 و L2 زبان‌های رسمی هستند، نتایج محصول آن‌ها Lه عنوان مجموعه {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 مورد نیاز است.

زبان‌های با قاعده، مستقل از متن هستند: گرامر مستقل از متن # زیر کلاس نزدیک به زبان‌های مستقل از متن با توجه به اتحاد و به هم پیوستگی (حتی کلی) هستند: گرامر مستقل از متن # ویژگی‌های بستار برابر با *∑ برای زبان‌های متن آزاد غیرقابل حل هستند. گرامر# شمولیت، زبان‌های با قاعده تحت خارج قسمت (حتی کلی) به هم نزدیک هستند، زبان # ویژگی‌های بستار

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Greibach's theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۴ ژوئن ۲۰۱۵.
• Sheila – غیرقابل حل بودن مسئله گنگ برای گرامرهای خطی حداقل …
• Sheila – یادداشتی بر ویژگی‌های غیرقابل حل بودن زبان‌های رسمی …
• John – تعریف نظریه خودکاری، زبان‌ها و محاسبه …