kleene star « Staffan Nöteberg's blog

Posts Tagged 'kleene star'

From Regular Expression to Finite Automaton

For each regular expression — and I mean the three operators and the six recursive rules style — there is a finite automaton that accepts exactly the same strings. Since this is not a university book in mathematics, I’ll show you an inductive reasoning about this and not a formal proof.

The hypothesis is thus that for an arbitrary regular expression p, we can create a finite automaton that has exactly one start state, no paths into the start state, no paths out from the acceptance state and that accepts exactly the same strings that are matched by p.

The empty string ε is a regular expression corresponding to a finite automaton with a start state, a path that accepts the empty string ε and leads from the start state to an acceptance state. We’ll call this an //ε-path//.
The empty set Ø is the set equivalent to a regular expression that can’t match any single string — not even the empty string ε. It is the same as a two-state automaton, with no single path. One state is start and the other one acceptance. But, they are not linked.
A regular expression that only matches the symbol b corresponds to a finite automaton with two states: start and acceptance. There’s a path from start t acceptance, and it only accepts the symbol b.

All three finite automata above have two states. One is start and the other one is acceptance. The difference is that the first one has an ε-path from start to acceptance, the second one has no path, and the third one has a b-path. Now we’ll continue. Imagine that we have two regular expressions p and q corresponding to finite automata s and t respectively.

Concatenation of two regular expressions p and q means that we first match a string with p, directly followed by a string that’s matched by q. To create this finite automaton we first add ε-paths from every acceptance state in s to the start state of t. Then we deprive all acceptance states in s their acceptance status and we’ll also withdraw the start status of the start state in t.
Alternation of two regular expressions p and q, i.e. p|q is like a finite automaton with a new start state that has ε-paths to all start staes of s and t. The new finite automaton also has a new acceptance state that is reached with ε-paths from all acceptance states of s and t. The start and acceptance states of s and t are thus not start and acceptance state in our new automaton.
Kleene star is the concatenation closure. Assume that p = q*. Then s is the finite automaton we get if we take t and add two states and four paths as follows: One new state is the start state and the other one is an acceptance state. All acceptance states of ´s´ loses that status in s, but instead gets an ε-path to the new acceptance state. We add two ε-paths from the new initial state — one to the old start state and one to the new acceptance state. In addition to that, we insert one ε-path from each of the old acceptance states to the old start state.

Look at the pictures above. Then take a deep breath and feel if you can translate an arbitrary regular expression to a finite automaton. Finally assess the last picture where the regular expression (w|bb)* is depicted as a graph using the method described above. Does it feel reasonable?

Simple Regular Expression Examples

Published 2012-01-25 Programming , Howto , Technology , Regex , Regular Expressions , Ruby , Regexp , Java , Python , C# , Scala , Javascript , PHP Leave a Comment
Tags: kleene star, concatenation, alternation

Now, we have three operators and a small framework. After all this theory, you might wonder if it’s possible for us to solve any problems. Yes, of course we can. Here are some examples:

All binary strings with no more than one zero:

'01101'.match /1*(0|)1*/ #=> #<MatchData "011">
'0111'.match /1*(0|)1*/ #=> #<MatchData "0111">
'1101'.match /1*(0|)1*/ #=> #<MatchData "1101">
'11010'.match /1*(0|)1*/ #=> #<MatchData "1101">

All binary strings with at least one pair of consecutive zeroes:

'101001'.match /(1|0)*00(1|0)*/ #=> #<MatchData "101001">
'10101'.match /(1|0)*00(1|0)*/ #=> nil
'1010100'.match /(1|0)*00(1|0)*/ #=> #<MatchData "1010100">

All binary strings that have no pair of consecutive zeros:

'1010100'.match /1*(011*)*(0|)/ #=> #<MatchData "101010">
'101001'.match /1*(011*)*(0|)/ #=> #<MatchData "1010">
'0010101'.match /1*(011*)*(0|)/ #=> #<MatchData "0">
'0110101'.match /1*(011*)*(0|)/ #=> #<MatchData "0110101">

All binary strings ending in 01:

'110101'.match /(0|1)*01/ #=> #<MatchData "110101">
'11010'.match /(0|1)*01/ #=> #<MatchData "1101">
'1'.match /(0|1)*01/ #=> nil
'01'.match /(0|1)*01/ #=> #<MatchData "01">

All binary strings not ending in 01:

