Linked Questions

5
votes
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$ ...
0
votes
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-...
-1
votes
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 | ...
4
votes
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 ...
2
votes
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 ...
0
votes
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 ...
1
vote
3answers
203 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 \...
0
votes
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 ...
3
votes
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. ...
3
votes
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 ...
1
vote
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 ...
0
votes
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 > ...
0
votes
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 ...
0
votes
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'...
0
votes
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