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.♦
- 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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
regular-languages × 1778formal-languages × 814
finite-automata × 529
regular-expressions × 395
automata × 365
pumping-lemma × 273
context-free × 224
closure-properties × 144
formal-grammars × 111
computability × 49
proof-techniques × 45
turing-machines × 37
complexity-theory × 36
pushdown-automata × 36
nondeterminism × 26
algorithms × 24
undecidability × 22
kleene-star × 18
strings × 15
decision-problem × 14
check-my-answer × 13
terminology × 12
reference-request × 12
parsers × 12
logic × 10