سلام.

[tex]S\to 0A0|1B1[/tex]
[tex]A\to CAC|0[/tex]
[tex]B\to CBC|1[/tex]
[tex]C\to 0|1[/tex]

(۱۸ خرداد ۱۳۹۳ ۰۹:۴۹ ب.ظ)uniquegirl نوشته شده توسط:  سلام دوستان
یه سوال فوری برای یکی از دوستام می خواستم
ممنون میشم جواب بدین

یک گرامر مستقل از متن و آتاماتای پشته ای برای زبانی میخوام که اولا الفبای آن ۰ و ۱ بوده و حرف اول و وسط و آخر آن عین هم باشد
مثال: ۱۰۰۱۰۰۱
۰۱۰۱۰۰۰۱۱۱۱۰۰
۰۱۱۰۰۰۰

سلام
در مورد رشته های تک کاراکتری توضیح ندادی. اما من با این فرض که رشته هایی مثل "۰" و "۱" هم عضو زبان هستند پیش می رم
گرامر:
[tex]S\longrightarrow0A0\mid1B1\mid1\mid0[/tex]
[tex]A\longrightarrow0A0\mid1A1\mid0A1\mid1A0\mid0[/tex]
[tex]B\longrightarrow0B0\mid1B1\mid0B1\mid1B0\mid1[/tex]

اینم از NPDA:
state های ۱۱و۲۲و۴و۶ فاینال هستند
[tex]\delta(q_0,0,\: z)=\{(q_{00,1z})\}[/tex]
[tex]\delta(q_0,1,\: z)=\{(q_{11,1z})\}[/tex]
[tex]\delta(q_{11},\: 0,1)=\{(q_1,11)\}[/tex]
[tex]\delta(q_{11},\: 1,1)=\{(q_1,11)\}[/tex]
[tex]\delta(q_{22},\: 0,1)=\{(q_2,11)\}[/tex]
[tex]\delta(q_{22},\: 1,1)=\{(q_2,11)\}[/tex]
[tex]\delta(q_1,\: 0,1)=\{(q_1,11),(q_3,1)\}[/tex]
[tex]\delta(q_2,\: 1,1)=\{(q_2,11),(q_5,1)\}[/tex]
[tex]\delta(q_1,\: 1,1)=\{(q_1,11)\}[/tex]
[tex]\delta(q_2,\: 0,1)=\{(q_2,11)\}[/tex]
[tex]\delta(q_3,1,1)=\{(q_3,\lambda)\}[/tex]
[tex]\delta(q_3,0,1)=\{(q_4,\lambda)\}[/tex]
[tex]\delta(q_4,0,1)=\{(q_4,\lambda)\}[/tex]
[tex]\delta(q_4,1,1)=\{(q_3,\lambda)\}[/tex]
[tex]\delta(q_5,0,1)=\{(q_5,\lambda)\}[/tex]
[tex]\delta(q_5,1,1)=\{(q_6,\lambda)\}[/tex]
[tex]\delta(q_6,0,1)=\{(q_5,\lambda)\}[/tex]
[tex]\delta(q_6,1,1)=\{(q_6,\lambda)\}[/tex]