GATE CSE 2016 | Set 2 | Question: 16

Question

The number of states in the minimum sized DFA that accepts the language defined by the regular expression.

$(0+1)^{*} (0+1) (0+1)^{*}$

is ________.

Comments

substring is length 1 

so, “  n+1 “ is a formula for substring mini DFA state

n+1=1+1= 2 Ans

Answer 1

All strings over $\{0,1\}$ having length $\geq 1$

$(0+1)^*(0+1)(0+1)^* = (0+1)(0+1)^*=(0+1)^*(0+1)= (0+1)^+$

Having DFA:

Number of states in minimal DFA $=2$.

Comments

sir make NFA and convert it into DFA is correct?

---

Yes.

---

@Praveen Sir How (0+1)^*(0+1)(0+1)^*=(0+1)(0+1)^* can be written?

---

$r^*rr^* =\{r,rr,rrr,rrrr,...\}=rr^* = r^*r$

---

@Praveen Saini sir

this is also possible, according to the above rule$?$

 

---

bro thats not DFA

---

@Vegeta

Now check,i edit it

---

bro still indeterministic

---

So, only $1$ minimized $DFA$ and $3$  $NFA$ is possible  for given a regular expression$?$

---

there could be many dfa but only one minimal, and there could be many nfa also

---

@Lakshman Patel RJIT

why second diagram is NFA?

---

$\Rightarrow$ Every DFA is always NFA.

https://www.quora.com/Is-every-DFA-a-NFA

https://cs.stackexchange.com/questions/18577/does-a-dfa-converted-from-nfa-always-contain-2q-states

---

@Praveen Saini sir, how is epsilon accepting in the dfa?

---

Epsilon does not belong to the our language.

---

Ohh, okay since it is a positive closure. Got it Thanks :)

Answer 2

simply convert NFA to DFA

Answer 3

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.

Answer 4

The given regular expression is  (0+1)*(0+1) (0+1)*

After applying R*. R*=R* it becomes (0+1)(0+1)*

in (0+1)(0+1)* there is atleast one appearance of (0+1) hence we can write it as (0+1)^+

A={0,1,00,01,10,11,000,001,011,........} if draw DFA we need atleast 2 states so the answer is 2.

Answer 5

The exression will give first NFA and then has to be converted to DFA