#Union concatenation kleene star order plus

matches any single character that is not a lowercase letter from 'a' to 'z'. For example, matches any character other than 'a', 'b', or 'c'. Matches a single character that is not contained within the brackets. These forms can be mixed: matches 'a', 'b', 'c', 'x', 'y', or 'z', as does. specifies a range which matches any lowercase letter from 'a' to 'z'. This includes 'ab', 'acb', or 'a123456789b'.Ī bracket expression matches a single character that is contained within the brackets. Therefore, a.*b matches any string that contains an 'a' and a 'b' with 0 or more characters in between. For example, a.b matches any string that contains an 'a', then any other character, and then a 'b' such as 'a7b', 'a&b', or 'arb', but not 'abbb'. For example, ab+c matches 'abc', 'abbc', 'abbbc', and so on, but not 'ac'.

#Union concatenation kleene star order plus

The plus sign indicates one or more occurrences of the preceding element. For example, colou?r matches both 'color' and 'colour'. The question mark indicates zero or one occurrences of the preceding element.

For example, ab*c matches 'ac', 'abc', 'abbc', 'abbbc', and so on. For example, gray|grey can match 'gray' or 'grey'.Īs described above, the asterisk indicates zero or more occurrences of the preceding element. They are pretty universal across allĪs described above, a vertical bar separates alternatives.

Here are the additional syntax rules that we will use. Interactive websites for testing regexes are a useful resource forĪ very nice exposition is Pattern Matching with Regular Expressionsįrom the Automate the Boring Stuff book and online course.

Implementation, programming language, or library in use. Unfortunately, the specific syntax rules vary depending on the specific All modern programming languages have regular expression libraries. Programmers use Regular Expressions (usually referred to as regex) extensively forĮxpressing patterns to search for. A 'most simplified' Regular Expression or FSA is not always well defined. For a given FSA or Regular Expression, there are many others which are equivalent to it. Conversely, if we have an FSA, we can mechanically develop a Regular Expression which will describe the strings which can be parsed by the FSA. If we have a Regular Expression, then we can mechanically build an FSA to accept the strings which are generated by the Regular Expression. 'd(ca)*b' generates strings db, dcab, dcacab, dcacacab, and so on. Similar to standard Algebra, parentheses can be used to group sub-expressions.įor example, 'dca*b' generates strings dcb, dcab, dcaab, and so on, whereas The order of precedence for Regular Expression operators is: Kleene Star, concatenation, and then union. if a and b are both REs, then so are the strings built up using the following rules:Ī. If the string a is in the input alphabet, then it is a RE. The rules for forming a Regular Expression (RE) are as follows:ġ. For example, the regular expression corresponding to the first FSA given above is xx*yy*. The FSA above will accept strings composed of one or more x’s followed by one or more y’s (e.g., xy, xxy, xxxyy, xyyy, xxyyyy).Ī Regular Expression (RE) is an algebraic representation of an FSA. In State C, seeing any additional letter y will keep the machine in state C. State C is a final state so if the string being parsed is completed and the FSA is in State C, the input string is said to be accepted by the FSA. Once in state B, there are two transition rules: seeing the letter y will cause the FSA to make C the active state, and seeing an x will keep B as the active state. The only way to go from state A to B is by seeing the letter x. The initial state is A the final state is C. In the above FSA, there are three states: A, B, and C. Here is a drawing of an FSA that is used to parse strings consisting of x's and y's: