特定语言的上下文语法
Context grammar for specific language
我无法理解简单的问题。我必须指出以下语法
单词
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
有人可以检查这些练习并给我反馈吗?我做错了什么?
第一个会生成(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
的原因。
我无法理解简单的问题。我必须指出以下语法 单词
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
有人可以检查这些练习并给我反馈吗?我做错了什么?
第一个会生成(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
的原因。