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

1 Answers 1

1
  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\} \]
  • 0
    @BrianM.Scott You're right of course.2012-11-01