字符串中 A 数量的常规语言

Question

L={w|w€{a,b}，a能被2整除的数}是语言。有人可以帮我解决这个问题的常规语法吗？

Answer 1

语言是a和b的所有字符串的集合，a是偶数个。这是一种常规语言，目标是为其生成常规语法。

除非您需要的常规语法很简单，否则我建议始终先写下有限自动机，然后再将其转换为语法。将有限自动机转换为文法非常容易，使用有限自动机解决这个问题也很容易。我们将有两种状态：一种对应于看到 a 的偶数，另一种对应于奇数。对应于看到偶数个 a 的状态将是接受，而看到 b 不会导致我们改变状态。因此，DFA 是：

       b         b
      /-\       /-\
      | V       | V
----->(q0)--a-->(q1)
        ^         |
        |    a    |
        \---------/

通过将转换记为产生式，使用状态作为非终结符号，并为接受状态包括一个空产生式，可以形成一个常规语法：

(q0) -> b(q0) | a(q1) | e
(q1) -> b(q1) | a(q0)

为了完整起见，你可以运行语法或自动机上的一些其他算法并得到一个正则表达式，可能是这样的：b*(ab*ab*)*（只是写下来，不确定是否对不对，留作练习）。

字符串中 A 数量的常规语言

Regular language for number of A's in the string

computation-theory