1
$\begingroup$

Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b*". Does anyone know why this regex is not being matched against the pattern space?

This is the failure case:

$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

SOLUTION 'b*' expects 0 or more occurrences of 'b'. If 0 occurrences of 'b' the empty string $\epsilon$ is expected. In the string above, 'ab' is preceded by the empty string and it is matched in the beginning of "ab" pattern space as follows:

printf "ab\n" | sed -En 's/b*/x/ p' | od -t c
0000000   x   a   b  \n

where 'x' is substituted for empty string.

In order to match b, I had to use the following form:

Kleene Plus in addition to Kleene Star as follows:

 printf "ab\n" | sed -En 's/(.*)(b+)(.*)/\1/ p' | od -t a
0000000   a  nl

This case, without Kleene Star, behaves as expected:

$ printf "ab\n" | sed -En 's/b// p' | od -t c
0000000   a  \n
0000002

I'm trying to match the 'b' and replace it with nothing.

The pattern space is 'ab', beginning of line is unspecified, so I'm confused why /b*/ would not match a pattern of zero or more 'b's, in this case 'b'.

Oddly, this case works with the '.' prepended to the '*':

# fails to match
$ printf "abb\n" | sed -En 's/b*// p' | od -t c
0000000   a   b   b  \n
0000004
# matches with .* !
$ printf "abb\n" | sed -En 's/b.*// p' | od -t c
0000000   a  \n
0000002

Kleene Star matches zero or more occurrences of the preceding alphabet (in this case a single character).

By definition:

$V^0 = \{\epsilon\}$

$V^1 = V$

$\forall i ( (i \gt 0) \land (V^{i + 1} = \{ wv : w \in V^i \land v \in V )\} $

Therefore $V^0 = \{ \epsilon\}$, $V^1 = \{ \epsilon \cdot b\}$, $V^2 = \{ \epsilon \cdot b \cdot b\}$.

$V^* = \bigcup\limits_{i\ge0} V^i = V^0 \cup V^1 \cup ...$ which I have specified by /b*/.

The following cases agree with my understanding of sed and Kleene Star:

# * : matches 0 or more occurances
# no match
$ printf "a\n" | sed -En 's/b*// p' | od -t c
0000000   a  \n
0000002

# match a
printf "a\n" | sed -En 's/a*// p' | od -t c
0000000  \n
0000001

# match a
printf "ab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

# match aa
printf "aab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

I tested using BSD and GNU sed, both have the same results.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is about the behaviour of a Unix program, not about computer science. $\endgroup$ – David Richerby Jul 13 at 9:00
1
$\begingroup$
$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

This regex expression "$b*$" does match the empty string, which is zero '$b$', at the very front of the input "$ab$". This is in accordance with the definition of Kleene star since $b^*$ stands for the language $\{\epsilon, b, bb, \cdots\}$, where $\epsilon$ stands for the empty string. The matched part, an empty substring is replaced by the empty string. So, the same input string "$ab$" is printed with the newline attached.

Note that sed tries to find a match as early as possible. Although the substring "$b$" of "$ab$" matches "$b*$" more, it is ignored by sed completely since it happens later than the match said above.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.