我如何找出这种无上下文语法生成的语言？ [英] How do I figure out the language generated by this context-free grammar?

问题描述

我正在处理以下语法：

G = ( {S, A}, {a, b}, P, S ) 
P = { S -> aAb, S -> bAa, 
A -> aSa, 
A -> S, 
A -> epsilon}

我需要找出L（G）。
问题是，我发现语法中的单词具有以下形式：
以a开头并以b结束，或者以b开头并以a结束，并且在这些字母之间，组合：ab，ba，aaba，abaa；然后通过在中间的a和b之间插入这4个组合中的一个来形成下一个单词。但是，我该如何正式表达呢？
我的意思是，据我所知，L（A）= a ^ n S a ^ n，如果w属于L（G），则w反转也属于L（G）。
我尝试将其表示为正则表达式，但失败了……有人可以帮忙吗？

I need to find out L(G). The thing is, I figured out that the words in the grammar are of the form: starts with a and ends with b, or starts with b and ends with a, and between these letters one of the combinations : ab, ba, aaba, abaa; then the next word is formed by inserting one of these 4 combinations between the a and b in the middle..but how can I express this formally? I mean, as far as I could tell, L(A) = a^n S a^n and if w belongs to L(G), then w reversed also belongs to L(G). I tried to express it as a regular expression but failed...could anyone please help?

谢谢。

推荐答案

您看到L不是规则的，以证明您可以使用抽取引理或 Myhill-Nerode定理，因此不能讨论正则表达式

You see that L is not regular, to prove you can use Pumping lemma or Myhill–Nerode theorem, so regular expression can't be discussed

您会注意到，由于L仅由{a，b}组成，因此可以使用它的幂
我们看到语言为aAb或bAa或aAa形式，但aAa不能位于单词的开头。

You can notice, that since L consists just of {a,b} you can use it's power We see that language is in the form of aAb or bAa or aAa with exception that aAa can't be located at begin-end of the word

所以让我们使用它，我们唯一想念的是bAb
A的组合几乎可以生成所有内容（单词| w | = 2k，和| w |> = 2），但是b的位置与b的位置相反的单词

So let's use this, the only thing we miss is the combination of bAb A can generate almost everything (words |w| = 2k, and |w|>=2) but words where position of b matches position of b from the reverse

正式

很抱歉，我的tex技能和形式表达方式

Sorry for my tex skills and my formal expression

有点错误，因为我没有太多时间考虑这个问题，但是可以通过某种方式继续下去，这是家庭作业，所以可以考虑一下！ ：）

there must be some error, because I didn't have so much time to think about this, but it can be some way how to continue, it's homework so it's fine, think about it! :)

这篇关于我如何找出这种无上下文语法生成的语言？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！