特定语言的上下文语法

Question

我无法理解简单的问题。我必须指出以下内容的语法的话

a） (ab)^2i c, i>=1

对于 i=1 ababc对于 i=2 ababababc

   S -> abA
   A -> ab | abc | c

b） a^(m-1) b^(m+1) a^n b^n, m>=1 n>=1

对于 i=1 bbab对于 i=2 abbbaabb

   S -> AbbAaAb
   A -> ba | ab | a

有人可以检查这些练习并给我反馈吗？我做错了什么？

Answer 1

第一个会生成(ab)^i，你只需要单词中偶数个ab对，所以你必须将其定义为

S -> ababA
A -> ababA | c

在

第二条规则中，您还必须在右侧使用A，因为您的规则将创建一个最大长度为 5 的单词。

第二个

S -> AbbB
A -> aAb | epsilon (empty string)
B -> aAb

对于单词的第一部分，您始终需要在右侧bb。你从中生成剩下的a^n b^n。

对于单词的第二部分，我们重用非终端A，但我们确保单词部分中至少有一个ab - 这就是B的原因。