CFG for language

问题描述 投票:0回答:1

我正在尝试创建一个生成以下语言的cfg:

“FOO

该语言是否与上下文无关,可以由cfg生成?如果是,如何创建生成该语言的语法?

我在为cfl创建cfg方面经验不多。如果有任何帮助或解决方案,我将很高兴

context-free-grammar context-free-language
1个回答
1
投票

[开始时,您知道如何为{a^n d^t | n = t}语言创建CFG吗?这将是您的起点。

S -> aSd | epsilon

[从这里开始,需要扩展当a多于dd多于a时发生的情况。目标始终是确保左侧消耗的每个ab的右侧消耗的是cd

S -> aSd | aAc | bDd | epsilon

Aa多于d s的情况,D是另一种情况。在每种情况下,您都需要为每个右字符消耗一个左字符。

还有另外一种情况,即nt之一或全部为0。我会留给您确定如何处理。

然后,您将不得不处理一方角色的不足。例如,如果您处于状态A,则希望将ac匹配,直到a用尽并变成b。类似,

A -> aAc | bCc

我将剩下的留给您找出。

© www.soinside.com 2019 - 2024. All rights reserved.