## RGPV 2010, 02

## Q. Write short note on equivalent of DFA and NDFA ?

## Solution:

If from a regular set an NDFA is created than there may be chances of existence of DFA.

DFA is 5 tuple machine:

M = (Q, Σ, δ, q0, F)

- Q is a finite non empty set of states.
- Σ is a finite non empty set of input symbols.
- δ is a transition function, QXΣ int to Q
- q0 is an initial state belong to Q.
- F is the set of final states belong to Q.

NDFA is 5 tuple machine:

- M = ( Q, Σ, δ, q0, F )
- Q is a finite non empty set of states.
- Σ is a finite non empty set of input symbols.
- δ is a transition function, QXΣ int to 2Q
- q0 is an initial state belong to Q.
- F is the set of final states belong to Q.

Component | DFA | NFA |
---|---|---|

Definition | (Q, Σ, δ, q₀, F) | (Q, Σ, δ, q₀, F) |

States (Q) | Finite set of states | Finite set of states |

Alphabet (Σ) | Finite alphabet (input symbols) | Finite alphabet (input symbols) |

Transition Function (δ) | Q × Σ → Q | Q × Σ → P(Q) |

Initial State (q₀) | Initial state in Q | Initial state in Q |

Accepting States (F) | Set of accepting (final) states | Set of accepting (final) states |

Determinism | Transitions are deterministic | Transitions can be non-deterministic |

Transition Ambiguity | None | Multiple transitions possible |

Uniqueness of Paths | Unique path for each input symbol | Multiple paths for each input symbol |

Language Recognition | Determines acceptance or rejection | Determines acceptance or rejection |

Equivalence | Equivalent to NFA with one state per DFA state | Equivalent to DFA |

Memory Usage | Generally more memory efficient | May use more memory due to multiple transitions |

Size (States) | May have more states due to determinism | May have fewer states due to non-determinism |

**Problem**: Convert the following Non-Deterministic Finite Automata (NDFA) to Deterministic Finite Automata (DFA).

Transition table for NDFA from above NDFA transition diagram

State | Input 0 | Input 1 |

->q0 | q0 | q0, q1 |

q1 | – | *q2 |

q2 | – | – |

Transition table for DFA from above NDFA transition table

State | Input a | Input b |

->q0 | q0 | {q0, q1} |

{q0, q1} | q0 | *{q0, q1, q2} |

*{q0, q1, q2} | q0 | *{q0, q1, q2} |

Transition diagram from above DFA transition table

## Q1: What is the difference between a DFA and an NFA?

**Ans:** A DFA (deterministic finite automaton) is a type of finite automaton that has a single unique next state for every input symbol in each state, while an NFA (nondeterministic finite automaton) can have multiple possible next states for a given input symbol in each state.

## Q2: Can every NFA be converted to an equivalent DFA?

**Ans:** Yes, every NFA can be converted to an equivalent DFA. This is done using the subset construction algorithm.

## Q3: What is the subset construction algorithm?

**Ans:** The subset construction algorithm is a method for converting an NFA to an equivalent DFA. It works by simulating the behavior of the NFA on all possible input strings, keeping track of the set of states that the NFA could be in after reading each input symbol. The resulting set of states corresponds to a single state in the DFA, and transitions in the DFA are defined based on the transitions between sets of states in the NFA.

## Q4: Are all languages recognizable by NFAs also recognizable by DFAs?

**Ans:** Yes, all languages that can be recognized by an NFA can also be recognized by a DFA, since every NFA can be converted to an equivalent DFA.

## Q5: Are all languages recognizable by DFAs also recognizable by NFAs?

**Ans:** Yes, all languages that can be recognized by a DFA can also be recognized by an NFA.

## Q6: Can an NFA recognize languages that a DFA cannot recognize?

**Ans:** No, an NFA cannot recognize languages that a DFA cannot recognize. Although an NFA can have more expressive power than a DFA in terms of the complexity of languages it can recognize, any language recognized by an NFA can also be recognized by a DFA.

## Q7: Can a DFA recognize languages that an NFA cannot recognize?

**Ans:** Yes, there are languages that can be recognized by a DFA but not by an NFA. One example of such a language is the language {0^n1^n | n >= 0} which is not recognized by any NFA, but can be recognized by a DFA.

## Q8: Can an NFA have fewer states than a DFA that recognizes the same language?

**Ans:** Yes, it is possible for an NFA to have fewer states than a DFA that recognizes the same language. This is because NFAs can use nondeterminism to explore multiple possible paths through the input, potentially reducing the number of states needed to recognize the language.