b. Suppose we are willing to pay the cost of converting our regex-derived NFA into a DFA. Give pseudo-code that simulates a DFA running on an input string. It must process all characters of the input....

Extracted text: b. Suppose we are willing to pay the cost of converting our regex-derived NFA into a DFA. Give pseudo-code that simulates a DFA running on an input string. It must process all characters of the input. AsSsume the DFA is represented by a table (which is called its transition function, often denoted by 8). The table maps the current state and current input character to a new state.


Extracted text: c. Analyze your DFA simulator pseudo-code to show its worst-case asymptotic complexity. Give your final answer in Big-Oh notation, and be sure to explain why it is so (e.g. by referring to lines in your pseudo-code).