اتوماتون پشته‌ای

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

اتوماتون پشته‌ای صوری سازی این مفهوم شهودی، یک تعریف دقیق از آتاماتون پشته ای بدست می دهد. تعریف: یک پذیرنده ی پشته ای غیر قطعی(npda) به شکل ( M=(Q،∑، Γ، ∂،qo،z،F

نمایش داده می شود، بطوری که در آن

  • Qیک مجموعه نامتناهی از حالت های داخلی واحد کنترل است،
  • ∑الفبای ورودی است،
  • Γ یک مجموعه متناهی از نشانه ها که الفبای پشته نامیده می شود،
  • (∂:Q×(∑υ{⋋})×Γ تابع انتقال،
  • Q0€Q حالت اولیه واحد کنترل است،
  • z€Γ≤Qنشانه ی شروع پشته است

شکل پیچیده دامنه و برد تابع انتقال نیاز به بررسی بیشتری دارد.آرگومان ∂ حالت های فعلی واحد کنترل، نشانه ورودی فعلی و نشانه ی بالای پشته است.نتیجه یک مجموعه از زوج های (q،x) می باشد که در آن q حالت بعدی در واحد کنترل است.رشته ی x نیز به جای نشانه ای که اکنون بر روی پشته است قرار می گیرد.به خاطر داشته باشیم که دومین آرگومان∂ ممکن است برابر با⋋ باشد؛ بنابراین حرکتی که هیچ نشانه ای را از ورودی مصرف نمی کند امکان پذیر است. به چنین حرکتی، یک انتقال -⋋ گفته می شود.همچنین ∂ طوری تعریف شده است که به نشانه ی موجود بر روی پشته نیاز دارد. اگر پشته خالی باشد هیچ حرکتی ممکن نیست.بالاخره اینکه، برد تابع انتقال یابد باید یک زیرمجموعه محدود باشد زیرا Q×Γ نامتناهی بوده و بنابراین دارای تعداد نامتناهای زیرمجموعه است. در حالیکه یک npda ممکن است . انتخاب های زیادی برای حرکت داشته باشد، این انتخاب‌ها باید به یک مجموعه متناهی از حالت‌ها محدود باشد. فرض کنید که مجموعه ی قانون های انتقال یک npdaشامل ∂(q1،a،b)={(q2،cd)،(q3،⋋) باشد . اگر در یک لحظه ی مشخص، واحد کنترل در حالت q1، نشانه ورودی برابر با a و نشانه موجود در بالای پشته نیز برابر با b باشد، یکی از دو مورد زیر اتقاف می افتد: 1)واحد کنترل به حالت q2 می رودو رشته ی cd جایگزین نشانه ی بالای پشته می شود. 2)واحد کنترل به حالت q3 می شود و نشانه ی b نیز از بالای پشته حذف می شود. در این روش نشانه گذاری، اضافه کردن یک رشته به پشته، به صورت نشانه به نشانه و از انتهای راست آن رشته انجام می شود.

عملکرد[ویرایش]

نمودار اتومات پشته ای

اتومات پشته ای با ماشین‌های حالات متناهی در دو چیز متفاوت اند:

1-آن ها میتوانند از قسمت بالا پشته استفاده کنند 

که کدان انتقال صورت گیرد.

2-آن ها میتوانند پشته را به عنوان بخشی از انجام 

انتقال دستکاری کنند.

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

انوماتون پشته ای میتواند بخشی از پشته را برای انتقال دستکاری کنند.ماشین های وضیعت محدود حالت جدیدی را که نتیجه انتقال است را انتخاب میکند.دستکاری ها یا میتوانند به صورت وارد و یا خارج کردن نماد خاصی از پشته باشد.دستکاری شدن یا نشدن توسط جدول انتقال معلوم میشود.

با هم شدن:با توجه به سیگنال ورودی، وضعیت فعلی و نماد پشته،اتومات میتواند دنبال کند انتقال را به حالت دیگر و به صورت اختیاری پشته را دستکاری کند.

به طور کلی اتوماتون پشتهای ممکن است محاسبات متعددی روی سیگنال های ورودی انجام دهد.اگر در هر موقعیت فقط یک انتقال برای ادامه محاسبات باشد در آن صورت نتیجه اتوماتون پشتهای قطعی است.(DPDA) در غیر این صورت اتوماتون پشتهای غیر قطعی میشود(NDPDA) .تنها در گرامر مستقل از متن میشود گرامر های مبهم را از طریق DPDA یعنی گرامرمستقل از متن قطعی,شناخت.تمام گرامر های مستقل از متن , قطعی نیستند و مشکل شناخت گرامر مستقل از متن قطعی حل نشده است.[۱] به عنوان یک نتیجه از بالا DPDA یک نوع به شدت ضعیف تر از PDA است و هیچ الگوریتم برای تبدیل PDA به معادل DPDA وجود ندارد.

اگرما اجازه دسترسی به 2 پشته به جای یک پشته داشتیم آنگاه وسیله ای قوی به مانند ماشین تورینگ داشتیم.اتوماتون خطی محدود ابزاری قوی تر از اتوماتون پشته ای است ولی از ماشین تورینگ ضعیف تر است.

تعریف رسمی[ویرایش]

مااز نماد های استاندارد زبان رسمی استفاده میکنیم: \Gamma^{*} به رشته ای از حروف و \Gamma و \varepsilon به رشته ای خالی اشاره میکند.

یک PDA عموما با 7 عنصر مشخص میشود:

M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ q_{0},\ Z, \ F) که :
  • \, Q مجموعه محدودی از حالت هاست.
  • \,\Sigma مجموعه محدودی است که الفبای ورودی میگویند.
  • \,\Gamma مجموعه محدودی است که الفبای پشته گویند.
  • \,\delta زیرمجموعه ای از Q \times  (\Sigma \cup\{\varepsilon\})  \times \Gamma \times Q \times \Gamma^* (رابطه انتقال)
  • \,q_{0}\in\, Q حالت آغازین.
  • \ Z\in\,\Gamma نماد پشته اولیه.
  • F\subseteq Q مجکوعه ای از حالات پذیرفته شده.

عنصر (p,a,A,q,\alpha) \in \delta تابع انتقال M است.

  • \,\delta تابع انتقال است.

محاسبات


مرحله از اتوماتون پشته ای

به منظور معنا شناسی از ماشین پایین فشردنی شرح وضعیت فعلی معرفی شده است.هر سه عنصر (p,w,\beta) \in Q \times \Sigma^* \times \Gamma^* شرح لخظه ای M گویند(ID), که شامل حالت کنونی و قسمتی از نوار ورودی که خوانده نشده است و محتویات پشته میشود.رایطه انتقال \delta رابطه گام به گام \vdash_{M} of M در هر لحظه تعریف میکند.برای ساختار (p,a,A,q,\alpha) \in \delta مرحله (p,ax,A\gamma) \vdash_{M} (q,x,\alpha\gamma), برای هر x\in\Sigma^* و هر \gamma\in \Gamma^* وجود دارد.

اتوماتون پشته ای عموما تبعیض ناپذیرند که در حالت لحظه ای (p,w,\beta) چندین راه ممکن است باشد.هر کدام از این روش ها ممکن است انتخاب شوند.با تعاریف بالا در هر مرحله سمبل منفرد از بالای پشته خارج میشود و با نماد هایی که لازم تر است جایگزین میشود.به عنوان نتیجه هیچ مرحله ای که زمانی پشته خالی است انجام نمیشود.

محاسبات اتوماتون پشته ای دنباله ای از مراحل است.محاسبات با حالت اولیه q_{0} و سمبل پشته ای اولیه Z و رشته ورودی wآغاز میشود, بنابراین در حالت اولیه داریم (q_{0},w,Z) .دو حالت پذیرش اولیه داریم.روش دیگر پذیرش از طریق حالت نهایی است.به این معنی است که پس از خواندن ورودی آن ماشین به یک حالت مورد قبول میرسد و یا به وسیله پشته خالی پذیرش میشود.حالت پذیرش برای اولین بار با استفاده از حافظه داخلی و حلت دوم توسط حافظه خارجی است.

بعبارت دیگر تعریف کنیم:

  1. \gamma \in \Gamma^* \} و f \in F با L(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (f,\varepsilon,\gamma)
  2. q \in Q \} با N(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (q,\varepsilon,\varepsilon)

برای هر اتوماتون پشته ای این دو رابطه ربطی به هم ندارند.شاید در بعضی جا ها با هم برابر باشند ولی دلیلی بر یکی بودن نیست.مشخصات ماشین نیز باید حالت مورد نظر را پذیرش می باشد.در تمامی اتوماتون پشته ای 2 حالت پذیرش بیانگر زبان یکی اند.

توصیف آنی[ویرایش]

توصیف آنی یک سه‌تایی منظم به فرم (q,w,α) است که در آن:

  • 1- q یک حالت باشد.
  • 2- w باقیمانده‌ی رشته‌ی ورودی باشد.
  • 3- α محتویات پشته باشد.

را یک توصیف آنی از ماشین پشته‌ای می‌نامیم.

  • دقت کنید که در نگارش فوق سمت چپ‌ترین نماد α، بالاترین عضو پشته است. ضمناً برای نمایش حروف الفبا معمولاً از b,a,.... ، برای نمایش حرف‌های پشته از Y,X,... و برای نمایش محتویات پشته از γ,β,αو... استفاده می‌شود.

مثال[ویرایش]

در پایین شرح یک PDA را داریم که زبان \{0^n1^n \mid n \ge 0 \} را از طریق حالت نهایی نشان میدهد:

PDA for \{0^n1^n \mid n \ge 0\} (by final state)

)]]

