Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
What have you tried? –  dtldarek Jan 3 '13 at 13:16

2 Answers 2

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|improve this answer

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.

share|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

 
discard

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.