I'm trying to write a CFG over the alphabet Σ = {a,b} for all words starting and ending with the same number of a's, with at least one b in the middle.
我正在尝试在字母表Σ= {a,b}上写一个CFG,所有单词以相同数量的a开头和结尾,中间至少有一个b。
Now I understand the basic concept of CFG, variables, production rules, etc. Unfortunately I've run out of ideas for writing the aforementioned CFG. All I've got so far is
现在我理解了CFG的基本概念,变量,生产规则等。不幸的是,我已经没有用于编写上述CFG的想法了。到目前为止,我所有的一切都是
S → aYXYa
X → XbX | b | λ
Y → ???
I think that the production rules S and X will give me a string with two **a**s on both sides with as many **b**s in the middle as I'd like. However, I'm not sure how I can also put as many **a**s on both sides of the **b**s while making sure there are exactly the same number of **a**s on each side.
我认为生产规则S和X会给我一个字符串,两边都有两个** a **,中间有尽可能多的** b ** s。但是,我不确定如何在** b **的两侧放置尽可能多的** a **同时确保每侧的** a **数完全相同。
Any suggestions, solutions would be much appreciated. Thanks.
任何建议,解决方案将不胜感激。谢谢。
3 个解决方案
#1
S → aSa | B B → b | bB
This should be the CFG you're looking for. Whenever you've dealing with the same thing on the beginning and end, remember that you can't guarantee that the same var will be filled the same way. As such, you have to make those explicit.
这应该是您正在寻找的CFG。每当你在开头和结尾处理同样的事情时,请记住你不能保证同样的var将以相同的方式填充。因此,你必须明确这些。
#2
As an ex-professor who's taught this class before, I'm not going to give you the answer. I will, however, give you a hint:
作为以前教过这门课程的前教授,我不打算给你答案。但是,我会给你一个提示:
You have the right idea to break it into two parts, the a's and the rest. However, you're not doing either one of them right.
你有正确的想法把它分成两部分,a和其他部分。但是,你没有正确地做其中任何一个。
First try writing: anban then branch off from there.
首先尝试写作:anban然后从那里分支。
Hope that helps.
希望有所帮助。
#3
It's been a while since my CS undergrad days but this looks reasonable:
我的CS大学时代已经有一段时间,但这看起来很合理:
S -> aSa | bX
S - > aSa | BX
X -> bX | E
X - > bX | Ë
Basically, you start with S and add as many pairs of a's as you want and then switch to X and add as many b's as you want.
基本上,你从S开始并根据需要添加任意数量的a,然后切换到X并添加任意数量的b。
#1
S → aSa | B B → b | bB
This should be the CFG you're looking for. Whenever you've dealing with the same thing on the beginning and end, remember that you can't guarantee that the same var will be filled the same way. As such, you have to make those explicit.
这应该是您正在寻找的CFG。每当你在开头和结尾处理同样的事情时,请记住你不能保证同样的var将以相同的方式填充。因此,你必须明确这些。
#2
As an ex-professor who's taught this class before, I'm not going to give you the answer. I will, however, give you a hint:
作为以前教过这门课程的前教授,我不打算给你答案。但是,我会给你一个提示:
You have the right idea to break it into two parts, the a's and the rest. However, you're not doing either one of them right.
你有正确的想法把它分成两部分,a和其他部分。但是,你没有正确地做其中任何一个。
First try writing: anban then branch off from there.
首先尝试写作:anban然后从那里分支。
Hope that helps.
希望有所帮助。
#3
It's been a while since my CS undergrad days but this looks reasonable:
我的CS大学时代已经有一段时间,但这看起来很合理:
S -> aSa | bX
S - > aSa | BX
X -> bX | E
X - > bX | Ë
Basically, you start with S and add as many pairs of a's as you want and then switch to X and add as many b's as you want.
基本上,你从S开始并根据需要添加任意数量的a,然后切换到X并添加任意数量的b。