Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# TOC-grand test Q4

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

What is the smallest possible number of states needed in constructing DFA for the language $\small \Sigma^*1(\Sigma\Sigma^*)1\Sigma^*$ , where $\small \Sigma = \{0,1\}$. ?

reshown Sep 8, 2019

The following DFA with four states recognizes L=Σ*1(ΣΣ*)1Σ*

By the Myhill–Nerode theorem, no smaller DFA exists because each of the four strings "epsilon,1,10,11" is in a different equivalence class of L. Their distinguishing suffixes are as follows:

answered Sep 11, 2019 by (91,540 points)

ANS . 4

Expression will become -  (0+1)* 1 (0+1)^+  1  (0+1)*

Langauges = { 101, 111............}

Min. DFA will contain 4 states.

answered Sep 8, 2019 by (14,660 points)
may be 3 states