我正在尝试创建一个生成以下语言的cfg:
该语言是否与上下文无关,可以由cfg生成?如果是,如何创建生成该语言的语法?
我在为cfl创建cfg方面经验不多。如果有任何帮助或解决方案,我将很高兴
[开始时,您知道如何为{a^n d^t | n = t}
语言创建CFG吗?这将是您的起点。
S -> aSd | epsilon
[从这里开始,需要扩展当a
多于d
或d
多于a
时发生的情况。目标始终是确保左侧消耗的每个a
或b
的右侧消耗的是c
或d
。
S -> aSd | aAc | bDd | epsilon
A
是a
多于d
s的情况,D
是另一种情况。在每种情况下,您都需要为每个右字符消耗一个左字符。
还有另外一种情况,即n
和t
之一或全部为0
。我会留给您确定如何处理。
然后,您将不得不处理一方角色的不足。例如,如果您处于状态A
,则希望将a
与c
匹配,直到a
用尽并变成b
。类似,
A -> aAc | bCc
我将剩下的留给您找出。