Linked Questions

3
votes
2answers
22k 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\}\,.$$ ...
-1
votes
2answers
9k 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 ...
1
vote
0answers
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?
0
votes
0answers
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
vote
1answer
1k 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 ...
-1
votes
1answer
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 ...
-3
votes
2answers
2k 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.
0
votes
1answer
254 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 = \{...
0
votes
1answer
415 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 ...
1
vote
1answer
353 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=\{...
0
votes
1answer
333 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 ...
0
votes
1answer
156 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, ...
0
votes
1answer
172 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 ...
1
vote
0answers
118 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\}$$
0
votes
1answer
84 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.

15 30 50 per page
1
2 3 4 5
8