'010'.match /(0|1)*(0|11)|1|0|/ #=> #<MatchData "010">
'011'.match /(0|1)*(0|11)|1|0|/ #=> #<MatchData "011">
''.match /(0|1)*(0|11)|1|0|/ #=> #<MatchData "">
'1'.match /(0|1)*(0|11)|1|0|/ #=> #<MatchData "1">
'01'.match /(0|1)*(0|11)|1|0|/ #=> #<MatchData "0">
'101'.match /(0|1)*(0|11)|1|0|/ #=> #<MatchData "10">

All binary strings that have every pair of consecutive zeroes before every pair of consecutive ones:

'0110101'.match /0*(100*)*1*(011*)*(0|)/ #=> #<MatchData "0110101">
'00101100'.match /0*(100*)*1*(011*)*(0|)/ #=> #<MatchData "0010110">
'11001011'.match /0*(100*)*1*(011*)*(0|)/ #=> #<MatchData "110">
'1100'.match /0*(100*)*1*(011*)*(0|)/ #=> #<MatchData "110">
'0011'.match /0*(100*)*1*(011*)*(0|)/ #=> #<MatchData "0011">

See if you can find even better regular expressions that solve these problems. Remember that there’re an infinite number of synonyms to each regular expression.

Regular Expression Precedence

Published 2012-01-24 Programming , Howto , Technology , Regex , Regular Expressions , Ruby , Regexp , Java , Python , C# , Scala , Javascript , PHP Leave a Comment
Tags: kleene star, concatenation, alternation, operator precedence, operator position, operator associativity

You might be tempted to read the following regular expression as third or fifth row:

'fifth row'.match /third|fifth row/ #=> #<MatchData "fifth row">
'third row'.match /third|fifth row/ #=> #<MatchData "third">

But unfortunately, as you can see, it’s more like either third (only) or else fifth row. This is due to something called order of operations or operator precedence. The invisible operator for concatenation has higher precedence than the alternation operator |.

To oil these wheels, we now add parentheses to our three operators. In a regular expression, the sub expression enclosed in parentheses get the highest priority:

'fifth row'.match /(third|fifth) row/ #=> #<MatchData "fifth row">
'third row'.match /(third|fifth) row/ #=> #<MatchData "third row">

Note that the parentheses are meta-characters, not literals. They won’t match anything in the subject string. And of course it’s possible to nest parentheses:

There are three things we need to remember, to know in what order and with what operands the regular expression engine will execute the operators:

Operator precedence is an ordered list that tells you if one operator should be executed before another operator in a regular expression. Several operators can have the same priority. In mathematics, the terms inside the parentheses have the highest priority. Multiplication and division have a lower priority. Addition and subtraction have the lowest. This is why 6+6/(2+1) = 8.
Operator position indicates where the operands are located in relation to the operator. The position can be prefix, infix, or postfix. If the operator is prefix, then the operand resides to the right of the operator, as the unary minus sign e.g. -3. An infix operator has an operand on each side, as in addition 1+2. A postfix operator stands to the right of its operand, as the exclamation point that represents the faculty operator in 5!.
Operator associativity tells us how to group two operators on the same precedence level. An infix operator can be right-associative, left-associative or non-associative. In mathematics, the infix operations addition and subtraction have the same precedence. Since both are left-associative the following equation holds: 1-2+3 = (1-2)+3 = 2. Prefix or postfix operators are either associative or non-associative. If they are associative, we start with the operator that is closest to the operand. An operator that is non-associative can’t compete with operators of same precedence.

Here goes the table for the operators we have studied so far. Later on, there’s a complete table of all regex operators.

Operator	Symbol	Precedence	Position	Associativity
Kleene star	`*`	1	Postfix	Associative
Concatenation	N/A	2	Infix	Left-associative
Alternation	`\|`	3	Infix	Left-associative

If you think this is hard to remember, then try to memorize the mnemonic SCA. It stands for Star-Concat-Alter, i.e. the order of precedence in regular expressions.

The Kleene Star operator

Published 2012-01-23 Programming , Howto , Technology , Regex , Regular Expressions , Ruby , Regexp , Java , Python , C# , Scala , Javascript , PHP Leave a Comment
Tags: kleene, kleene star, stephen kleene

