كيف يمكنني بناء القواعد التي تولد هذه اللغة؟
-
06-07-2019 - |
سؤال
وأنا أدرس لالآلي وقواعد النحو اختبار محدود وأنا عالقة مع هذا السؤال:
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 يتذكر أعداد م ون؟ انا التخمين هذا يجب أن يكون بدلا النحوي الخالية من السياق، إذا كان الأمر كذلك، كيف يجب أن يكون؟
المحلول
ويبدو أنه ينبغي أن يكون مثل:
A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon
وتحتاج إلى قوة C'c لتحسب أثناء عملية البناء. من اجل اظهار انها خالية من السياق، أود أن تنظر إلى استخدام مضخة يما .
نصائح أخرى
نعم، هذا لا يبدو وكأنه الواجبات المنزلية، ولكن تلميح:
وفي كل مرة كنت تطابق "أ"، يجب أن تتطابق مع 'ج'. نفس لمطابقة 'ب'.
S -> X
X -> aXc | Y
Y -> bYc | e
وحيث e == epsilon
وX
لا لزوم لها ولكن
وأضاف لوضوح
S-> ASC | A A-> BAC | λ
وهذا يعني أي وقت مضى عندما تحصل على ما لا يقل عن لديك 1 ج أو إذا كنت تحصل على وباء يجب أن يكون لديك 2 ج. وآمل أنها كانت مفيدة
والرجال حسنا، هذه هي الطريقة سأفعل ذلك:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}