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

زبان‌های نمایه‌سازی‌شده یک دسته از زبان‌های صوری می‌باشند که توسط آلفرد آهو^[۱] کشف شده است، این زبان‌ها توسط گرامرهای نمایه‌سازی‌شده شرح داده می‌شوند و می‌توانند با ماشین پشته‌ای مشبک شناخته شوند.^[۲]

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

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

جرالد گزدلر (۱۹۸۸)^[۳] و ویجی شنکر (۱۹۸۷)^[۴] یک گروه از زبان حساس به متن را که در حال حاضر به‌عنوان گرامر نمایه‌سازی‌شده خطی (LIG)^[۵] شناخته‌شده است را معرفی کردند. گرامر نمایه‌سازی‌شده خطی محدودیت‌های بیشتری نسبت به گرامر نمایه‌سازی‌شده (IG) دارند. گرامر نمایه‌سازی‌شده خطی هم‌ارزی ضعیفی (از نظر تولید همان دسته از زبان) در مقابل گرامر درخت مجاورت می‌باشد.^[۶]

مثال‌ها

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

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

^[۳]

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

^[۲]

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

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

^[۲]

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

^[۳]

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

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

ویژگی‌ها

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

گرامرهای نمایه‌سازی‌شده آهو (Aho)^[۱]
ماشین پشته‌ای مشبک یک‌طرفه آهو (Aho)^[۱۰]
گرامر ماکرو فیشر (Fischer)^[۱۱]
اتوماتای گریباخ (Greibach) با پشته‌هایی از پشته‌ها^[۱۲]
ویژگی‌های جبری میبیوم (Maibaum)^[۱۳]

هایاشی ^[۱۴] لم تزریق را برای گرامرهای نمایه‌سازی‌شده تعمیم می‌داد. در مقابل، گیلمن^[۷]^[۱۵] لم کاهشی را برای زبان نمایه‌سازی‌شده ارائه کرد.

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

وراثت چامسکی

منابع

↑ ^۱٫۰ ^۱٫۱ ^۱٫۲ ^۱٫۳ 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 (ed.). 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,^[۸] 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". {{cite journal}}: Cite journal requires |journal= (help)

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

"NLP in Prolog" chapter on indexed grammars and languages

P ≟ NP

این یک مقالهٔ خرد مرتبط به علوم نظری رایانه است. می‌توانید با گسترش آن به ویکی‌پدیا کمک کنید.

[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 (ed.). 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,^[۸] 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". {{cite journal}}: Cite journal requires |journal= (help)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]

[۱۴]

[۱۵]

[۸]