Consider the NFA specified by the following transition table with start state p and set of...

Transcribed Image Text:

Consider the NFA specified by the following transition table with start state p and set of accepting states {s,t}. State/symbol 0 1 p {p,q} {p} 9 {r. s} {t} r {p,r} {t} * S * t {q, s} 0 0 {p} a. [3 points] Give three different computation paths of the NFA for the input 001. b. [3 points] What is 8* (p,001), the set of states reached after input 001? Is 001 accepted? c. [10 points] Convert the NFA to a DFA using the subset construction. Give the DFA by its transition table, and include only the states that are reachable from the initial state. Make sure to indicate the start state and the accepting states of the DFA. Consider the NFA specified by the following transition table with start state p and set of accepting states {s,t}. State/symbol 0 1 p {p,q} {p} 9 {r. s} {t} r {p,r} {t} * S * t {q, s} 0 0 {p} a. [3 points] Give three different computation paths of the NFA for the input 001. b. [3 points] What is 8* (p,001), the set of states reached after input 001? Is 001 accepted? c. [10 points] Convert the NFA to a DFA using the subset construction. Give the DFA by its transition table, and include only the states that are reachable from the initial state. Make sure to indicate the start state and the accepting states of the DFA.