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

I'm stuck on these practice problems. If someone could help me solve them it would be great.

  1. What is a contextfree grammar for the langauge $L = \{a^i b^j c^j d^i \mid i,j \ge 0\}$

  2. The following claim is false. Explain why it is false and make a modification to the claim so that it becomes true.

    Claim: Let $N = (Q, \Sigma, \delta, q_0, F)$ be an NFA with a unique final state, $F = \{q_f\}$. Suppose we add the production $\delta(q_f, \lambda) = q_0$ to $\delta$. Then the resulting NFA accepts the language $L(N)^*$

  3. Give a regular expression for the language $L = \{w \in \Sigma^* \mid 1 \le |w| \le 3\}$. Here $\Sigma = \{a,b\}$.

share|cite|improve this question
  1. To find a context free grammar for $L$, note that a word of $L$ can be generated by first adding $a$s and $d$s on both sides of the starting symbol $S$, and afterwards, adding $b$s and $c$s. So a grammar will be \[ \{S \to T\mid aSd, T \to \lambda \mid bTc \} \]
  2. Denote the modified NFA by $N^+$. As we needn't have $q_f \in \delta^*(q_0, \lambda)$, $\lambda$ needn't be accepted by $N^+$, and then (of course) $L(N)^* \ne L(N^+)$. But we have $L(N^+) = L(N)^+ =\bigcup_{n\ge 1} L(N)^n$.
  3. We use the variables to count the number of symbols we need to add, let $S_3$ denote the starting symbol, then a grammar is \[ \{S_3 \to aS_2\mid bS_2, S_2 \to aS_1\mid bS_1 \mid \lambda, S_1 \to a \mid b \mid \lambda \} \] another grammar would be (starting variable $S$) \[ \{S \to aaa \mid aab \mid aba \mid abb \mid baa \mid bab \mid bba \mid bbb \mid aa \mid ab\mid bb\mid a \mid b\} \]
share|cite|improve this answer
For #3 what would be a regular expression? – Thresh Nov 1 '12 at 21:07
@BrianM.Scott You're right of course. – martini Nov 1 '12 at 21:23

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.