Linked Questions

1
vote
1answer
430 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 ...
0
votes
1answer
249 views

Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free?

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 > ...
0
votes
1answer
400 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 ...
3
votes
1answer
137 views

Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free

This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not ...
0
votes
1answer
215 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 ...
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 ...
0
votes
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 ...
0
votes
1answer
322 views

Pumping lemma with multiple of prime number + a constant

Given the language $$L = \big\{ 0^{m} 1 0^{2m+k} \mid m \text{ prime and } k \ge 1 \big\} $$ show that $L$ is not context free by giving a counterexample of the context free pumping lemma. It may be ...
6
votes
1answer
501 views

Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}...
0
votes
2answers
203 views

Complement and Context Free Surprising

Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free? $$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$ $$L_{2}= \{w_{1}...
2
votes
2answers
118 views

Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?

I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma. I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but ...
3
votes
2answers
64 views

Can the pumping lemma for context free languages be extended to any subword?

It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...
0
votes
1answer
173 views

Does a pushdown automata exists for the following language?

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 ...
0
votes
1answer
157 views

How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ? [closed]

How are these Context-Free Pumping Lemma Approaches differ? Maybe this might help understand pumping lemma better $(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$} $(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$} ...
-1
votes
1answer
153 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = a^mb^...

15 30 50 per page
1
4 5
6
7 8