Prove or disprove (with closure properties or using grammars)

Question

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.

score 2 · Answer 1 · answered Jan 03 '13 at 15:21

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

score 1 · Answer 2 · edited Apr 13 '17 at 12:48

1

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.

edited Apr 13 '17 at 12:48

Community

1

answered Jan 03 '13 at 15:20

Brian M. Scott

616,228

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

Prove or disprove (with closure properties or using grammars)

2 Answers2