ماشین پشته‌ای جاسازی‌شده

یک ماشین پشته‌ای جاسازی‌شده (انگلیسی: Embedded pushdown automaton) یا EPDA یک مدل محاسباتی برای تجزیه زبان‌هایی که به وسیلهٔ گرامر درخت مجاور (TAG) تولید می‌شوند است. آن شبیه گرامر مستقل از متن ماشین پشته‌ای را تجزیه می‌کند به جز اینکه به جا استفاده از ماشین یک پشتهٔ ساده برای ذخیره سمبل‌ها، یک پشته از پشته‌های تأثیری که نمادها را ذخیره می‌کنند دارد، دادن گرامرهای درخت مجاور یک ظرفیت تولیدی بین گرامر مستقل از متن و گرامر حساس به متن، یا یک زیرمجموعه از گرامرهای حساس به متن ملایم است و ماشین پشته‌ای جاسازی شده نباید با ماشین پشته‌ای تودرتو که قدرت محاسباتی بیشتری دارد اشتباه گرفته شود.

تاریخچه و کاربرد

EPDAها ابتدا توسط K. Vijay-Shanker و در پایان‌نامه دکترایش تعریف شدند. آن‌ها برای تعریف‌های کامل تر از کلاس‌های گرامرهای حساس به متن ملایم درخواست شده‌اند و نقش مهمی در پالایش سلسله مراتب چامسکی داشته‌اند؛ بنابراین زیرگرامرهای متنوع، به‌طور مثال linear indexed grammar می‌تواند تعریف شود. EPDAها همچنین شروع‌کننده و ایفاکنندهٔ نقش مهمی در پردازش زبان طبیعی هستند.

در حالی که زبان‌های طبیعی به‌طور سنتی به وسیلهٔ گرامرهای مستقل از متن تجزیه و تحلیل می‌شده‌اند. transformational-generative grammar) وcomputational linguistics (این مدل برای زبان‌های با وابستگی ضربدری خوب کار نمی‌کند، از قبیل Dutch وضعیت‌ها برای یک EPDA خیلی مناسب است. یک تحلیل دقیق زبانی در دسترس است.

نظریه

یک EPDA یک ماشین با وضعیت‌های متناهی و یک مجموعه از پشته‌ها که از طریق پشته جاسازی شده به همدیگر دسترسی دارند، است. هر پشته شامل عناصری از الفبای پشته $\,\Gamma$ است و بنابراین ما یک عنصر از پشته را با $\,\sigma _{i}\in \Gamma ^{*}$ (که بستار کلینی است) تعریف می‌کنیم.

هر پشته سپس می‌تواند به لحاظ عناصرش تعریف شود؛ بنابراین ما پشتهٔ jام را با استفاده از نماد دو خنجر معنی می‌کنیم. $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$,جایی که نماد بعدی$\,\sigma _{j,k}$ قابل دستیابی در پشته است. پشته جاسازی شده از پشته می‌تواند به شکل زیر معنی شود.

$\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$

ما یک EPDA را به وسیلهٔ یک ۷تایی تعریف می‌کنیم.

$\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})$

مجموعهٔ محدودی از وضعیت‌ها است. $\,Q$

یک مجموعهٔ محدود از الفبای ورودی است. $\,\Sigma$

$\,\Gamma$ مجموعهٔ متناهی از الفبای پشته است.

$\,q_{0}\in Q$ وضعیت شروع است.

مجموعهٔ وضعیت‌های پایانی است. $\,Q_{\textrm {F}}\subseteq Q$

نماد شروع پشته است. $\,\sigma _{0}\in \Gamma$

$\,\delta :Q\times \Sigma \times \Gamma \rightarrow S$تابع انتقال است که در آن $\,S$ یک زیرمجموعهٔ متناهی از $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ است.

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

یک وضعیت داده شده به صورت زیر تعریف می‌شود:

$\,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}$

که در آن $\ ,q$ وضعیت جاری و $\,\Upsilon$ها پشته‌های داخل پشتهٔ جاسازی شده هستند و $\,\Upsilon _{m}$ پشتهٔ جاری است و برای یک رشتهٔ ورودی $\,x=x_{1}x_{2}\in \Sigma ^{*}$، $\,x_{1}$ بخشی از رشته است که با خواندن نماد جاری توسط head در حال حاضر به وسیلهٔ ماشین پردازش می‌شود و$\,x_{2}$ بخشی است که پردازش خواهد شد. دقت داشته باشید که رشتهٔ تهی $\,\epsilon \in \Sigma$ به‌طور ضمنی به عنوان نماد پایان تعریف شده یعنی اگر ماشین در یک وضعیت پایانی باشد وقتی رشتهٔ تهی خوانده می‌شود، تمام رشتهٔ ورودی پذیرفته شده‌است و در غیراین صورت رد شده‌است. این رشته‌های پذیرفته شده عناصر زبان ما هستند.

$\,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}$

که در آن $\,q_{\textrm {F}}\in Q_{\textrm {F}}$و $\,\rightarrow _{M}^{*}$ تابع انتقال است که با توجه به تجزیهٔ رشته هر چند بار که لازم باشد استفاده شده‌است.

یک تعریف غیررسمی از EPDA همچنین می‌تواند در Joshi, Schabes (1997), Sect.7, p.23-25 پیدا شود.

EPDA ی k سطحی و بند سلسله مراتب

به‌طور دقیق تر سلسله مراتب زبان‌ها را که مرتبط با کلاس حساس به متن ملایم است را تعریف می‌کند که به وسیلهٔ David J. Weir انجام شده‌است. بر اساس کار سلسله مراتب کنترل زبان Weir عبارت است از سلسله مراتب مجموعه قابل شمارش از کلاس‌های زبان که سطح اول در آن به عنوان مستقل از متن و سطح دوم کلاس از درخت مجاور و سه گرامر دیگر است.

در زیر بعضی از. ویژگی‌های زبان‌های سطح k در سلسله مراتب آورده شده‌است:

زبان‌های سطح k در کلاس زبان سطح (k+1) هستند.

زبان‌های سطح k می‌توانند در زمان $O(n^{3\cdot 2^{k-1}})$ تجزیه شوند.

سطح k شامل زبان $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ هست اما شامل $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}$ نیست.

سطح k شامل زبان $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ هست اما شامل $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$نیست.

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Embedded pushdown automaton». در دانشنامهٔ ویکی‌پدیای انگلیسی.