زبان نمایه‌سازی‌شده

زبان‌های نمایه سازی شده یک دسته از زبان‌های صوری می‌باشند که توسط آلفرد آهو (Alfred Aho)[1] کشف شده است، آن‌ها توسط گرامرهای نمایه سازی شده شرح داده می‌شوند و می‌توانند با ماشین پشته‌ای مشبک شناخته شوند.[2]

زبان‌های نمایه سازی شده یک زیر مجموعهٔ مناسب از زبان‌های حساس به متن می‌باشند.[1] آن‌ها به عنوان یک خانواده انتزاعی از زبان‌ها (علاوه بر AFL کامل) واجد شرایط می‌باشند و ازین رو بسیار از خصوصیات بستاری را برآورده کنند. با این حال، آنها تحت اشتراک یا متمم بسته نیستند.[1]

دسته زبان‌های نمایه سازی شده اهمیت عملی بسیاری در پردازش زبان طبیعی به عنوان محاسباتی مقرون به صرفه در تعمیم زبان‌های مستقل از متن دارد، چرا که گرامر نمایه سازی شده می‌تواند بسیاری از محدودیت‌های غیرمحلی که در زبان‌های طبیعی رخ می‌دهد را توصیف کند.

جرالد گزدلر (۱۹۸۸)[3] و ویجی-شنکر (۱۹۸۷)[4] یک گروه از زبان حساس به متن ملایم را که در حال حاضر به عنوان گرامر نمایه سازی شده خطی (LIG)[5] شناخته شده است را معرفی کردند. گرامر نمایه سازی شده خطی محدودیت‌های بیشتری نسبت به گرامر نمایه سازی شده (IG) دارند. گرامر نمایه سازی شده خطی هم‌ارزی ضعیفی (از نظر تولید همان دسته از زبان) در مقابل گرامر درخت مجاورت می‌باشد.[6]

مثال‌ها

زبان‌های زیر نمایه سازی شده می‌باشند اما مستقل از متن نیستند:

\{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}

[3]

\{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}

[2]

این دو زبان نیز نمایه سازی شده می‌باشند، اما تحت خصوصیات Gazdar حساس به متن خفیف نمی‌باشند:

\{a^{2^{n}}|n\geq 0\}

[2]

\{www|w\in \{a,b\}^{+}\}

[3]

از سوی دیگر، زبان زیر نمایه سازی شده نمی‌باشد:[7]

$\{(ab^{n})^{n}|n\geq 0\}$

ویژگی‌ها

هاپکرافت (جان هاپکرافت) و اولمان(Ullman) تمایل داشتند که زبان‌های نمایه سازی شده را به عنوان یک دسته طبیعی در نظر بگیرند، ازین رو آنها توسط چندین صور تولید شده‌اند، مانند: [9]

گرامرهای نمایه سازی شده آهو (Aho)[1]
ماشین پشته‌ای مشبک یک طرفه آهو (Aho)[10]
گرامر ماکرو فیشر (Fischer)[11]
اتوماتای گریباخ (Greibach) با پشته‌هایی از پشته‌ها[12]
ویژگی‌های جبری میبیوم (Maibaum)[13]

هایاشی (Hayashi)[14] لم تزریق را برای گرامرهای نمایه سازی شده تعمیم می‌داد. در مقابل، گیلمن[7][15] لم کاهشی را برای زبان نمایه سازی شده ارائه کرد.

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

وراثت چامسکی
گرامر نمایه سازی شده

منابع

Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM. 15 (4): 647–671. doi:10.1145/321479.321488.
Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages". In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. pp. 69–94.
http://search.proquest.com/docview/303610666
Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 31. ISBN 978-3-642-14846-0.
Laura Kallmeyer (16 August 2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 32. ISBN 978-3-642-14846-0.
Gilman, Robert H. (1996). "A shrinking lemma for indexed languages". Theoretical Computer Science. 163 (1–2): 277–281. doi:10.1016/0304-3975(96)00244-7. ISSN 0304-3975.
Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 390. ISBN 0-201-02988-X.
Introduction to automata theory, languages, and computation,[8] Bibliographic notes, p.394-395
Alfred Aho (1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529.
Michael J. Fischer (1968). "Grammars with Macro-Like Productions". Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). pp. 131–142.
Sheila A. Greibach (1970). "Full AFL's and Nested Iterated Substitution" (PDF). Information and Control. 16 (1): 7–35. doi:10.1016/s0019-9958(70)80039-0.
T.S.E. Maibaum (1974). "A Generalized Approach to Formal Languages" (PDF). J. Computer and System Sciences. 8 (3): 409–439. doi:10.1016/s0022-0000(74)80031-0.
T. Hayashi (1973). "On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem". Publication of the Research Institute for Mathematical Sciences. Research Institute for Mathematical Sciences. 9 (1): 61–92. doi:10.2977/prims/1195192738.
Robert H. Gilman (Sep 1995). "A Shrinking Lemma for Indexed Languages".

پیوند به بیرون

"NLP in Prolog" chapter on indexed grammars and languages

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[aho1968-1] Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM. 15 (4): 647–671. doi:10.1145/321479.321488.

[partee_etal_1990-2] Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.

[gazdar1998-3] Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages". In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. pp. 69–94.

[4] ttp://search.proquest.com/docview/303610666

[Kallmeyer2010-5] Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 31. ISBN 978-3-642-14846-0.

[Kallmeyer2010b-6] Laura Kallmeyer (16 August 2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 32. ISBN 978-3-642-14846-0.

[Gilman.1996-7] Gilman, Robert H. (1996). "A shrinking lemma for indexed languages". Theoretical Computer Science. 163 (1–2): 277–281. doi:10.1016/0304-3975(96)00244-7. ISSN 0304-3975.

[hopcroft_ullman_1979-8] Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 390. ISBN 0-201-02988-X.

[9] Introduction to automata theory, languages, and computation,[8] Bibliographic notes, p.394-395

[10] Alfred Aho (1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529.

[11] Michael J. Fischer (1968). "Grammars with Macro-Like Productions". Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). pp. 131–142.

[12] Sheila A. Greibach (1970). "Full AFL's and Nested Iterated Substitution" (PDF). Information and Control. 16 (1): 7–35. doi:10.1016/s0019-9958(70)80039-0.

[13] T.S.E. Maibaum (1974). "A Generalized Approach to Formal Languages" (PDF). J. Computer and System Sciences. 8 (3): 409–439. doi:10.1016/s0022-0000(74)80031-0.

[14] T. Hayashi (1973). "On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem". Publication of the Research Institute for Mathematical Sciences. Research Institute for Mathematical Sciences. 9 (1): 61–92. doi:10.2977/prims/1195192738.

[15] Robert H. Gilman (Sep 1995). "A Shrinking Lemma for Indexed Languages".