M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ p,\ Z, \ F), که:

Q = \{ p,q,r \}

\Sigma = \{0, 1\}

\Gamma = \{A, Z\}

q_{0} = p

F = \{r\}

\delta متشکل از شش دستورالعمل های زیر است:

(p,0,Z,p,AZ), (p,0,A,p,AA), (p,\epsilon,Z,q,Z), (p,\epsilon,A,q,A), (q,1,A,q,\epsilon), و (q,\epsilon,Z,r,Z).

آشنایی با روند محاسبات[ویرایش]

محاسبات پذیرش شده برای: 0011

در زیر فرق محاسبات را در رشته های متفاوت در PDA نشان میدهیم: الف)رشته ورودی:0011 .با توجه به حرکت از حالت p به حالت q , انواع مختلف محاسبات داریم. و فقط یکی از اینان قبول است.

(i) (p,0011,Z) \vdash (q,0011,Z) \vdash (r,0011,Z).حالت نهایی مورد پذیرش است ولی ورودی این راه خواندن را قبول نمیکند.
(ii) (p,0011,Z) \vdash (p,011,AZ) \vdash (q,011,AZ).مراحل دیگر امکان پذیر نیست.
(iii) (p,0011,Z) \vdash (p,011,AZ) \vdash (p,11,AAZ) \vdash (q,11,AAZ)  \vdash (q,1,AZ) \vdash (q,\epsilon,Z)  \vdash (r,\epsilon,Z).پذیرش محاسبه: در حالت پذیرش به پایان میرسد.، در حالی که ورودی کامل خوانده شده است.

