Linked Questions
115 questions linked to/from How to prove that a language is not context-free?
3
votes
2
answers
41k
views
Is $a^n b^n c^n$ context-free? [duplicate]
I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language
$$\{a^nb^nc^n\mid n\geq 1\}\,.$$
...
- 156
-1
votes
2
answers
15k
views
How is $a^nb^nc^{2n}$ not a context free language, where as $a^nb^mc^{n+m}$ is? [duplicate]
$L_1 = \{a^mb^nc^{m+n}: n,m>1\}$
I know $L_1$ is CFL and works with a pushdown automata.
$L_2 = \{a^nb^nc^{2n}: n>1\}$
The language $L_2$ should also be a CFL because it looks similar, but ...
- 141
-2
votes
2
answers
3k
views
Pumping Lemma for Context-Free Languages for reversal language [duplicate]
Show that the language L = {ww^Rw: w in {a,b}*} is not a context-free language.
- 17
1
vote
0
answers
5k
views
Context Free Grammar for $\{A^nB^nC^n | n \in \mathbb{N}\}$ [duplicate]
Is $L = \{A^n B^n C^n \mid n \in \mathbb{N}\}$ a context-free language, e.g. $AAAABBBBCCCC \in L$
If so, what's that context-free grammar that produces it?
Nick Mpora
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
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
0
votes
1
answer
2k
views
Create CFG and pushdown automaton for {ww} [duplicate]
I've been trying to make a CFG, a pushdown automaton and a regular expression for the language
$\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$.
I understand how the reverse of the ...
- 125
0
votes
1
answer
320
views
Proving the language of words with equal numbers of symbols non-context-free [duplicate]
Possible Duplicate:
How to prove that a language is not context-free?
I'm having a hard time figuring this out, any help is appreciated.
Let EQUAL be the language of all words over $\Sigma = \{...
user3115
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
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
1
answer
402
views
Proving $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ is not a context-free language [duplicate]
I have the language $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ I and want to prove that it is not context-free by using the Pumping lemma for context-free languages. I am new to this field and I am having ...
- 1
0
votes
1
answer
240
views
Show Language is not context free without pumping lemma [duplicate]
Can we show that following language is not context free using Push down automata approach?
L = {a^i b^i a^i : i>=1}
For every a we will Push 'A' onto stack, ...
- 1
0
votes
1
answer
245
views
Pumping lemma to show a language is not context free [duplicate]
I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start ...
- 153
1
vote
0
answers
240
views
Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language? [duplicate]
Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part.
$$L=\{a^mb^nc^{mn}\mid m>n\}$$
- 11
0
votes
0
answers
215
views
Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]
Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
- 21