Assaf Gordon wrote:
> The immediate cause is somewhere in gnulib's DFA module.

The bug was introduced in Gnulib, in commit 
403adf1b40897ba108075008c10bd38d937e1539 dated 2016-11-25 and labeled "dfa: 
addition of new state on demand". It's not a bug that grep runs into, since grep 
doesn't use the newline transition that sed does. I installed the attached patch 
to fix the Gnulib bug. I'll leave Bug#25390 open, as I assume you'll want to 
check it for 'sed' and add a test case for 'sed'.