note:

DFA: Deterministic Finite Automata NFA: Nondeterministic Finite Automata

Problem 3. Let S = {0.1,2,3,4,5,6,7,8,9} {+, x,-, } be an alphabet. A string we is called a simple numeric erpression if it is in one of the following two forms. 1. w consists of one or more digits with no leading zeros. 2. w = w; 2 where w, and w, are also simple nu veric expressions and {+, 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 C 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