Allen Carrer Institute: TOC1

Question

How many no. of states in DFA for the following required expression? $(a + b + c) (a + b + c) (a + b + c) (a + b + c) ……… (n – 2)$ times $(a + b + c)^{+}$

$(1) $	$n – 1$
$(2) $	$n$
$(3) $	$n + 1$
$(4) $	$n + 2$

 Plz confirm me the answer . Is it $(n-1)$ or $n ?$

Comments

What is output of ur dfa??

for example

aaaa for 5 states

is it $\left ( n-2 \right )$ times $\left ( a+b+c \right )$??

or $\left ( n-1 \right )$ times $\left ( a+b+c \right )$??

---

aaaa

$\implies 3\; times\; a's.(a)=4 \;times\; a$

So it is n-2 times a. Followed by one more a from $(a+b+c)^+$

Yes it will be n-1 times a.

---

Ok..i got your point.

$R=(a+b+c)(a+b+c)\ldots (n-2)times. (a+b+c)^+$

$\because(a+b+c)^+=(a+b+c)(a+b+c)^*$

So we can write initial regexp as-

$R=(a+b+c)(a+b+c)\ldots (n-1)times.(a+b+c)^*$


$\implies n \; states$  required.