Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

1) Define $L = \{a^i*b^j*c^k*d^m \mid \text{ if } a=1 \text{ then } j=k=m\}$. Is $ L$ a context free language ?

2) If $L$ is a context free language then $\mathrm{Mirror}(L) = \{ww^r \mid w \in L \}$ is also a context free language?

3) If $L$ is a context free language, then $\mathrm{Sub}(L) = \{x \mid \exists\, y\in\Sigma^*,\; xy\in L\}$ (prefix languages) is also a context free language. ($x$ is prefix of $w$ if there is exists word $y$ such that $xy = w$)

Thanks in advance! I really need your help.

share|cite|improve this question

Since this is tagged as homework, I'll give a hint for each problem.

Hint(1). Form the intersection of $L$ with the language denoted by the regular expression $ab^*c^*d^*$. What do you get?

Hint(2). Let $L=\{a^nb^n\,\vert\, n\ge 0\}$. What is Mirror(L)?

Hint(3). Use a Chomsky Normal Form grammar for $L$.

share|cite|improve this answer


(1) Let $R$ be the language generated by the regular expression $ab^*c^*d^*$; what is $R\cap L$?

(2) The language $\{a^nb^n:n\in\Bbb N\}$ is context free. Is $\{a^nb^{2n}a^n:n\in\Bbb N\}$?

(3) This problem is a special case of this question; the extended hints given by Raphael and sdcwc are especially helpful.

share|cite|improve this answer
Heh. As usual, you beat me by seconds. – Rick Decker Jan 3 '13 at 15:21
Time's up: +1. Are you my heretofore-unknown twin? – Rick Decker Jan 4 '13 at 1:39
@Rick: And returned. If I am, I must have been an awfully delayed birth! – Brian M. Scott Jan 4 '13 at 14:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.