崇州市建设局网站什么是搜索引擎

为字母表Σ={a,b}Σ=\{a,b\}Σ={a,b}上的下列每个语言设计一个文法

(a) 每个a后面至少有一个b的所有串

• 首先，每个a后面至少有一个b的正规式怎么写呢？
• 每个a都需要至少跟一个b，那么可以用ab表示
• 那么这个串的前面可以有若干个a或者若干个b或者他们的任意组合，那么保证有了ab以后，在它的前面或者后面都添加若干个a或b
• 则正规式为：(ab|b)*，这样得到了上述语言的正规式
• 那么文法怎么写呢？直观的看，该正规式可以推到ab之后跟任意ab或者b的串，可以推到空串，也可以推到b开头后续跟任意ab或b的串
• 则用一个文法符号S表示，可以推到如下文法
  • $$\begin{gathered} S\to abS \\ S\to bS \\ S\to ϵ \end{gathered}$$
  • 这个文法就满足
    • 可以推到ab开头之后跟任意ab或者b的串
    • 可以推到b开头后续跟任意ab或b的串
    • 可以推到空串

(b)a和b个数相等的所有串

• $$\begin{gathered} S\to aB|bA|ϵ \\ A\to aS|bAA \\ B\to bS|aBB \end{gathered}$$
• 上述文法怎么得到的呢？
• 如下:
  (c）a和b个数不相等的所有串
•