این نکته خودش جزو گزینه های چندتا از سوالات کنکوره.

چون میخواهیم قطعی باشه و خالی شدن پشته نشان پذیرش رشته است اگر به ازای مثلا ab پشته خالی شود نمیدانیم آیا رشته ما ab بوده و باید بپذیرد یا هنوز رشته تمام نشده مثلا abdc پس اگر بخواهیم قطعی باشه نباید هیچ رشته ای پیشوند رشته دیگر باشد.

این سوال به این صورت میتونه مطرح بشه:برای کدامیک از گزینه های زیر یک dpda وجود دارد که با خالی کردن پشته رشته را بپذیرد؟
حال باید دنبال گزینه ای بگردید که شامل رشته ای باشه که پیشوند یه رشته دیگه در همون زبان نباشه

واسه فهم بیشتر:
مثلا اگه ماشین رشته های ababab..... (هر تعدادی ab پشت سر هم) رو بپذیره پس ما باید بعد از هر a یه b پوش کنیم و بعد هر دو رو پاپ کنیم و پشته خالی میشه و رشته پذیرفته میشه حالا ما اگه رشته abab رو بهش بدیم وقتی ab اول رو پوش و پاپ کرده و هنوز خالیه نمیدونیم که هنوز باید منتظر بقیه ورودی‌ها باشیم یا اینکه چون پشته خالی شده همون ورودی رو بپذیریم و این نشانه غیر قطعی بودنه حالا چرا این مشکل پیش اومد چون ab که خودش عضوی از زبان این ماشین بود پیشوند abab بود.

:منم چندتا نکته میگم،اینارو بعضی هاش از کتاب لینزه بعضی هاشم برداشت خودمه در نتیجه اگه فک میکنین بعضی هاش غلطه بگین تا روش بحث کنیم
هر گرامر LL(K) ای قطعی هست،درنتیجه در گرامری که LL (K) نیست قطعی نیست و هر قطعی ای غیر مبهمه.
----------------------------------------------------------------------
هر زبان تک نمادی که منظم نیست،مستقل از متن هم نیست.
این نکته تو گزینه‌ها خیلی کاربرد داره:
مثلا زبون a^n (به شرطی که n اول باشه) مستقل از متن نیست،چون فقط یه نماد داره و گرامرش منظم نیست.
-----------------------------------------------------------------------
تعداد علائم هر pda در پشته حداکثر به تعداد طول رشته به علاوه یکه.(به علاوه یک به خاطر Z)
مثلا زبون a^n b^2n رو در نظر بگیرین،رشته a^10 b^20 متعلق به زبون هست و برای پذیرشش ۲۰ تا a میریزیم تو استک بعد به ازای ۲۰ تا b اونارو برمیداریم،بنابراین حداکثر ۲۰ تا خونه استفاده کردیم و این کمتر از طول رشتس.

هر گرامر LL(K) ای قطعی هست،درنتیجه در گرامری که LL (K) نیست قطعی نیست و هر قطعی ای غیر مبهمه.
یکم کمک از کامپایلر ،فرض کنید که LL(K) نباشه پس امکان داره SLR باشه ولی میتونه قطعی باشه و غیر مبهم نباشه
راستی این مبحث مگه برای قسمت کامپایلر نیست !!!!!!!!!!!!!!!

من هم یه چند تا نکته بگم که بدرد دوستان بخوره:
۱-اگر L یک زبان غیر تهی باشد. بطوریکه حداقل طول رشته پذیرفته شده بوسیله ان برابر با n باشد. انگاه هر dfa پذیرنده این زبان دارای طول n+1 خواهد بود.
تشریح نکته:
منظور اینکه فرض کنید a* حداقل طول رشته ای که می پذیره صفر ه ولی ماشینش ۱ حالت داره و اون هم حالت شروع حالت پذیرش هستش . بهمین ترتیب +^a

۲-اگر یک dfa با k حالت رشته w با طول بیش از k-1 را بپذیرد . انگاه زبان پذیرفته شده توسط ان نا متناهی خواهد بود .
تشریح نکته:

مثلا: زبان +^a که dfa اون دو وضعیت داره بنابراین k=2 هستش این dfa رشته بیش از ۱ (k-1) رو می پذیره پس زبان نا متناهی هستش

سلام دوستان
چه تاپیک خوبی!! واقعا جای این تاپیک خالی بود، ممنون
راجع به نکته اول من منظورتون رو
"زبان این ماشین شامل هیچ رشته ای نیست که پیشوند رشته دیگری باشد"
متوجه نشدم. اما مثالی که برای این نکته بکار بردید یعنی ababab..... رو میشه با dpda طراحی کرد.

[tex]\delta (q0,a,z)=q1,za[/tex]

[tex]\delta (q1,b,a)=q0,\lambda[/tex]

q0 هم حالت شروع و هم حالت فاینال هست. که با دریافت a اون رو در پشته پوش میکنه و به q1 میره.
در q1 هم با دریافت b از ورودی a از پشته پاپ میشه و به q0 برمیگرده.

(۱۰ خرداد ۱۳۹۰ ۰۸:۴۷ ق.ظ)behdad نوشته شده توسط:  سلام دوستان
چه تاپیک خوبی!! واقعا جای این تاپیک خالی بود، ممنون
راجع به نکته اول من منظورتون رو
"زبان این ماشین شامل هیچ رشته ای نیست که پیشوند رشته دیگری باشد"
متوجه نشدم. اما مثالی که برای این نکته بکار بردید یعنی ababab..... رو میشه با dpda طراحی کرد.

[tex]\delta (q0,a,z)=q1,za[/tex]

[tex]\delta (q1,b,a)=q0,\lambda[/tex]

q0 هم حالت شروع و هم حالت فاینال هست. که با دریافت a اون رو در پشته پوش میکنه و به q1 میره.
در q1 هم با دریافت b از ورودی a از پشته پاپ میشه و به q0 برمیگرده.

سلام دوست عزیز
این نکته رو اتفاقا امروز تو کتاب پارسه خوندم
فکر می کنم منظور اینه که مثلا اگه رشتمون باشه aaabbb پذیرش می شه ولی ababab پذیرش نمی شه
اگه اشنباه می گم اصلاح کنید.

یه نکته بسیار جالب تو کتاب نظریه پارسه هست که میگه:
یک آتاماتای دو پشته ای نا معین‌، هم قدرت با یک ماشین تورینگ است.

متاسفانه هیچ اثباتی براش تو کتاب پارسه ارایه نشده .