## DFA

Question 1 |

The minimum possible number of a deterministic finite automation that accepts the regular language *L = {w _{1}aw_{2} | w_{1}, w_{2} ∈ {a,b}*, |w_{1}| = 2,|w_{2}| ≥ 3}* is _________.

8 | |

9 | |

10 | |

11 |

Question 1 Explanation:

|w

So we have four possibilities of w

|w

w

So, the required DFA is

_{1}| = 2 means the length of w_{1}is two.So we have four possibilities of w

_{1}= {aa, ab, ba, bb}.|w

_{2}| ≥ 3 means the w_{2}will have at least three length string from {a,b}.w

_{2}will have {aaa, aab, aba, abb, baa, bab, bba, bbb, ……….}So, the required DFA is

Question 2 |

The number of states in the minimum sized DFA that accepts the language deﬁned by the regular expression

2 | |

3 | |

4 | |

5 |

Question 2 Explanation:

The regular expression generates the min string “0” or “1” and then any number of 0’s and 1’s .

So, the DFA has two states.

So, the DFA has two states.

Question 3 |

1 | |

2 | |

3 | |

4 |

Question 3 Explanation:

M accepts the strings which end with a and N accepts the strings which end with B. Their intersection should accept empty language.

Question 4 |

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________

3 | |

4 | |

5 | |

6 |

Question 4 Explanation:

No. of states in minimal DFA is 3.

Question 5 |

2 | |

3 | |

4 | |

5 |

Question 5 Explanation:

L = {aa, aaa, aaaaa, ...}

The minimum string length is 2 [aa], so we require 3 states to construct DFA.

The minimum string length is 2 [aa], so we require 3 states to construct DFA.

There are 5 questions to complete.