9
$\begingroup$

I'm currently reading the book Introduction to the Theory of Computation (2nd or 3rd Ed.) by Michael Sipser, and have stumbled upon a question in Chapter 1 - Regular Languages, namely when the author is presenting the proof idea of Theorem 1.49 - "The class of regular languages is closed under the star operation." using NFA.

The approach suggested is that, if we have a regular language $A_1$ and want to prove that $A_1^*$ also is regular, we can take an NFA $N_1$ and modify it into an $N$ as in the image below, which is then a particular NFA recognizing $A_1^*$.

Modifying the NFA $N_1$

He noted:

One (slightly bad) idea is simply to add the start state to the set of accept states. This approach certainly adds $ε$ to the recognized language, but it may also add other, undesired strings.

I have drawn the "bad" NFA as below and tried to figure out why this will result in undesired strings. However, I can't find an example of when the an undesired string is recognized. Why will this idea result in the NFA recognizing undesired strings?

enter image description here

Could someone point this out for me or give me a hint, or have I misunderstood the author? Thanks in advance!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
13
$\begingroup$

Consider a two state automaton for the language $a^*b$, two transitions from the initial state, one looping with label $a$, the other with label $b$ to the final state.

Making the initial state final, would also accept $a^*$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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