写出下列语言的正则表达式在字母表

Question

写出过字母表Σ=以下语言正则表达式{0,1}：

1. 的所有字符串的语言不与11
结束
2. 不包含子字符串01的所有字符串的语言也 为每种上述语言绘制有限自动机。

Answer 1

为第一个正则表达式是e + 0 + 1 + S* (00 + 01 + 10)其中e是空字符串，S是字母表，*是克林闭合，+是联合。这是可行的，因为语言可以分成长度小于2的字符串（e + 0 + 1）和长度至少为2的字符串，但不以11（此结尾为00,01和10）结尾。

第二语言的正则表达式是1*0*。请注意，我们必须在所有0 s的左侧放置任意1 s以避免子字符串01，但我们可以根据需要选择多个。

甲DFA为第一个看起来像

q e q' 
q0 0 q0 
q0 1 q1 
q1 0 q0 
q1 1 q2 
q2 0 q0 
q2 1 q2 

状态Q0为初始，Q0和Q1被接受。在状态q0中，你刚刚开始或最后一次看到一个零;你的最后一个符号不是1.在状态q1中，你的最后一个符号是1，但是倒数第二个符号不是。在q2状态中，你已经看到了连续两个1。

甲DFA用于第二看起来像：

q e q' 
q0 0 q1 
q0 1 q0 
q1 0 q1 
q1 1 q2 
q2 0 q2 
q2 1 q2 

Q0是初始状态，和Q0和Q1被接受。 q0读取所有0，q1读取所有1，并且如果在我们看到1后看到0，则发生q2。