كيف يمكنني بناء القواعد التي تولد هذه اللغة؟

Question

وأنا أدرس لالآلي وقواعد النحو اختبار محدود وأنا عالقة مع هذا السؤال:

Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}

وأعتقد أن بلدي إنتاج تذهب على طول هذه الخطوط:

    S->aA | aB
    B->bB | bC
    C->cC | c Here's where I have doubts

وكيف يمكن إنتاج بلدي لC يتذكر أعداد م ون؟ انا التخمين هذا يجب أن يكون بدلا النحوي الخالية من السياق، إذا كان الأمر كذلك، كيف يجب أن يكون؟

Answer 1

ويبدو أنه ينبغي أن يكون مثل:

A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon

وتحتاج إلى قوة C'c لتحسب أثناء عملية البناء. من اجل اظهار انها خالية من السياق، أود أن تنظر إلى استخدام مضخة يما .

Answer 2

نعم، هذا لا يبدو وكأنه الواجبات المنزلية، ولكن تلميح:

وفي كل مرة كنت تطابق "أ"، يجب أن تتطابق مع 'ج'. نفس لمطابقة 'ب'.

Answer 3

S -> X
X -> aXc | Y
Y -> bYc | e

وحيث e == epsilon وX لا لزوم لها ولكن وأضاف لوضوح

Answer 4

S-> ASC | A A-> BAC | λ

وهذا يعني أي وقت مضى عندما تحصل على ما لا يقل عن لديك 1 ج أو إذا كنت تحصل على وباء يجب أن يكون لديك 2 ج. وآمل أنها كانت مفيدة

Answer 5

والرجال حسنا، هذه هي الطريقة سأفعل ذلك:

P={S::=X|epsilon,
   X::=aXc|M|epsilon,
   M::=bMc|epsilon}