题目
COMP30026_2025_SM2 2025 sample exam - Requires Respondus LockDown Browser
匹配题
Let L be a language defined as follows: L = { w | w ∈ {0,1}* && w does not have any 1s that are separated only by 2*n 0's where n ∈ ℕ\{0} } examples: "11", "101", "00", "010" are in L "1001", "10100001" 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? For each of the following attempts, select the most specific answer from the respective drop-down. Attempt #1: S = { 1, 100, 10000, ...} = { 102m | m ∈ ℕ } ALG = " Given two elements from S 102i and 102j, where i < j, choose suffix 02i1 " Attempt #2: S = { 1, 10, 100, ...} = { 10m | m ∈ ℕ } ALG = " Given two elements from S 10i and 10j, where i < j: IF (i even and j odd || j even and i odd) -> Choose suffix "1" ELSE -> Choose suffix "0i1" " Attempt #3: S = { 0, 10, 100 } ALG = " Choose the suffix according to the following map of element pairings: (0,10) -> choose suffix "01" (0,100) -> choose suffix "1" (10,100) -> choose suffix "1" " 1: Attempt #1 2: Attempt #2 3: Attempt #3
选项
A.False - S not a fooling set.
B.False - Insufficient proof.
C.False - S is a fooling set, but ALG does not always choose a distinguishing suffix.
D.True - Valid proof.
查看解析
标准答案
Please login to view
思路分析
Question restatement:
- We are given a language L over {0,1} where w ∈ L if and only if w has no occurrence of two 1s that are separated by exactly 2n zeros for any n ∈ ℕ \ {0}. In other words, we must avoid patterns 1 0^{2n} 1 for any n ≥ 1 within w. The task presents three attempts to form a fooling set S and an accompanying algorithm (ALG) to choose a distinguishing suffix for a pair of elements in S, and asks, for each attempt, to select the most specific matching description from the provided drop-down options. The drop-down options are:
- False - S not a fooling set.
- False - Insufficient proof.
- False - S is a fooling set, but ALG does not always choose a distinguishing suffix.
- True - Valid proof.
Attempt #1:
S = { 1, 100, 10000, ...} = { 1 0^{2m} | m ∈ ℕ }
ALG = " Given two elements from S 102i and 102j, where i < j, choose suffix 02i1. "
Analysis for Attempt #1:
- The set S here consists of strings that start with 1 followed by an even number (2m) of zeros. This construction aims to create a family of prefixes that interact with the no-1s-separated-by-2n-zeros constraint in a way that allows a distinguishing continuation.
- A fooling set requires that for any two distinct members x and y of S, there exists a suffix z (which may depend on the chosen pair (x,y)) such that exactly one of xz or yz is in L. The proposed ALG selects a fixed-form suffix depending on i and j (specifically 02^i 1 in the notation given). To be valid, this suffix must distinguish every pair (1 0^{2i}, 1 0^{2j}) with i ≠ j.
- Potential issues: (a) The suffix 02i1 must be interpreted precisely; if the intended suffix is 0^{2i} 1 or 0 2^i 1, the meaning changes. Either interpretation must be checked against the actual property of L. (b) It is not immediately obvious that appending 0^{2i} 1 to both 1 0^{2i} and 1 0^{2j} yields one string in L and the other not ......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^i1" 1: Attempt #1 2: Attempt #2 3: Attempt #3 4: Attempt #4
Let 𝐿 be the language consisting of bit strings of the form 𝑤 𝑤 . More precisely, 𝐿 = { 𝑤 𝑤 ∣ 𝑤 ∈ Σ ∗ } . So, 𝐿 contains 𝜖 , 00 , 11 , 1010 , 0101 , 1111 , 101101 , … Select all options that are fooling sets of size at least k.
L = {(01)n(10)m | n ≥ 0, m ≥ 2} is a regular language. Select the errors that are present in the following fooling set ‘proof’ that L is not regular: Proof (attempt): Suppose there is a DFA with k states that recognises L. Consider the set S = {(01)n | 1 ≤ n ≤ k}. Every pair of strings in S can be written as (01)i and (01)j, with i<j. These two strings are distinguishable with respect to L with the distinguishing suffix (10)i, as (01)i(10)i is in L but (01)j(10)i isn't. Thus every pair of distinct strings in S is distinguishable with respect to L, and so S is a fooling set of size k. Thus, there cannot exist a DFA with k states that recognises L. Because k was arbitrary, no DFA that recognises L can exist, and so L is not regular.
In a consumer society, many adults channel creativity into buying things
更多留学生实用工具
希望你的学习变得更简单
加入我们，立即解锁 海量真题 与 独家解析，让复习快人一步！