Part 1: Define a language for unsigned binary integer numbers. An unsigned binary integer number consists of any number of digits (0 or 1), but contains no leading zeros. For example, 0, 1, 100, 101, 10 are all acceptable integers, but 00, 01, 0001, 0101 are not.
Q: Write a regular expression for unsigned binary integer numbers described above.
Part 2: Transform the regular expression to an NFA.
Part 3: a - Transform the NFA to a DFA using the algorithm.
b - Transform the DFA to a minimum state DFA using the algorithm.
Part 4: Transform the NFA to regular grammar.
Part 5: Write a context-free grammar for arithmetic expressions consisting of non-negative binary integer numbers defined in Activity 1 and four operators, + (addition), - (subtraction), * (multiplication), and / (division).
No precedence needs to be considered in the grammar. In addition, no parentheses will be used in expressions.
For case, (10 + 1) * 101 is not acceptable. The regular grammar you have obtained in part 1 should be included as part of your solution.
Part 6: Transform the context-free grammar obtained in Part 5 to a pushdown automaton.
Part 7: Write parsers for arithmetic expressions. Transform your grammar into a LL(1) grammar.
You may need to do a left-factoring of common prefix of productions, and/or to remove any left-recursive productions in the grammar for arithmetic expressions. Then prepare a recursive-descent parser for the context-free grammar for arithmetic expressions.
Part 8: Use the LL(1) grammar obtained in Activity 7 and design the parse table for top-down parsing. Include the computation of all first sets and follow sets in your answer.
Part 9: Design a Turing machine that accept expressions defined in Part 5.
Suppose the tape head is initially at the left end of the input string. If the input string is acceptable, the tape head must be at the right end of the output string. There are no blank cells in the input string.
You need to prepare a regular expression for unsigned binary integer numbers explained in the above question.