2k views

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?
180 views

### Is $\{u u^R u : u \in \Sigma^*\}$ context-free?

Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$) I tried to show it wasn't context-free by using the ...
2k views

### PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
205 views

### Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \}$

So i know that $L =$ { ${w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2}$ } is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL i even know the grammar for it ...
I cannot go on with this exercise: Determine whether $L = \{a^nb^m \mid n > 2^m \}$ is context-free. Let's suppose that $L$ is context-free. According to the pumping lemma, there exists $N > ... 1answer 201 views ### Push-down Automata Construction Construct a push-down automata to recognize the language$ A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \} $. Here,$v^{\complement}$is the bit-complement of v. I don't see how to perform ... 1answer 253 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 = \{...
I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...