题目
COMP30026_2025_SM2 Worksheet 6
多重下拉选择题
Let Σ = {0, 1} and let A = {w ∈ Σ* | w has no 0's and has odd length}, B = {w ∈ Σ* | w has no 1's and has odd length}. Select the correct expressions to make these equations true: (A ∪ B)* = [ Select ] {w ∈ Σ* | w has an even number of 0's, and an odd number of 1's} {w ∈ Σ* | the length of w is odd} Σ* {w ∈ Σ* | neither “01” nor “10” are substrings of w} (A ◦ A) ◦ A = [ Select ] A \ {1} A {w ∈ Σ* | w has no 0's and has length 6n + 3 for some nonnegative integer n} {w ∈ Σ* | w has no 0's} BC ∩ (B ◦ B)C = [ Select ] {ε} {w ∈ Σ* | w = ε or 1 occurs in w} A* {w ∈ Σ* | 1 occurs in w} Hint: set intersection, union, and complement are Boolean operations!
查看解析
标准答案
Please login to view
思路分析
We start by restating the given problem components so we can reason about each expression piece by piece.
- Σ = {0, 1}
- A = { w in Σ* | w has no 0's and has odd length } = {1^k | k is odd}
- B = { w in Σ* | w has no 1's and has odd length } = {0^k | k is odd}
- The three drop-downs to fill are:
1) (A ∪ B)* = [Select]
2) (A ◦ A) ◦ A = [Select]
3) BC ∩ (B ◦ B)C = [Select]
(here ◦ is string concatenation and C denotes complement relative to Σ*, so X C means the complement of X)
- The provided answer choices for each dropdown are as given in the prompt, and the user-provided selections are the three specific strings in the answer array.
Analysis of option 1 for (A ∪ B)* = [Select]
- A ∪ B consists of two kinds of blocks: a block of only 1’s of odd length (from A) and a block of only 0’s of odd length (from B). When you take the Kleene star (A ∪ B)*, you are concatenating any finite sequence of such blocks.
- If you concatenate two blocks of different symbols (e.g., 1^odd followed by 0^odd), at the boundary you inevitably create the substrings 10 or 01. Hence, many words in (A ∪ B)* will contain 01 or 10 as substrings.
- The only words that avoid both 01 and 10 substrings are precisely the words that consist of a single symbol only (all 0’s, all 1’s), including the empty word ε. Equivalently, these are the words w with no occurrences of 01 or 10.
- Therefore, the set of words with no 01 or 10 substrings equals {ε} ∪ 0* ∪ 1*. This is exactly the language of words over {0,1} that contain no switch between symbols.
- Among the given options ......Login to view full explanation登录即可查看完整答案
我们收录了全球超50000道考试原题与详细解析,现在登录,立即获得答案。
类似问题
Let L be a language defined as follows: L = {w | w <- {0,1}* && w does not have any 1s that are separated only by 2n 0s where n ∈ ℕ\{0} } examples: "11", "10001", "0110" are in L "1001", "100001" are not in L Which of the following attempts to prove that L is a non-regular language provides a valid fooling set 'S' + algorithm to choose a distinguishing suffix for a pair of elements in S? Select the most specific answer from the drop-downs below corresponding to the correctness each of the following proofs. Attempt #1: S = { 11, 1001, 100001, ...} = { 102m1 | m ∈ ℕ } ALG = " Given two elements from S 102i and 102j, where i < j, choose suffix 02i1 " Attempt #2: S = { 1, 110, 11100, ...} = { 1m0m-1 | m ∈ ℕ } ALG = " Given two elements from S 1i0i-1 and 1j0j-1, where i < j, choose suffix 0i1 " Attempt #3: S = { 1, 110, 11100, ...} = { 1m0m-1 | m ∈ ℕ } ALG = " Given two elements from S 1i0i-1 and 1j0j-1, where i < j, choose suffix 02j1 " Attempt #4: S = { 100, 110000, 11100000000, ...} = { 1m02^m | m ∈ ℕ\{0} } ALG = " Given two elements from S 1i02^i and 1j02^j, where i < j, choose suffix 02^i " 1: Attempt #1 2: Attempt #2 3: Attempt #3 4: Attempt #4
Let Σ = {0, 1} and let A = {w ∈ Σ* | w has no 0's and has odd length}, B = {w ∈ Σ* | w has no 1's and has odd length}. Select the correct expressions to make these equations true: (A ∪ B)* = [ Select ] {w ∈ Σ* | neither “01” nor “10” are substrings of w} Σ* {w ∈ Σ* | the length of w is odd} {w ∈ Σ* | w has an even number of 0's, and an odd number of 1's} (A ◦ A) ◦ A = [ Select ] A \ {1} {w ∈ Σ* | w has no 0's and has length 6n + 3 for some nonnegative integer n} {w ∈ Σ* | w has no 0's} A BC ∩ (B ◦ B)C = [ Select ] {w ∈ Σ* | w = ε or 1 occurs in w} {ε} {w ∈ Σ* | 1 occurs in w} A* Hint: set intersection, union, and complement are Boolean operations!
Consider the alphabet T={a,b}. Which one of the following is correct?
Which of the following would be a valid partition of the set of all strings A^* over the alphabet A = \{a, b\}?
更多留学生实用工具
希望你的学习变得更简单
加入我们，立即解锁 海量真题 与 独家解析，让复习快人一步！