1
$\begingroup$

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

$\endgroup$
1
$\begingroup$
  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\} \]
$\endgroup$
  • $\begingroup$ For #3 what would be a regular expression? $\endgroup$ – Thresh Nov 1 '12 at 21:07
  • $\begingroup$ @BrianM.Scott You're right of course. $\endgroup$ – martini Nov 1 '12 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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