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

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

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

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

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

مثال‌ها

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

$\{a^n{b}^n{c}^n{d}^n|n\ge 1\}$

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

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

$\{a^{2^n}|n\ge 0\}$

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

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

ویژگی‌ها

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

• گرامرهای نمایه‌سازی‌شده آهو (Aho)
• ماشین پشته‌ای مشبک یک‌طرفه آهو (Aho)
• گرامر ماکرو فیشر (Fischer)
• اتوماتای گریباخ (Greibach) با پشته‌هایی از پشته‌ها
• ویژگی‌های جبری میبیوم (Maibaum)

هایاشی لم تزریق را برای گرامرهای نمایه‌سازی‌شده تعمیم می‌داد. در مقابل، گیلمن لم کاهشی را برای زبان نمایه‌سازی‌شده ارائه کرد.

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

• وراثت چامسکی

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

• "NLP in Prolog" chapter on indexed grammars and languages