# Prove or disprove (with closure properties or using grammars)

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.

-

## 2 Answers

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$.

-

HINTS:

(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.

-
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