A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [pumping-lemma]

Necessary properties of formal langagues in certain classes that rely on closure against repetition of certain subwords. Make sure your question isn't covered by applying the techniques in https://cs.stackexchange.com/q/1031/755.

364 questions
Filter by
Sorted by
Tagged with
53 views

96 views

61 views

### What does pump down means in this solution?

Problem text (from Sipser's "Introduction to the Theory of Computation"): 2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for$k \geq 0$, each$t_i \in 1^*$, and$...
108 views

### Closure properties of a non-regular language under complement? [duplicate]

Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language. But let's say if the complement of L1 is a ...
35 views

### Does |xy| ≤ p in the pumping lemma count for all i?

While learning about the pumping lemma, I came across the following question: Given the language L is $a^n(0|1)^*$ with $c_0 \cdot c_1 = n$, where $c_0$ indicates the amount of zeros present, ...
130 views

### Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma

I have the following alphabet: $Σ = {0, 1, . . . , 9}$ and the Language $L$ defined as: $L = \{ abc | a + b = c\}$ where substrings $a$, $b$ and $c$ are interpreted as ordinary integers. My answer ...
62 views

### Pumping lemma — Is this enough to prove that the language L is not regular?

I have a language $L$: $$L = \{w : a^ib^j; i > j \}$$ I need to prove this language is not regular using Pumping Lemma. I'm wondering if I'm doing it correctly: $L$ Is assumed to be regular. A ...
### Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ In my opinion complement of the L language is $L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$ I choose to ...