我知道下面的问题的解决方案，使用4个变量，包括开始变量，但不少于4。是否有一个解决方案使用少于4个变量？
找到语言L = {a^n * B^m的正则文法：n，m>=0，n + m是奇数}，使用包括S在内的少于4个变量。
xa9qqrwz1#
你已经在注解中提供了一个正确的建议，但是你可以删除一个非终结符（变量），这样它就变成了：𝑆 → 𝑎𝑎𝑆𝑆 → 𝑎𝑇𝑆 → 𝑏𝑇𝑇 → 𝑏𝑏𝑇𝑇 → ε也就是说，当且仅当一个输入由一个偶数的组成，后跟一个或一个，后跟一个偶数的时，它才被接受。𝑏𝑎注意：我使用了更常见的做法，使用ε来表示空字符串。在更紧凑的正则表达式语法中，这将是：
(aa)*[ab](bb)*
1条答案
按热度按时间xa9qqrwz1#
你已经在注解中提供了一个正确的建议，但是你可以删除一个非终结符（变量），这样它就变成了：
𝑆 → 𝑎𝑎𝑆
𝑆 → 𝑎𝑇
𝑆 → 𝑏𝑇
𝑇 → 𝑏𝑏𝑇
𝑇 → ε
也就是说，当且仅当一个输入由一个偶数的组成，后跟一个或一个，后跟一个偶数的时，它才被接受。𝑏𝑎
注意：我使用了更常见的做法，使用ε来表示空字符串。
在更紧凑的正则表达式语法中，这将是：