10 votes
Accepted

Is the language given by the regex (ab)* star-free?

No. $L=(ab)^*$ is star-free. A word is in $L$ iff It starts with $a$ (or is empty) It ends with $b$ (or is empty) It does not contain any consecutive $a$'s It does not contain any consecutive $b$'s ...
D.W.'s user avatar
  • 154k
2 votes

Why can't I prove that the regular language is closed under concatenation by this way?

Actually, that works if you add $\varepsilon$-transitions between final states of $M_1$ and the initial state of $M_2$. His argument of "maybe the cut of $w$ was wrong and you should have waited ...
Nathaniel's user avatar
  • 12.3k

Only top scored, non community-wiki answers of a minimum length are eligible