ضخ lemma ل cfls

Question

سؤالي هو:

دع l = {x في {a، b} * | X لديه عدد متساو من A و B's}

أعلم أن هذه هي لغة خالية من السياق لأنني أستطيع إنشاء قواعد قوية لذلك (E IS EPSILON):

S -> aX | bY | e

X -> bS | aXX

Y -> aS | bYY

يمكنك أيضا إثبات أنه سياق مجاني باستخدام حقيقة أن لغة حرة للسياق تتقاطع بلغة منتظمة خالية من السياق.

نظرا لأنها لغة خالية من السياق، وفقا ل Lemma ضخ ل CFL's، يجب أن تكون أي سلسلة أطول من طول الضخ P قادرة على ضخها. ومع ذلك، إذا اخترت السلسلة s = a ^ pb ^ pa ^ pb ^ p، لا يمكن ضخ هذه السلسلة، وبالتالي لا ينبغي أن تكون اللغة حرة.

هل أنا على خطأ؟

Answer 1

تأكد من أن السلسلة يمكن ضخها. يترك u = a^p b^(p-1), v = b, x = e, y = a, z=a^(p-1) b^p. وبعد حاليا uvxyz = s ولأي أنا u v^i x y^i z لديه كمية متساو من AS و BS.

Answer 2

اسمحوا لك = a ^ p، v = b ^ (p-1)، x = ba، y = a ^ (p-1)، z = b ^ p، بحيث سلسلة s = uvxyz.

ثم أي سلسلة من النموذج الأشعة فوق البنفسجية ^ ixy ^ iz باللغة، وبالتالي فإن شروط ضخ CFL Lemma راضية.

طول الضخ ليس "p" على سبيل المثال ... ربما هذا هو المكان الذي تشعر به الخلط؟

يحرر: يشير SEPP2K بشكل صحيح إلى أن خياري من Vxy ينتهك الحالة التي | Vxy | <= p، طول الضخ للغة. الحل الخاص به v = b، x = e، y = a هو الصحيح. لهذه اللغة، يجب أن تظهر أي سلسلة من الطول 2 أو أكبر - "AB" أو "BA" في مكان ما، لذلك VY = AB أو VY = BA ستعمل دائما.