# Linked Questions

2answers
348 views

### Why is the following language not context-free?

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck. Assuming that $a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
2answers
1k views

### Existence of non-context free but decidable languages

I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-...
1answer
1k views

### Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps: S -> T T | U T -> 0 T | ...
1answer
571 views

### A context free grammar proof

There is a problem which I cannot solve. If you give a tip I will be very glad. Prove that following language is not context free: $L= \{ a^nb^m | \gcd(n,m) = 1 \}$. It can be proven using the ...
2answers
296 views

### Does this language have a context-free grammar?

Here is a question that I encountered in one of my exams: Find one context-free grammar that recognizes the language: $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\}$ Can you find such a ...
3answers
594 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 ...
3answers
203 views

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 \... 1answer 417 views ### Prove that L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \} is not CFG Can someone help me prove that L = \{ a^ib^jc^k | i < j \ and \ i+2j+3 < k \} is not a context free language? I've tried applying the pumping lemma for CFGs and proving case by case (taking ... 1answer 390 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. ... 1answer 136 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 ... 3answers 153 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 ... 1answer 194 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 > ... 1answer 182 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 290 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'... 1answer 286 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 ...

15 30 50 per page