95 views

### Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? [duplicate]

Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? I think it is, but I could not find a way to prove it by using push down automaton or any other way.
25 views

### CFG. Ensure that $n\neq m$ twice in $L=\{a^m b^n c^m d^n, m\neq n\}$ [duplicate]

During the formal language exam, the professor allowed to find a CFG to following language: $\{a^m b^n c^p d^q, m\neq n\wedge p\neq q\}(1)$, because neither he saw a solution (He passed a test without ...
102 views

### The pumping lemma - Proving that this language is NOT context free [duplicate]

I would like to find out if this language is context free or not: $\qquad L=\{a^{i}b^{j}c^{k} \mid i<j,i+2j+3<k\}$. I've tried to apply the pumping lemma taking out $w=a^n b^{n+1}c^{3n+6}$ ...
• 33
1 vote
2k views

### Using the pumping lemma to prove that a language is context-free [duplicate]

I am new to automata theory. Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping ...
• 13
24 views

### Prove this language is not CFL [duplicate]

I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL. I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung ...
• 31
459 views

• 141
1 vote