To be precise, define delta-hat by:
Define a new function f by:
Your task is to prove, by induction on the length of y (and no other way --- we really want to see an induction), that delta-hat(q,y) = f(q,y).
0 | 1 | |
---|---|---|
p | {q,s} | {q} |
q | {r} | {q,r} |
r | {s} | {p} |
s | {} | {p} |
Use the subset construction to find an equivalent DFA.
In order to make sure that you use nondeterminism, your NFA should have no more than 13 states and 15 arcs. You may represent your NFA by a transition diagram.