Jawaharlal Nehru Technological University Hyderabad B.Tech III AUTOMATA AND COMPILER DESIGN Previous Question Paper (February - 2022 - R15)

To construct a Deterministic Finite Automata (DFA) that accepts strings with an odd number of 0's and an even number of 1's, we define four states representing the parity of 0's and 1's: q00 (even 0's, even 1's), q01 (even 0's, odd 1's), q10 (odd 0's, even 1's), and q11 (odd 0's, odd 1's).

The start state is q00. The transitions are as follows:

• From q00: on 0 go to q10, on 1 go to q01
• From q01: on 0 go to q11, on 1 go to q00
• From q10: on 0 go to q00, on 1 go to q11
• From q11: on 0 go to q01, on 1 go to q10

The final state is q10, as it represents the condition of having an odd number of 0's and an even number of 1's.

The conversion of a regular expression to an NFA is performed using Thompson's Construction algorithm, which builds the NFA compositionally based on the structure of the regular expression.

1. Base cases: For the empty string ε, create a start state with an ε-transition to an accepting state. For a symbol 'a', create a transition from start to end state labeled 'a'.
2. Union (r|s): Create a new start state with ε-transitions to the start states of NFA(r) and NFA(s), and ε-transitions from their end states to a new final state.
3. Concatenation (rs): Connect the end state of NFA(r) to the start state of NFA(s) using an ε-transition.
4. Kleene Closure (r*): Create a new start and end state. Add ε-transitions from the new start to the old start, from the old end to the new end, from the old end back to the old start, and from the new start to the new end to allow for zero occurrences.

Example: For the expression (a|b)*, we first construct the NFA for 'a' and 'b', apply the union construction to get (a|b), and finally apply the Kleene closure construction to obtain the resulting NFA.