computer-science - 给出正则语言 L

Question

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

我会做这样的事情：

s---> A | 空字符串

A---> aB| 空字符串

b--->抗体

但是我们如何计算语法中的数字呢？意思是它如何知道何时有超过 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）次

a^(n-1) X b^(n-1) -> a^nb^n （使用第三条规则，X -> ab）