Shell Programming and Scripting

I also tried python 2.5.2 for (a*)(b*|(ab)*) and it was aab, same as perl.
Actually aa-b was I expected and I don't understand why tcl/awk/sed will get a-abab.

Any idea ?

Yes,
read about Regex Engine Types.
Observe the differences between GNU sed and super sed:

Code:

% sed -r 's/(a*)(b*|(ab)*)/-->\1<-- -->\2<--/'<<<aabab  
-->a<-- -->abab<--

% ssed -r 's/(a*)(b*|(ab)*)/-->\1<-- -->\2<--/'<<<aabab
-->aa<-- -->b<--ab

NFA and DFA:

Code:

% sed -r 's/(nfa|nfa not)/-->\1<--/'<<<'nfa not'      
-->nfa not<--

% ssed -r 's/(nfa|nfa not)/-->\1<--/'<<<'nfa not'  
-->nfa<-- not

Thanks for pointing out NFA & DFA difference. I document what I learn here in case someone out there is as boring as I am.
So NFA is straightforward. It tries the patterns in question one by one. In the (a*)(b*|(ab)*) against aabab case, NFA first tries a*, then (b*|(ab)*). And when it comes to alternation, traditional NFA engine chooses the ordered one but not the greedy one. So in the case (nfa|nfa not) against "nfa not", it chooses nfa. So (a*)(b*|(ab)*) against aabab is aab

DFA is some what counterintuitive. It scans the string to rule out the patterns in question and if there exists multi-matches, DFA finds the longest possible match (for alternation, DFA is greedy not ordered). Take the (a*)(b*|(ab)*) against aabab case for instance, starting from aa, there exists 2 possible matches, aa-b and a-abab. So it chooses a-abab.

And I think the case (a*)((b|ab)*)against aabab is a more interesting case now. Because both aa-bab and a-abab match aabab and they are the same length. So why choose aa-bab over a-abab ? I still don't have a clear answer for it.