[Solved]: Deciding if language is Context-Free

Problem Detail: 

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 \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$, so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

Asked By : mrjasmin

Answered By : Shitikanth

Hint: rewrite $L$ as $L = \{a^p b^r b^q c^s d^t d^q e^r e^p \mid p,q,r,s \ge 0, s>t\}$.

Does $L$ now look like something you can generate with a CFG?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13981

3.2K people like this

 Download Related Notes/Documents