设计上下文无关文法(由a和b组成)使得其中所有字符串都并非由某个字符串重复两次形成的
时间: 2023-05-31 17:01:49 浏览: 145
第二章上下文无关文法
5星 · 资源好评率100%
S -> aSb | bSa | aB | bB
B -> a | b | aBb | bBa | aBbA | bBaA
A -> aA | bA | ε
解释:
S是起始符号,可以生成两种情况:以a开头、以b开头。分别对应aSb和bSa。此外,也可以直接生成一个B,对应a和b。这样可以保证至少有一个a和一个b。
B是一个辅助符号,可以生成单个a或b,也可以生成一个a和一个b,但是它们的顺序是任意的,对应aBb和bBa。此外,为了避免形如aa、bb、abab、baba等重复两次的字符串,我们需要在B的基础上再加上一些规则。
为了避免形如aa、bb这样的字符串,我们在B的基础上加上一个A。A可以生成任意个a或b,但是它们的顺序是任意的,对应aA、bA和ε(空串)。
为了避免形如abab、baba这样的字符串,我们在B的基础上再加上两个规则:aBbA和bBaA。这两个规则可以生成类似于ab、baab、babab、abbba、babbba这样的字符串,但是它们的长度至少为5,因此不会形成由某个字符串重复两次形成的字符串。
综上所述,这个文法可以生成所有由a和b组成的字符串,但是这些字符串都不是由某个字符串重复两次形成的。
阅读全文