JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (March - 2021 - R18)

To convert a Mealy machine to a Moore machine, we split states based on the output associated with incoming transitions. If a state q has multiple incoming transitions with different outputs, we create multiple versions of q (e.g., q/0 and q/1) to ensure the output is consistent for every state in the Moore machine.

1. Identify all unique (state, output) pairs from the Mealy machine transitions.

2. Create a new state in the Moore machine for each unique pair.

3. For each new state, define the output as the output component of the pair.

4. For each transition in the original Mealy machine from state q to state p with input 'a' and output 'x', create a transition in the Moore machine from the state representing (q, any) to the state representing (p, x) with input 'a'.

5. If the initial state of the Mealy machine has no incoming transitions, create a new initial state with a default output, or if it does, ensure the Moore machine initial state reflects the output produced by the Mealy machine's initial transitions.

The conversion of an NFA to a DFA uses the subset construction algorithm (also known as powerset construction) to track all possible states the NFA could be in after a specific input sequence.

1. Start State: The start state of the DFA is the epsilon-closure of the NFA's start state.

2. Transition Function: For each DFA state (which is a set of NFA states) and each input symbol 'a', the new DFA state is the epsilon-closure of the union of all NFA states reachable from the current set on input 'a'.

3. Final States: Any DFA state that contains at least one final state from the original NFA is marked as a final state in the DFA.

4. Iteration: Repeat the transition process for all new sets of states until no new sets are created. If a set of states has no transitions for an input, it maps to a dead state (trap state).