314 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 ...
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-...
352 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$ ...
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 | ...
586 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 ...
804 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 ...
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 ...
485 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 ...
474 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. ...
208 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 \...
330 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 ...
380 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'...
### 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 ...