edited by
7,695 views
2 votes
2 votes

Given a Non-deterministic Finite Automaton (NFA) with states $\text{p}$ and $\text{r}$ as initial and final states respectively and transition table as given below $:$

$$\begin{array}{|l|l|l|l|} \hline \text{}  & \text{a} & \text{b} \\\hline \text{p} & \text{-} & \text{q} \\\hline \text{q} & \text{r} & \text{s} \\\hline \text{r} & \text{r} & \text{s} \\\hline \text{s} & \text{r}  & \text{s} \\\hline\end{array}$$

The minimum number of states required in Deterministic Finite Automaton (DFA) equivalent to NFA is

  1. $5$
  2. $4$
  3. $3$
  4. $2$
edited by

3 Answers

2 votes
2 votes

Given NFA

Required Dfa

Minimum number of states =4

Hence,Option(B)4.

edited by
2 votes
2 votes

Correct answer is (B) 4 states in mDFA.

Explanation already mentioned by other users. 

Extra:

The official answer key (C) 3 states is wrong. The following snapshot shows it why. 

The above example ignores the Dead state while constructing mDFA from DFA(Wrong approach because Dead states should always be included in the mDFA- either implicitly or explicitly)

Reference link 1 - Good reference

Reference link 2 - Good reference

Reference link 3 <- CAUTION - Avoid links like this, it contains incorrect information. 

edited by
0 votes
0 votes

Since The given Question is NFA because we don't know on state P on 'a' where to go i.e Not Deterministic therefore to make it a DFA we just need to add a DEAD STATE  and the resulting Finite automaton will be an DFA.

Answer Will be 5 states because the given question is similar to DFA but just for State P on 'a' we dont know where to go therefore in DFA we nedd to add a DEADSTATE and there result will generate the same Language.

Answer:

Related questions

6 votes
6 votes
2 answers
1
go_editor asked Jul 14, 2016
5,450 views
Given L1=L(a*baa*) L2=L(ab*). The regular expression corresponding to language L3=L1/L2 (right quotient) is given bya*ba*baa*a*ba*None of the above
1 votes
1 votes
1 answer
2
go_editor asked Jul 14, 2016
2,179 views
The $mv$ command changesthe inodethe inode-numberthe directory entryboth the directory entry and the inode
3 votes
3 votes
1 answer
4
go_editor asked Jul 14, 2016
4,039 views
A virtual memory based memory management algorithm partially swaps out a process. This is an example ofshort term schedulinglong term schedulingmedium term schedulingmutu...