Jawaharlal Nehru Technological University Hyderabad B.Tech III AUTOMATA AND COMPILER DESIGN Previous Question Paper (September - 2021 - R13)

To compute the First and Follow sets, we analyze the productions:

• First(F) = { (, id }
• First(B) = { *, ε }
• First(T) = First(F) = { (, id }
• First(A) = { +, ε }
• First(E) = First(T) = { (, id }

Follow sets:

• Follow(E) = { $, ) }
• Follow(A) = Follow(E) = { $, ) }
• Follow(T) = First(A) ∪ Follow(A) = { +, $, ) }
• Follow(B) = Follow(T) = { +, $, ) }
• Follow(F) = First(B) ∪ Follow(B) = { *, +, $, ) }

The NFA for (0+1)(01)*(011)* consists of a start state q0 transitioning to q1 on 0 or 1. From q1, transitions are defined for (01)* and (011)* using intermediate states to track the sequences. Conversion to DFA involves creating subset states: State A={q0}, State B={q1}, State C={q2} (after 0), State D={q3} (after 1), etc., until all transitions are deterministic.

For the input 1011:

• NFA: Start at q0, take transition 1 to q1, then follow the path for 0, 1, 1. Since the final state reached is an accepting state, 1011 is accepted.
• DFA: Starting from the initial state, follow the transitions corresponding to 1, 0, 1, 1. If the resulting state is in the set of accepting states (those containing the NFA final state), the string is accepted.