根據使用者給定的語言構建正則表示式。

正則表示式是一種用於描述語言並被有限自動機接受的語言。正則表示式是表示任何語言的最有效方法。設 Σ 為表示輸入集的字母表。

Σ 上的正則表示式可以定義如下：

• Φ 是一個正則表示式，表示空集。
• ε 是一個正則表示式，表示集合 { ε}，稱為空字串。
• 對於 Σ 中的每個 ‘a’，‘a’ 是一個正則表示式，表示集合 {a}。
• 如果 r 和 s 是表示語言的正則表示式。
  • 分別為 L1 和 L2，則：
  • r+s 等價於 L1 U L2（並集）
  • rs 等價於 L1L2（連線）
  • r* 等價於 L1*（閉包）

r* 被稱為 Kleen 閉包或閉包，表示 r 出現無限次。

問題 1

編寫接受集合 l: = {a} 中所有 a 的組合的語言的正則表示式。

解答

所有 a 的組合意味著 a 可以出現零次、一次、兩次等等。如果 a 出現零次，則表示空字串。也就是說，我們期望集合 {E, a, aa, aaa, ....}。因此，我們為其給出如下正則表示式：

R = a*

即 a 的 Kleen 閉包。

問題 2

編寫接受集合 l: = {a} 中所有 a 的組合（除了空字串）的語言的正則表示式。

解答

需要為語言 L = {a, aa,aaa, ....} 構建正則表示式。

此集合表示沒有空字串。因此，我們可以將正則表示式表示為：

R = a+

問題 3

編寫集合 l: = {0, 1} 上的語言 L 的正則表示式，使得所有字串都不包含子字串 01。

解答

語言如下：

L = {E, 0, 1,00, 11,10,100,.....}

上述語言的正則表示式如下：

R = (1* 0*)

問題 4

編寫包含每個 0 後緊跟 11 的字串的語言的正則表示式。

解答

正則表示式將是：R = (011+ 1)*

Bhanu Priya

更新於: 2021年6月12日

2K+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習