JNTU B.Tech III COMPILER DESIGN Previous Question Paper (February/March - 2022 - R18)

The construction of a Deterministic Finite Automaton (DFA) from the regular expression (a|b)*aab(a|b)* involves the following steps:

1. Convert the regular expression into a Non-deterministic Finite Automaton (NFA) using Thompson's construction. This involves creating individual NFAs for each sub-expression and connecting them using epsilon transitions.
2. Convert the NFA to a DFA using the Subset Construction (or Powerset Construction) algorithm. This process involves creating a new DFA state for every set of NFA states reachable by a specific input symbol.
3. Define the start state of the DFA as the epsilon-closure of the start state of the NFA.
4. For each DFA state and each input symbol in the alphabet, compute the set of reachable NFA states and mark these as a new DFA state if not already visited.
5. Identify all DFA states that contain at least one accepting state from the original NFA as final states.
6. Minimize the resulting DFA by merging equivalent states using the state minimization algorithm (e.g., Hopcroft's algorithm) to ensure the fewest number of states.

A Lex program performs lexical analysis by matching input text against regular expression patterns and executing associated C code actions. The structure consists of three sections: definitions, rules, and user subroutines.

For identifying arithmetic operators and identifiers, the rules section defines patterns:

[a-zA-Z_][a-zA-Z0-9_]* { printf("Identifier: %s\n", yytext); }
[\+\-\*\/]          { printf("Operator: %s\n", yytext); }

When the lexer runs:

1. The input stream is scanned to find the longest match for the defined patterns.
2. If an identifier (e.g., 'count') is matched, the rule for identifiers triggers, and the action prints the token type and the matched string stored in the global variable yytext.
3. If an arithmetic operator (e.g., '+') is encountered, the operator rule matches, and the corresponding action executes.
4. The lexer continues this process until the entire input is consumed or an error occurs.