5,078 views
1 votes
1 votes
What is the minimum number of states in string ${(ab)}^{*}$?

How to approach this kind of problem?

1 Answer

Best answer
10 votes
10 votes

(I am assuming you are asking no of states in DFA). cheeky

The correct answer would be 3. Minimum number of states in FA will be 3.

To solve this kind of problem first generate the set from given regular expression.

${(ab)}^{*}$ = $\{ \epsilon, ab, abab, ababab, .... \} $

Now see, $\epsilon$ is present in the set then first state will be final state. Second is $(ab)$, if you create FA to accept this string then it will need 2 more states. After this, think of each and every states that what happens if there is an $(a||b)$ will arrive. Make transition for that. These transitions may leads to create some more states. But this is how you can solve this. 

selected by

Related questions

0 votes
0 votes
0 answers
1
techbrk3 asked Dec 20, 2017
573 views
L = (0*1 + 1+ 0)I got minimal DFA with 5 state only, but in their answer, they have mentioned with minimum 6 states.
5 votes
5 votes
3 answers
2
Manu Thakur asked Oct 9, 2017
2,125 views
I think, there will be 4 states in minimum DFA, following states will be merged in the resulted DFA{q0&q3}, {q4&q5}, {q1&q6}, {q2&q7}
4 votes
4 votes
3 answers
3
2 votes
2 votes
2 answers
4
Utk asked Jan 13, 2016
16,107 views
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$I draw the following DFA The minimum number of states is 4. The answer giv...