patternModerate
Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?
Viewed 0 times
theincorrectstarnfaoperationunderusingrecognizingresultsstrings
Problem
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^$.
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?
Could someone point this out for me or give me a hint, or have I misunderstood the author? Thanks in advance!
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^$.
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?
Could someone point this out for me or give me a hint, or have I misunderstood the author? Thanks in advance!
Solution
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^*$.
Making the initial state final, would also accept $a^*$.
Context
StackExchange Computer Science Q#83244, answer score: 13
Revisions (0)
No revisions yet.