510 views

Determining whether $L = \{ 0^n1^{n^2} | n \ge 0 \}$ is a CFL

Assuming $L$ is defined as follows: $$L = \{ 0^n1^{n^2} | n \ge 0 \}$$ I'm trying to either prove/disprove whether $L$ is CFL or not. My intuition tells me its not CFL since I cannot express the ...
247 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

Is it possible to prove Language L context-free? [duplicate]

Give a question: Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not. If the answer is yes, can I use the following PDA to prove it? Since {a^n b^(n+m) a^m}={a^n b^n ...
110 views

Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma [duplicate]

In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's ...
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 ...
942 views

Showing that u#v with u a substring of v is not context-free

I need to find whether this language is context-free or not: {u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#} I suspect that it'...
1k views

Structure of a Pumping Lemma proof: contradiction or counterexample?

This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact ...
9k views

How to prove {a^(n^2) | n>0} is not context-free?

So I have a language: $$L = \{a^{n^2} \mid n > 0\}$$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'...
421 views

Why do we study closure properties of formal languages?

In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is ...
12k 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 ...
148 views

Showing that $\mathscr{L}$ is not context-free-grammar language

Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leqslant i\leqslant |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$. Prove ...
1k views

Use the pumping lemma to prove that {www} is not context-free

Use the pumping lemma to prove that the following language is not context-free. $\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$ I am studying for an exam and really trying to understand this question. ...
206 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, ...
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?