Pick all non-regular languages:

Notes

Assume they are defined over the appropriate Sigma.
Spaces are added to the patterns for readability purpose.

Question

Pick all non-regular languages:

Notes

Assume they are defined over the appropriate Sigma.
Spaces are added to the patterns for readability purpose.

BlackTom AI · Accepted Answer

1. Relevant knowledge points and concepts
- Pumping Lemma for regular languages: if L is regular, there exists p such that any s in L with |s| ≥ p can be decomposed s = xyz with |xy| ≤ p, |y| > 0, and for all i ≥ 0, xy^i z ∈ L.  
- Regular languages include simple periodic unary sets (e.g., {1^(2k)}), which can be recognized by a 2-state DFA.  
- Palindrome-like constraints (matching counts or mirrored structure) typically force non-regularity over alphabets with ≥2 symbols.

2. Step-by-step reasoning for each candidate

A) L1 = { 1^n + 1^m = 1^(n+m) : n>0, m>0 } over alphabet {1,+,=}  
- Assume L1 is regular with pumping length p. Choose s = 1^p + 1^p = 1^{2p} ∈ L1.  
- By pumping lemma, s = xyz with |xy| ≤ p and |y| > 0, so y consists only of 1’s from the first block 1^p. Let |y| = t (t ≥ 1).  
- Pump i = 0: xz = 1^{p-t} + 1^p = 1^{2p}. The left-hand side sum equals (p - t) + p = 2p - t, but the right-hand side has 2p ones. So xz ∉ L1.  
- Contradiction → L1 is not regular.

B) L2 = { w w^R : w ∈ Σ* } (assume Σ contains at least two symbols, e.g., {a,b})  
- Assume L2 is regular with pumping length p. Pick w = a^p b so s = w w^R = a^p b b a^p ∈ L2.  
- Decompose s = xyz with |xy| ≤ p, |y| > 0. Then y is a^t with t ≥ 1 inside the first a^p block.  
- Pump i = 0: xz = a^{p-t} b b a^p. Leading a’s = p - t, trailing a’s = p, so the string cannot be of the form ww^R (the two halves are no longer mirror images). Hence xz ∉ L2.  
- Contradiction → L2 is not regular.

3. Intermediate calculations shown above
- For L1: after removing y of length t, left sum = (p - t) + p = 2p - t ≠ 2p.  
- For L2: leading a’s p - t ≠ trailing a’s p, violating mirror property.

4. Why the correct answers are correct
- Both L1 and L2 impose exact arithmetic or mirrored equality constraints that cannot be preserved under the pumping lemma’s required repetitions, so they are non-regular.

5. Why the other options are incorrect
- {1^(2k) : k ≥ 0} is regular: regular expression (11)* or a 2-state DFA tracking parity.  
- "None is correct." is false because there do exist non-regular languages among the options (L1 and L2).

6. Conclusion
The non-regular languages are "{ 1^n + 1^m = 1^(n+m) : n > 0 , m > 0 }" and "{ w w^R : w E Sigma-star }", matching the provided answer.

Pick all non-regular languages: Notes Assume they are defined over the appropriate Sigma. Spaces are added to the patterns for readability purpose.多项选择题

类似问题

A language L is regular if: (Pick all true statements)

Both the Deterministic and Non-Deterministic finite automata are equivalent in expressive power to the language of regular expressions.

Pick all true statements about formal languages:

If L1 and L2 are regular languages, pick which of the following operations produce a regular language:

Which one is correct?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单