這兩個離散有限自動機如何不同？

Question

我有以下語句定義的離散有限自動機：

{ω| ω是任何不在*∪b *中的字符串}

出於某種原因，我只是不理解「a *∪b *」部分。我知道什麼是工會，但這與a * b *有何不同？這兩個陳述的結果DFA是否相同？我需要先創建用於補充此語言的DFA，然後使用該DFA基於此創建上述語言的DFA。

有人可以幫我理解嗎？

Answer 1

我們來分解一下定義，然後看看a* ∪ b*和a* b*之間的區別會更簡單。

• 設定x*指的是任何非負數的符號x的次數（包括零）。這包括空字符串（ε），x,xx,xxx等等。
• 的設置XY是指隨後Y
  • 如果X = {1, 2}和Y = {a, b}，然後XY = {1a, 1b, 2a, 2b}
• 的設置X ∪ Y是指通過X和Y描述的所述集合中的聯合的任何符號，它是在X 。這包括可能在集合X或Y中的任何符號，但不一定是兩者。
  • 如果X = {1, 2}和Y = {a, b}，然後X ∪ Y = {1, 2, a, b}

從上面可以告訴推斷出集a* b*元件是隨後的任何元件在設定b*在該組a*任何元件（請記住，因爲我們使用的是*表示法，所以包含空字符串）。 a* = {ε, a, aa, aaa, aaaa, ... }和b* = {ε, b, bb, bbb, bbbb, ... }。因此a* b* = {ε, a, b, ab, aa, aab, aabb, bb, abb, aabb, ...}。

類似地，我們現在知道a* ∪ b*包括集合a*或b*中的任何元素。因此a* ∪ b* = {ε, a, b, aa, bb, aaa, bbb, aaaa, bbbb, ...}。請注意，沒有任何元素具有符號a和b，因爲它不在集合中。

最後，你可以問什麼是a* b*中的元素，但不在a* ∪ b*。 a* b* \ a* ∪ b* = { x ∈ a* b* | x ∉ a* ∪ b*} = { ab, abb, abbb, ... aab, aabb, aabbb, ..., aaab, aaabb, ... }。這些是和符號a和b其中的元素。

Answer 2

a* U b*是a的所有字符串的語言，僅與b的所有字符串一起：{empty, a, b, aa, bb, aaa, bbb, ...}。不包含這種語言的字符串不僅包含a s或b s，而且包含兩個：{ab, ba, aab, aba, baa, abb, bab, bba, ...}。 a*b*是另一種語言，其由任何as出現在任何b s：{empty, a, b, aa, ab, bb, ...}之前的所有字符串組成。 a*b*是a* U b*的超集，但它不等於它。它既不是在a* U b*中的字符串語言的子集或超集，但它在許多地方確實重疊。由於三種語言都不同，所有三種語言都有不同的DFA。