Show with a counterexample that the following construction doesn't prove the closure of regular languages at the concatenation. In other words, find a NFA $N_1$ such that the NFA $N$ of the construction doesn't recognize the concatenation of the language of $N_1$.

Let $A_1$ be a regular language and let $N_1=(Q_1, \Sigma , \delta_1 , q_1, F_1)$ be a NFA that accepts $A_1$. To show that $A_1^{\star}$ is also regular, we construct a NFA $N=(Q_1, \Sigma , \delta, q_1, F)$ that accepts $A_1^{\star}$, as followed.

  1. The states of $N$ are the states of $N_1$.
  2. The start state of $N$ is the start state $N_1$.
  3. $F=F_1 \cup \{q_1\}$.
  4. $\delta(q,a)=\left\{\begin{matrix} \delta_1(q,a) & \text{ if } q \notin F_1 \text{ or } a \neq \varepsilon\\ \delta_1(q, a)\cup \{q_1\} & \text{ if } q \in F_1 \text{ and } a=\varepsilon \end{matrix}\right.$

Coud you give me some hints how we could find such a counterexample??

  • 1
    $\begingroup$ $A_1 = A$, right? And you mean the star operator, not the concatenation? $\endgroup$ – J.-E. Pin Mar 12 '15 at 0:10
  • $\begingroup$ I have edited my post... @J.-E.Pin $\endgroup$ – Mary Star Mar 12 '15 at 0:19
  • $\begingroup$ Hint: maybe think about some boundary cases. $\endgroup$ – ShyPerson Mar 12 '15 at 23:55

What happens if $Q_1 = \emptyset$? Hint: $\emptyset^* = \{\varepsilon\}$.


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.