代码之家 › 专栏 › 技术社区 › Johnrad

上下文无关语法问题

language-theory context-free-grammar

2

Johnrad · 技术社区 · 15 年前

首先,这是一个家庭作业问题。我有一个主意,但我仍然不能得到正确的答案。我不是在问答案,我只是在寻求帮助来回答这个问题。

a(iterated i times)db(iterated j times),  for i and j>=0,  and j = 2 * i.

所以基本上在2之间有两倍的a和b和a和d。例如:

d,  adbb,  aadbbbb,  â¦â¦

这是关于我所拥有的,我没有太多。。。我理解这些CFG的概念,我只是不确定这个问题的逻辑。我不确定我是否走对了方向。。。

S -> AdB
A -> EMPTY
A -> aAB
B -> DD

谢谢。

2 回复 | 直到 15 年前

1

Benn 15 年前

我想我首先会说你只需要两个语句就可以解决这个问题。我宁愿看你的一些作品(即使方向不对!)不过,如果我再给你。

编辑

谢谢你把你的东西贴出来。以下是一些思维练习,希望能让你朝着正确的方向前进:

^n个乙 ^n个对于n>0(ab、aabb、aaabbb…)

写一个表达 ^n个分贝 ^n个对于n>0(adb、aadbb、aaadbbb…)

当你得到最后一个,你会看到一些琐碎的附加到你的语法。

2

1

Chris Dodd 15 年前

每当你有一种语言,你可以这样列出,在下面的字符串的子字符串中的每个字符串,写一个简单的递归语法是相当简单的。您需要一个规则来生成第一个(最短)字符串,以及一个规则来生成前一个字符串中的每个较长字符串。

推荐文章

Max Koretskyi · 该语法是否通过右递归定义右结合性

8 年前

esseldm · 使用带有多个规则的pyparsing Forward()查找回文序列

10 年前

David Yi · NLTK、Python中的FCFG错误。语法问题

11 年前

Zhao · 困惑于将模棱两可的语法转换为明确的语法

11 年前

Kvass · 这两条上下文无关的语法规则是一样的吗?

12 年前

Jason Kleban · 语法规范解决移位/减少冲突

13 年前