# Kleene Star regex question, sed behavior? [closed]

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! • I'm voting to close this question as off-topic because it is about the behaviour of a Unix program, not about computer science. – David Richerby Jul 13 '19 at 9:00 ## 1 Answer $ 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.