All finite languages can be described by regular expressions. You can simply list the strings as an alternation string1|string2|string3 etc. But there are also some languages with an infinite number of strings that can be described by regular expressions. To achieve that, we use an operator we call Kleene star after the American mathematician Stephen Cole Kleene. If p is a regular expression, then p* is the smallest superset of p that contains ε (the empty string) and is closed under the concatenation operation. It is the set of finite length strings that can be created by concatenating strings that match the expression p. If p can match any other string than ε, then p* will match an infinite number of possible strings.

The real name of the typographic symbol (glyph) used to denote the Kleene Star is asterisk. It’s a Greek (not geek) word and it logically enough means little star. Normally, it has five or six arms, but in its original purpose — to describe birth dates in a family tree — it had seven arms. This is a very popular symbol. In Unicode, there are a score of different variants and many communities have chosen their own meaning of the asterisk. In typography it means a footnote. In musical notation, it may mean that the sustain pedal of the piano should be lifted. On our cell phones, we use the asterisk to navigate menus in touch-tone systems. So there is no world-wide interpretation of *. However, in this book it’ll always mean the operator Kleene star.

Do you want to see a simple example? The concatenation closure of one single symbol, such as a, is a* = { ε, a, aa, aaa,... }. Want to see a more academic example? The concatenation closure of the set consisting solely of the empty string ε is — well, the set consisting solely of the empty string ε* = ε. Want to see a more complicated example? (1|0)* = { ε, 0, 1, 01, 10, 001, 010, 011,... }. It may thus be different matches of the expression that concatenates. Can you write a regular expression that matches all binary strings that contain at least one zero? Or all binary strings with an even number of ones?

The operator Kleene star — pronounced /ˈkleɪniː stɑ:r/ klay-nee star — is unary, i.e. it only takes one operand. The operand is the regular expression to the left, which allows us to say that it’s a postfix operator. It has the highest priority of all operators and it is associative. The latter means that if two operators of the same priority are competing, then the operator closest to the operand wins. Since p** = p*, we say that the Kleene star is idempotent. And I want to emphasize again that p* = (p|)*, i.e. the empty string ε is always present in a closure. We’ll later on see that there is a very common — and none the less disastrous — mistake to forget this very fact.

Here are some possible answers to two the questions above:

The positive closure operator + and the at least n operator {n,} are abstractions for expressing infinite concatenation. We’ll soon explore them in more detail.

Regex at Windows’ command line

Published 2010-12-2 Howto , Regex , Regular Expressions 2 Comments
Tags: egrep, findstr, kleene, kleene star, windows

Regular Expressions are patterns that match strings in text files or text streams. All strings that can possibly be matched by a particular expression are collectively a regular language. Every regular language has at least one corresponding finite automaton. The finite automaton is a very simple state machine.

In order to match regular languages we need only three operations – Les trois Mousqetaires de Regex:

Kleene star, i.e * – repeat the preceding pattern zero or more times
Concatenation – match two consecutive patterns, e.g. 73 match 7 followed by 3
Alternation – match exactly one out of a list of patterns, i.e. logical OR

The precedence is as the list above. Sometimes, that’s not enough and thus we also need D’Artagnan, the fourth musketeer. I’m talking about parenthesis for grouping – just like in any other programming language.

The unix command-line tool egrep meets the regular expressions litmus test. It supports concatenation, Kleene star, alternation, and grouping.

What about Windows then?

There’s a built-in command-line tool in Windows called findstr. And findstr supports Kleene star and concatenation. That’s 2/4 of the mandatory operations we need to match regular languages. Unlike egrep, it lacks alternation and forced precedence with parenthesis – and thus you can’t use findstr for regular expressions.

What to do then if you want to write regular expressions at the command line in Windows? There are at least two alternatives:

UnxUtils are native Win32 ports of common GNU utilities. Native means that the executables only depend on the Microsoft C-runtime (msvcrt.dll) and not an emulation layer. One of the executables is egrep.
Cygwin is a Linux API emulation layer and a vast number of tools – among them egrep.

D’Artagnan and his three musketeer friends Athos, Porthos, and Aramis lived by the motto tous pour un, un pour tous. If you don’t have grouping and the three mandatory operations, then you can’t write regular expressions.

Staffan Nöteberg's blog

Posts Tagged 'kleene star'

From Regular Expression to Finite Automaton

Simple Regular Expression Examples

Regular Expression Precedence

The Kleene Star operator

Regex at Windows’ command line

Recent Posts

Most popular

Links

RSS feed

Staffan's just-read

Twitter feed

Follow “Staffan Nöteberg's blog”