如何构造语言La={ww^r | w∈{0,1}^*且w以1结尾}的文法？求方案点评

原文法的问题 #

你给出的文法S -> 0S0|1S1|0|1|ε是不正确的，原因如下：

• 生成的串不符合La的长度要求：La中的串都是ww^r，其中w以1结尾（w至少长度为1），因此每个串的长度都是偶数（2×|w|），但原文法能生成单个0、1（奇数长度）和空串ε，这些都不属于La。
• 生成的串不符合w的结尾要求：原文法可以生成以0开头和结尾的回文（比如00），但La中的串必须是ww^r且w以1结尾，因此串的首尾必然是1（w结尾是1，w^r开头是1），原文法生成的00这类串不在La中。

修改后的正确文法 #

针对La的定义，正确的上下文无关文法应该保证生成的串是偶数长度、首尾为1且对称的回文，对应ww^r（w以1结尾）的结构。可以构造如下文法：

S -> 0S0 | 1S1 | 11

文法解释 #

• 基础产生式11对应w=1的情况，生成串11（即11^r）。
• 递归产生式0S0和1S1用于在已符合要求的串两侧添加对称的0或1：比如基于11，用0S0可生成0110（对应w=01），用1S1可生成1111（对应w=11）；再基于0110用1S1可生成101101（对应w=101），以此类推，所有生成的串都满足ww^r且w以1结尾的条件。

内容的提问来源于stack exchange，提问作者sourga bah