0 votes 0 votes Find an nfa that accepts {a}* and is such that if in its transition graph, a single edge is removed (without any other changes), the resulting automaton accepts {a}. Theory of Computation theory-of-computation finite-automata + – Vishal Goel asked Apr 24, 2017 retagged Jun 18, 2019 by Cristine Vishal Goel 2.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes The obvious answer is no, but this is not so easy to defend. One way to argue is that for a dfa to accept {a} ∗ , its initial state must be a final state. Removing any edge will not change this, so the resulting automaton still accepts λ. shreyansh jain answered Apr 25, 2017 shreyansh jain comment Share Follow See all 3 Comments See all 3 3 Comments reply Vishal Goel commented Apr 25, 2017 reply Follow Share We need to design an nfa, not a dfa. The solution given in the book (pasted below), however, seems wrong to me because if we remove the first edge a (directly from initial state to final state), we still have an nfa that accepts the language a*. 0 votes 0 votes Ahwan commented May 5, 2017 reply Follow Share Its correct. Remove either epsilon transition or that loop, it will still accept a. Remove the 1st edge. Still it accepts a* hence accepts {a} too. 0 votes 0 votes Vishal Goel commented May 5, 2017 reply Follow Share According to me, the question asks that for the new dfas after removal of one edge (let's call all of them M), L(M) = {a}. Even if thr question doesn't, is it possible? 0 votes 0 votes Please log in or register to add a comment.