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\}\,.$$ ...
8k 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 ...
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?
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 ...
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 ...
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 ...
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.
254 views

331 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 ...
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=\{... 1answer 139 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, ... 1answer 170 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 ... 0answers 115 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\}$$ 1answer 83 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. 0answers 104 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 ... 0answers 101 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}$... 0answers 84 views ### Proving that$L = \{a^m b^n | m \% n = 0 \}$is not context-free [duplicate] For language$L = \{a^m\, b^n\: |\: m \:\%\: n = 0 \}$, that is,$m$is a multiple of$n$, I'm trying to find a proof that it isn't a context free. I know it isn't regular, but it also doesn't seem to ... 0answers 66 views ### Context-free Language, Pumping lemma [duplicate] I want to prove that$ L = {a^n b^m c^{ \lfloor \frac{n}{m} \rfloor } } $isn't context free language, so I choose N - constant from lemma so the word is$ w = a^N b^N c $and$ w = uvxyz $1 ... 1answer 65 views ### Prove or disprove if L is CFL? [duplicate] Given$L=\{a^ib^jc^k | i\neq j \space and \space j=k\}$. Is this CFL? How do I write CFG for it or prove it with pumping lemma? Thanks. 0answers 60 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 ... 0answers 50 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 ... 1answer 58 views ### using pumping lemma prove this language is not a context-free-language [duplicate] How can one prove that the language below is not context-free using the pumping lemma? $$\{ a^i b^m a^j b^m a^k b^m \mid i,j,k,m \geq 0 \}$$ 1answer 38 views ### Is the language$L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$context free? [duplicate] Is the language$L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$context free? I should probably use Ogden's lemma, but I don't know how to do that in this case. 0answers 34 views ### For$\sum = \{ 0,1 \}$,$A$has strings which contain a$1$in their middle third, and a$B$which contain two$1$'s in their middle third [duplicate] Language$A$can also be represented as, $$A = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$ Language$B$can also be represented as,$$B = \{ ... 0answers 28 views ### Generate a Grammar from a language(Non-CFL) [duplicate] I tried to solve this question, We have this Language, L(g)={AA|A={0+1}*} The output(Productions) must be similar as these = {(11 11), (0 0), (1101 1101), etc..} The left side equal to right side.. ... 0answers 27 views ### Is this language a context-free language? [duplicate] I'm currently trying to figure out whether this language is context-free using the pumping lemma.$\qquad L = \{ v_1 v_2 v_1 v_2 \mid v_1 \in \{a, b\}^*, v_2 \in \{a, c\}^* \}$I'm having trouble ... 0answers 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 ... 0answers 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 ...
I have laid out the various cases that would make this not a context free language already and proved all but one for this set: $$A = \{a^f b^g \mid f = g^2\}$$ ...