1 votes 1 votes No. of states in the DFA accepting the following set of strings are: ( ( aa* + φ* )* (aa* + φ* ) + bb* + φ* φ + φ* )* Quite confusing to me. Share your approach! Theory of Computation theory-of-computation minimal-state-automata finite-automata theory-of-computation- + – Prajwal Bhat asked Jan 17, 2017 Prajwal Bhat 1.3k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments focus _GATE commented Jan 17, 2017 reply Follow Share ( ( aa* + φ* )* (aa* + φ* ) + bb* + φ* φ + φ* )* ( aa* + φ* )* we know φ*=∈ so now it become ( aa* + ∈ )* =a* similarly we have ( bb* + φ* )*=b* so now it become ( ( a* )* (a*) + b* + φ* φ )* now we know ∅* =∈ ( ( a* )* (a*) + b* + ∈ φ)* ( ( a* )* (a*) + b* + ∈ φ )* ( ( a* )* (a*) + b* + ∈ φ )* so here ∈ φ= ∅ ( ( a* )* (a*) + b* +∅ )* ( a* + b* +∅ )* {minimal form of above question} 1 state is sufficient i think :) 1 votes 1 votes Sushant Gokhale commented Jan 17, 2017 reply Follow Share aa* + $\Phi$* = a+ + $\epsilon$ = a* bb* + $\Phi$*$\Phi$ + $\Phi$* = b+ + $\epsilon$$\Phi$ + $\epsilon$ = b+ + $\Phi$ + $\epsilon$ = b+ + $\epsilon$ = b* Thus, answer = (a*a* + b*)* = (a* + b*)* = (a+b)* So, 1 state should be sufficient 2 votes 2 votes Sushant Gokhale commented Jan 17, 2017 reply Follow Share @Kunal. If it accepts $\phi$, then 1 state isnt sufficient. 0 votes 0 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes ( ( aa* + φ* )* (aa* + φ* ) + bb* + φ* φ + φ* )* =((a+ + epsilon)* (a++epsilon) + b+ + epsilon)* =(a*a* + b*)* =(a*+b*)* =(a+b)* only 1 state needed sudsho answered Jan 17, 2017 selected Jan 17, 2017 by Sushant Gokhale sudsho comment Share Follow See all 0 reply Please log in or register to add a comment.