题目
题目

COMP30026_2025_SM2 2025 sample exam

匹配题

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

选项
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
思路分析
The problem asks us to evaluate four proposed fooling-set proofs for the non-regularity of a language L, by inspecting the given fooling set S and the proposed distinguishing suffix algorithm ALG, then selecting the most specific correct assessment among the four attempts. Option 1: "False - S is a fooling set, but ALG does not always choose a distinguishing suffix." - This claim asserts that S qualifies as a fooling set but the algorithm ALG fails to always pick a distinguishing suffix for all pairs. To evaluate this, we would need to verify two things: (a) S meets the fooling-set criteria (for all i, x_i y_i ∈ L, and for i ≠ j, x_i y_j ∉ L for some appropriate y_j), and (b) the particular suffix chosen by ALG when given a pair (102i, 102j) with i < j (namely 02i1) actually distinguishes x_i from x_j. The reasoning in this option is inconclusive without checking the detailed membership of the concatenations for all i, j and for the specified suffixes. In many standard fooling-set arguments, careless choices of suffix fail to disti......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 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

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

更多留学生实用工具

加入我们，立即解锁 海量真题 与 独家解析，让复习快人一步！