Note:

DFA = Deterministic Finite Automata NFA = Nondeterministic Finite Automata

Problem 3. Let S = {0,1,2,3,4,5,6,7,8,9}U{+,x, -, - } be an alphabet. A string we is called a simple numeric expression if it is in one of the following two forms. 1. w consists of one or more digits with no leading zeros. 2. w=wing where u and we are also simple numeric expressions and E{+, X, -, *} Therefore 1074 is a simple numeric expression of the first kind; 50 +7 is a simple numeric expression of the second kind; and 2 - 700 X 8 - 10 is also a simple numeric expression because of its recursive definition. Let S S be the set of all such simple numeric expressions. We also note that O ES because O is a digit without any leading zeros. (a) Give a DFA or an NFA that recognizes S. (b) Give a regular expression that recognizes S