给出一种规则语言

Question

给出L= {a^n b^n: n<=100}的正则语法

我会这样做:

s-> A |空字符串

A-> aB|空字符串

b——> Ab

但是我们如何计算语法中的数字?意思是它怎么知道什么时候有超过100个a。我甚至不确定我的方式是否有意义。

Answer 1

由于该语言的成员显然是有限的，因此您可以将它们作为所有可能情况的列表:

S -> ab | aabb | aaabbb | ... | a^100b^100

Answer 2

设S为起始符号:

1) S -> aXb
2) X -> aXb 
3) X -> ab

我可以证明这是有效的:
1) S -> aXb
2) aXb -> a aXb b
…(n-3)次

b

^ (n - 1) X ^ (n - 1) -> ^ n b ^ n(使用第三个规则,X -> ab)