0
$\begingroup$

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

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Consider the NFA N1 = (𝑄1,Σ,𝛿1,𝑞1,F1)

𝑄1 = {q1,q2}

Σ = {0,1}

𝛿1(q1,0) = q1

𝛿1(q2,1) = q2

F1= {q1,q2}

Then 010 ∈ L(N) where N is as you have defined in the incorrect construction. However 010 is not in L(N1)*

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .