# Tagged Questions

Necessary properties of formal langagues in certain classes that rely on closure against repetition of certain subwords.

3answers
302 views

### Structure of a Pumping Lemma proof: contradiction or counterexample?

This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact ...
0answers
10 views

### Struggling with Pumping Lemma application [duplicate]

I have studied Pumping Lemma carefully and have solved many exercises about it but I can't get an idea on how to solve this one: can anyone help me? Let L = { w#x | x is a substring of w }. Prove ...
0answers
35 views

### Pumping Lemma to prove that L is not context free

I have the language and I want to prove that is not context-free. So I started like this: is variable. Choose w = Case 1: vxy has no c. Choose i = 2 has more a than c or more b than c. Case 2: ...
1answer
65 views

### How to prove {a^(n^2) | n>0} is not context-free?

So I have a language: $$L = \{a^{n^2} \mid n > 0\}$$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'...
1answer
83 views

1answer
82 views

### Proof that a language is not regular using pumping lemma

I have a language $L$ that I think is not regular: $L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$ I'm using pumping lemma in my ...
0answers
30 views

### Ogden’s lemma on CFG

I'm trying to understand Ogden's lemma, and I know there are 4 cases, but in the next example I can only find 3: Assume A = {$0^n1^m0^k$ | k = $max${n, m}} is CF: Choose z = $0^k1^k0^k ∈ A$, z = ...