ب)رشته ورودی=00111.انواع مختلف محاسبه داریم.هیچ کدام مورد قبول نیست.

(i) (p,00111,Z) \vdash (q,00111,Z) \vdash (r,00111,Z).حالت نهایی مورد پذیرش است ولی ورودی این راه خواندن را قبول نمیکند.
(ii) (p,00111,Z) \vdash (p,0111,AZ) \vdash (q,0111,AZ).مراحل دیگر امکان پذیر نیست.
(iii) (p,00111,Z) \vdash (p,0111,AZ) \vdash (p,111,AAZ) \vdash (q,111,AAZ)  \vdash (q,11,AZ) \vdash (q,1,Z)  \vdash (r,1,Z). حالت نهایی مورد پذیرش است ولی ورودی این راه خواندن را قبول نمیکند.

اتوماتون پشته ای عمومی GPDA[ویرایش]

یک نوع PDA است که رشته هایی را با طول مساوی درون پشته مینویسد وتمام رشته هارا از پشته خارج میکند.

یک GPDA 6 عنصر تعریف میشود.

M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ q_{0}, \ F) که:

\Sigma\,, \Gamma\,, q0 و F همان تعریف در PDA دارد و

\,\delta: Q \times  \Sigma_{\epsilon}  \times \Gamma^{*} \longrightarrow P( Q \times \Gamma^{*} ) تابع انتقال است.

قوانین محاسبه در GPDA مانند PDA است با این تفاوت که ai+1 و bi+1 ها به جای نماد , رشته است. یکی می تواند اثبات تحلیلی برای هم ارزی از GPDA و PDA ها را با استفاده از شبیه سازی زیر تدوین و فرموله کند:

Let \delta(q1, w, x1x2...xm) \longrightarrow (q2, y1y2...yn) be a transition of the GPDA

where q_1, q_2 \in Q, w \in\Sigma_{\epsilon}, x_1, x_2,\ldots,x_m\in\Gamma^{*}, m\geq0, y_1, y_2,\ldots,y_n\in\Gamma^{*}, n\geq 0.

Construct the following transitions for the PDA:

\delta^{'}(q1, w, x1) \longrightarrow (p1, \epsilon)
\delta^{'}(p1, \epsilon, x2) \longrightarrow (p2, \epsilon)
\vdots
\delta^{'}(pm-1, \epsilon, xm) \longrightarrow (pm, \epsilon)
\delta^{'}(pm, \epsilon, \epsilon ) \longrightarrow (pm+1, yn)
\delta^{'}(pm+1, \epsilon, \epsilon ) \longrightarrow (pm+2, yn-1)
\vdots
\delta^{'}(pm+n-1, \epsilon, \epsilon ) \longrightarrow (q2, y1)

همچنین ببینید[ویرایش]

ماشین پشته

گرامر مستقل از متن

ماشین‌های حالات متناهی

منابع[ویرایش]

[۲]

  1. Greibach, Sheila (October 1966). "The Unsolvability of the Recognition of Linear Context-Free Languages". Journal of the ACM 13 (4)
  2. کتاب نظریه زبان‌ها و ماشین‌ها از پیتر لینر

پیوند به بیرون[ویرایش]