给定语言，定义其CFG

| 给定

L1 = {w belongs to {a,b}* | has as many a as b}

定义CFG G，使L（G）= L1 我认为这些作品应该是正确的答案

1) S → aSa

2) S → bSb

3) S → ε

我的理由是： L1包含诸如{ab，aabb，aaabbb，... etc}的字符串现在我有一个疑问：如果我将上述产品应用到简而言之： S → aSa 我应用1）所以得到S → aSa → aaSaa，然后选择2）我得到S → aSa → aaSaa → aabSbaa，然后使用空字符串得到最终的字符串string5ѭ 现在，也许我错了，但是在字符串ѭ6中，a的数量不等于b的数量任何帮助将不胜感激约阿希姆

已邀请:

3 个回复

昧伎

这是标准的课堂练习，尚无正确答案。

1) S -> aSb
2) S -> bSa
3) S -> SS
4) S -> ε

任意数量的a和b以任意顺序排列，包括空字符串。有很多在线课堂笔记以及答案和证明。例子：这里，这里，这里和这里展示一些。

款去芳尾脊

假设L1实际上是{a^nb^n | n ≥ 0}，那么您提供的语法就不能（如您所证明的那样）精确地产生L1。为了满足松散表达“单词左侧的9个数字必须等于单词右侧的10个数字”的要求，您的目标是找到一种语法在每部作品完成之后执行该要求。对此进行思考的另一种方式是：不允许您在语法中使用不能产生相等数量的a和b的产生式。编辑：由于这不是家庭作业，我将继续给出答案：

V = {A}, Σ = {a, b}, S = A, and R the set of rules:

(1) A -> aAbA | bAaA
(2) A -> ε

俺呵誓放胳

抱歉，我错了，但迈克尔·富卡拉基斯（Michael Foukarakis）的解决方案不起作用基本上，这两个规则不提供具有相同数字a和b的字符串。

(1) A -> aAb

(2) A -> ε

取A-> aAb，然后应用1）规则，您有A -> aAb ->aaAb，然后??? 如果您应用2），您最终将获得A -> aAb ->aaAb ->aab 我认为正确的答案是：

1)S->aSbS

2)S->bSaS

3) S->ε

即使我得到像strings18ѭ或aababb这样的字符串实际上，它们都满足初始要求，即：

the string must contain the same number of a and b.

（元素的排列方式都没有关系。）当然欢迎并鼓励提出评论。

要回复问题请先登录或注册

给定语言，定义其CFG

3 个回复

发起人

compiler_construction

grammar

问题状态

给定语言，定义其CFG

与内容相关的链接

3 个回复

发起人

compiler_construction

grammar

问题状态