A comprehensive lab series for regular languages topics Arit

A comprehensive lab series for regular languages topics: Arithmetic Expressions

This lab series is an exercise for topics learned from Chapter 11 about regular languages. It must be finished step by step. For solutions that involve the use an algorithm (e.g., transform an automaton to a grammar), step-by-step extrication of the algorithm must be included in your submission. The tasks of this project are:

Activity 1: Define a language for arithmetic expressions that consist of unsigned integer numbers and operators +, -, *, and /. An unsigned integer number consists of any number of digits (0 through 9), but contains no leading zeros. For example, 0, 1, 700, 101, 10 are all acceptable integers, but 00, 01, 0009, 0101 are not.

An arithmetic expression consists of any number of unsigned integer numbers connected by the four operators. No parenthesis are used.

Write a regular expression for the arithmetic expressions defined above.

Activity 2: Transform the regular expression to an NFA using the algorithm in Section 11.2.3.

Activity 3: Transform the NFA to a DFA using the algorithm in Section11.3.2. Activity 4: Transform the DFA to a minimum state DFA using the algorithm in Section

11.3.3.
Activity 5: Transform the NFA to regular grammar using the algorithm in Section 11.4.1.

Activity 6: Transform the minimum state DFA to regular grammar using the same algorithm in Activity 5. Compare the results of Activity 5 and 6.

Solution

Activity 1:

Arithmetic expressions that consist of unsigned integer numbers and operators +, -, *, and /. An unsigned integer number consists of any number of digits (0 through 9), but contains no leading zeros is as below

(0|[1-9][0-9]^* [+, -, *, /] 0|[1-9][0-9]^*)^*