Linked Questions

2
votes
1answer
523 views

How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help. The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should ...
2
votes
1answer
458 views

Is the language $\{a^n b^n c^i | i \leq n\}$ context free?

I'm trying to apply the CFL pumping lemma. And, I've already tried words $a^pb^p$ and $a^pb^pc^p$. Not sure where to go from here.
2
votes
0answers
40 views

How to use homomorphisms to prove irregularity [duplicate]

I'm a bit confused on how to use homomorphims to prove irregularity or to prove that a language is not context free. This is what I'm currently thinking: Example 1: Let $L = \{ a^{i}b^{j}c^{k} : i ...
2
votes
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 = \{ ...
1
vote
2answers
141 views

Is a^mb^n where m=n^2 a CFL?

Is $a^mb^n$ where $m=n^2$ a CFL? I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right? On the other hand I ...
1
vote
3answers
215 views

Deciding if language is Context-Free

I need help with deciding if $L$ is context-free. $$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$ Can be rewritten into: $$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \...
1
vote
1answer
6k 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'...
1
vote
3answers
162 views

Determine whether two languages are context free

(1) $L_1 = \{a^ib^{i+j}c^j|i,j\geq 0\} $ (2) $L_2 = \{xy | x,y \in \{0,1\}^*, x \neq y, |x| = |y| \}$ I doubt that $L_1$ is CFL. I've been trying to go with the string $s$ = $a^pb^{2p}c^p$. Thus, we ...
1
vote
2answers
2k views

Proof that a language involving $gcd$ is not context-free

How would you prove that the following language is not context-free? $$ L= \{a^n b^m |\, gcd(n,m)=1 \}$$ I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.
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
vote
1answer
66 views

Is this language is Context-free language or not?

Is anybody can help me please to determine is this language is Context-free language or not? L={wvw | w,v∈{a,b,c}+} for example: part of the language: acbac, abcab, bbcbb not part of the language:...
1
vote
1answer
66 views

Is regular expression syntax regular?

Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular? My guess is that the original syntax (concat, | and *) ...
1
vote
1answer
98 views

Applying the context-free pumping lemma to a language with crossed nestings

For proving language $\{a^nb^mc^nd^m \mid n,m > 0\}$ is not context free. Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length? Or do I have to use a string that ...
1
vote
1answer
33 views

How to prove that a language is not context-free using pumping lemma

I'm trying to prove that that language isn't a context free: $ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$ I succeed to prove that $L = ww$ isn't context free, but not the language above. What ...
1
vote
1answer
413 views

Prove not context free

How can we prove that: $$ L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\} $$ is not context-free? The language defines $w_1$ as a sub-string of $w_2$, and they ...

15 30 50 per page
1 2
3
4 5
8