هو s-قواعد قوية بما يكفي لتوليد كل شيء ممكن ديلويت فاينانس ليمتد?

Question

في s-النحوي جميع المنتجات هي في شكل من A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

"...و أي زوج (أ ، أ) يحدث مرة واحدة على الأكثر في بي" [P.لينز, 6th ed., p.144]

s-قواعد اللغة لا لبس فيه و أعتقد (لست متأكدا) يمكننا وصف كل لبس فيها-CFL بواسطة s-قواعد اللغة.أريد أن أعرف يمكن أن s-قواعد اللغة لوصف كل شيء ممكن ديلويت فاينانس ليمتد أو لا ؟ ووفقا لهذه الجملة ، أعتقد أننا لا يمكن أن تفعل ذلك ولكن أنا لست متأكد من ذلك:

للأسف, ليس كل ميزات نموذجية لغة البرمجة يمكن التعبير عنها بواسطة s-قواعد اللغة. [P.لينز, 6th ed., p.152]

ولكن جميع اللغات التي وصفها s-القواعد القطعية.

أقول هذا لأننا يمكن أن تقدم 2-الدولة DPDA لأي بسيطة-قواعد اللغة مع هذا التعريف:

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label 
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

إذا كان هناك أي ديلويت فاينانس ليمتد أننا لا يمكن أن توفر s-النحوي ، تبين لي أن يرجى تصحيح لي إذا كنت مخطئا.

شكرا

Answer 1

فعلا سبيل المثال من اللغة لا تقبل أن تكون بسيطة جدا ، بسبب خطأ فني.اللغة $a^*$ لا إنشاؤها بواسطة s-قواعد اللغة.

في الواقع, s-قواعد اللغة لا يمكن أن تولد $\varepsilon$.من أجل إزالة $S$ من المكدس علينا أن تطبيق واحد على الأقل الإنتاج ، أي إنتاج تنتج محطة الرمز.

ولكن حتى لو كنا نرى في ذلك تفصيل لا يمكننا توليد سلسلتين واحدة منها هي البادئة آخر.إذا نحن يمكن أن تولد سلسلة $\ألفا$ ثم قبلت لأن كل veriables وقد تم إعادة كتابة (المكدس يحتوي فقط على الجديد $z'$) ، ثم كيف يمكننا توليد أطول سلسلة $\alpha\بيتا$?يجب أن تتبع نفس الحساب في البداية.

هذا هو الحال لأن PDA تنتج في الواقع المساعد الشخصي الرقمي مع المجموعة الفارغة القبول:عندما كومة فارغة (أو في الواقع فقط $z'$) يجب علينا أن نقبل.ومن المعروف أن deterministice المساعد الرقمي الشخصي مع المجموعة الفارغة القبول يمكن أن تولد فقط البادئة خالية من اللغات.Addingan نهاية سلسلة علامة عادة العلاج.

في الوقت الحقيقي الملكية (قراءة رمز كل خطوة) هو أكبر مشكلة.النظر في اللغة $\{ a^أنا ب^j c^أنا \منتصف ط ، ي \قه 1\} \كأس \{ a^أنا ب^j d^ي \منتصف ط ، ي \قه 1\}$.فإنه يمكن أن يكون مقبولا من قبل DPDA.دفع $a$'s, دفع $b$'s.ثم عند قراءة $c$ نحن البوب $b$'s ومقارنة $a$'s ، $c$'s.وإلا عند قراءة $d$ قارنا $d$'ق مع $b$'s باستخدام المكدس.وبالتالي تحتاج ظهرت من كومة الرموز دون قراءة المدخلات.في الوقت الحقيقي PDA لا تستطيع أن تفعل ذلك (ولا s-النحوي).المصدر أعلم هذا يشير إلى Autebert, Berstel ، بواسون:السياق خالية من اللغات Pushdown التلقائية في الكتيب من اللغات الرسمية.

بالطبع PDA فقط دولة واحدة.أنا لا يجب أن تحقق:ويبدو ذلك أيضا في دولة واحدة تقييد يقلل من اللغات المقبولة.