number of states required to construct dfa accepting language L = (ab+aba)*

Question

number of states required to construct dfa accepting languages  L = (ab union aba)* alphabet = {a,b} is atleast??

my view:

for intersection of 2 reg langs we take cartesian product construct dfa then we mininise it ... for union of lang containing same symbols like (111+11)*we can enumerate and produce least no.for required states but for above question like (ab+aba)* what should i do to solve ?

Answer 1

Instead of any confusion,  it is better to design NFA for given regular expression and convert it to DFA. 

[ note : any one can design DFA directly depending on practice/aptitude] 

Comments

that may get wrong sometime , so i think its better to construct nfa then dfa ,even it is time consuming i ll go for it

Answer 2

Can you make a NFA for it? Something like this: 

If you can do that, you can simply convert it to DFA and minimize the DFA to get this: 

And thus get the answer: minimal states = 5

Comments

does nfa is correct ? y epsilon productions?

how to draw epsilon - nfa  by seeing regular exp?

---

Yes, there is a standard, easy to follow and pretty straight forward algorithm for it. See: Converting a regular expression to a NFA - Thompson's Algorithm. You might also wanna read this algorithm from a standard book.

This online tool will help you see it in action: http://hackingoff.com/compilers/regular-expression-to-nfa-dfa

---

Pragy: Thanks for online link.