# Closure of regular languages, Star Operator

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

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

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