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 = wi w2 where w and u2 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 CS' be the set of all such simple numeric expressions. We also note that 0 S 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