Linked Questions
115 questions linked to/from How to prove that a language is not context-free?
5
votes
2
answers
2k
views
Pumping lemma: if you can keep pumping, what does this tell you?
Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...
- 51
1
vote
0
answers
44
views
Language involving length constraints and reversal
Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language?
It is turning out to be really tricky. Is there an easy way to show this?
user39969
0
votes
1
answer
103
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.
- 31
0
votes
0
answers
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 ...
0
votes
0
answers
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
1
answer
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
0
votes
0
answers
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
0
votes
1
answer
497
views
How can I prove this language is not CFL? [duplicate]
I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m ...
- 31
0
votes
0
answers
4k
views
How to prove that the language { ww | w ∈ {a,b}* } is / isn't context free? [duplicate]
Is the language { ww | w ∈ {a,b}* } context free?
I have tried to create a pushdown automaton but I didn't find any solution. I think you need a queue and not a stack.
Is there a way to prove this ...
- 1
2
votes
0
answers
41
views
How to use homomorphisms to prove irregularity [duplicate]
I'm a bit confused on how to use homomorphims
to prove irregularity or to prove that a language is not context free.
This is what I'm currently thinking:
Example 1:
Let $L = \{ a^{i}b^{j}c^{k} : i ...
- 141
1
vote
1
answer
536
views
Prove that this language is not context-free [duplicate]
I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L=\{...
- 29
0
votes
0
answers
64
views
The pumping lemma for the context free languages [duplicate]
I am trying to use the pumping lemma to show this is not a context
free language
$$
L = \{a^n b^{2n} a^n\mid n\ge 0\}
$$
My idea is fist assume it is a CFG language and let $n$ be the pumping lemma
...
0
votes
0
answers
19
views
Pumping Lemma for CFG - How to do it? [duplicate]
I'm literally so confused on how to even start this problem of proving that the given language is not Context Free.
L = {a^i b^j c^k d^l | i = k and j = l}
I ...
0
votes
0
answers
51
views
Why is this language is not context-free? [duplicate]
Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this ...
1
vote
2
answers
472
views
Complement and Context Free Surprising
Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free?
$$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$
$$L_{2}= \{w_{1}...
- 139