寫出下列語言的正則表達式在字母表

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。