كيف يمكنني إرسال بلدي خالية من السياق النحوي؟ [مغلق]

Question

وأنا أحاول أن أكتب CFG على Σ = {a,b} الأبجدية لجميع الكلمات التي تبدأ وتنتهي مع نفس العدد من لa، مع b واحدة على الأقل في الوسط.

والآن أنا أفهم المفهوم الأساسي للCFG، والمتغيرات، وقواعد الإنتاج، وما إلى ذلك لسوء الحظ لقد نفد من الأفكار لكتابة CFG المذكور. كل ما عندي حتى الآن هو

S → aYXYa
X → XbX | b | λ
Y → ???

أنا <م> التفكير أن S قواعد الإنتاج وX سوف تعطيني سلسلة مع اثنين ** a ** الصورة على كلا الجانبين مع العديد من ** ** b الصورة في الوسط كما أنا ترغب. ومع ذلك، وأنا لست متأكدا كيف يمكن أيضا وضع العديد من ** ** a الصورة على كلا الجانبين من ** ** b الصورة في حين التأكد من عدم وبالضبط نفس العدد من ** ** a الصورة على كل جانب .

وأي اقتراحات والحلول سيكون موضع تقدير كبير. شكرا.

Answer 1

S → aSa | B
B → b | bB

وهذا يجب أن يكون CFG كنت تبحث عنه. كلما قمت التعامل مع نفس الشيء في بداية ونهاية، وتذكر أنك لا تستطيع أن تضمن أن نفس فار سيتم ملء بنفس الطريقة. على هذا النحو، لديك لجعل تلك صريحة.

Answer 2

وباعتبارها السابق الأستاذ الذي هو علم هذه الفئة من قبل، أنا لا أريد أن أعطيك الجواب. وأنا، ومع ذلك، تعطيك تلميح:

لديك فكرة الحق لتقسيمه إلى قسمين، ووبقية. ومع ذلك، كنت لا تفعل أي واحد منهم الحق.

والمحاولة الأولى كتابة: أ <سوب> ن في با <سوب> ن ثم تتفرع من هناك

وعلى أمل أن يساعد.

Answer 3

ولقد كانت فترة من الوقت منذ أيامي الجامعي CS ولكن هذا يبدو معقولا:

وS -> ASA | BX

وX -> BX | E

وفي الأساس، عليك أن تبدأ مع S وإضافة العديد من الأزواج من لما تريد ومن ثم التبديل إلى X وإضافة العديد من بز كما تريد.