FSAs and Regular Expressions
Finite state automata, the regular expressions that describe them, and pattern matching.
Overview
A Finite State Automaton (FSA) is a simple model of a machine. It has a finite number of states, exactly one of which is active at any moment; a set of transition rules that move the machine from one state to another when it reads an input symbol; one initial state; and one or more final (accepting) states.
In ACSL, FSAs are used to parse strings: the machine reads the string one character at a time, following the transitions, and the string is accepted if the machine finishes in a final state. If at any point there is no transition for the character being read, or the machine ends somewhere other than a final state, the string is rejected.
A Regular Expression (RE) is an algebraic way of writing the same thing: a compact pattern that describes exactly the set of strings an FSA accepts. Every FSA has an equivalent RE and every RE has an equivalent FSA.
Key Concepts:
- Drawing conventions: states are circles, the final state is a double circle, the start state has an incoming arrow from nowhere, and transitions are labelled arrows.
- The three RE operators are concatenation, union (
Uor|) and the Kleene star (*). - Typical questions: convert an FSA to an RE, simplify an RE, pick equivalent REs, or decide which strings a pattern matches.
Key Concepts
Reading an FSA
This FSA has three states. A is the initial state and C is the final state. Reading an x in state A moves to B. In B, an x stays in B and a y moves to C. In C, a y stays in C. So the machine accepts one or more x's followed by one or more y's: xy, xxy, xxxyy, xyyy and so on, but not yx, x, or xyx. The equivalent regular expression is xx*yy*.
Rules for Building Regular Expressions
- The null string, written λ, is an RE.
- Any single symbol of the alphabet is an RE.
- If a and b are REs, so are:
- Concatenation
ab: a followed by b. - Union
a U b(also writtena|b): a or b. - Kleene star
a*: a repeated zero or more times.
- Concatenation
Precedence
Kleene star binds tightest, then concatenation, then union. Parentheses group sub-expressions. So dca*b generates dcb, dcab, dcaab, ..., while d(ca)*b generates db, dcab, dcacab, ...
Regular Expression Identities
These identities let you simplify an RE or recognise that two REs are equivalent.
1. (a*)* = a*
2. aa* = a*a
3. aa* U λ = a*
4. a(b U c) = ab U ac
5. a(ba)* = (ab)*a
6. (a U b)* = (a* U b*)*
7. (a U b)* = (a*b*)*
8. (a U b)* = a*(ba*)*
Regex in Practice
Programmers use regular expressions ("regex") constantly to describe search patterns. Every modern language has a regex library. The exact syntax varies slightly between tools, but ACSL uses the following additions, which are nearly universal:
| Pattern | Meaning | Example |
|---|---|---|
| | Alternatives (union) | gray|grey matches gray or grey |
* | Zero or more of the preceding element | ab*c matches ac, abc, abbc, ... |
? | Zero or one of the preceding element | colou?r matches color and colour |
+ | One or more of the preceding element | ab+c matches abc, abbc, ... but not ac |
. | Any single character | a.b matches a7b, a&b, arb; a.*b matches ab, acb, a123b |
[ ] | One character from the set; ranges allowed | [abc], [a-z], [a-cx-z] |
[^ ] | One character not in the set | [^abc] matches any character except a, b or c |
( ) | Grouping | H(ä|ae?)ndel matches Handel, Händel, Haendel |
Examples
An FSA has states A (start), B and C (final). Transitions: A goes to B on 0; B loops to itself on 1; B goes to C on 0; C goes to a further final state D on 1.
Follow the only route from start to finish and write down what is read: a 0, then any number of 1's (the loop), then a 0, then a 1.
Regular expression: 01*01
Candidates: (A) 0000001111111, (B) 1010101010, (C) 1111111, (D) 0110, (E) 10.
- The union has two halves.
00*1*1means one or more 0's followed by one or more 1's: 01, 001, 0001111, ... 11*0*0means one or more 1's followed by one or more 0's: 10, 1110, 1111100, ...- A is all 0's then all 1's, so it matches the first half. E is 10, which matches the second half.
- B alternates, C has no 0, and D switches direction twice, so none of them match.
Accepted: A and E
Candidates: 1. ABCD8, 2. abcd5, 3. ABcd9, 4. AbCd7, 5. X, 6. abCD7, 7. DCCBBBaaaa5.
The pattern is: zero or more uppercase A-D, then zero or more lowercase a-d, then exactly one digit. Once you have started the lowercase part you cannot go back to uppercase (that rules out 4 and 6), and the string must end with a digit (rules out 5).
Matches: 1, 2, 3 and 7
Candidates: 1. Highb, 2. HiiighS, 3. HigghhhC, 4. Hih, 5. Hghe, 6. Highd, 7. HgggggghX.
H, then an optional single i, then one or more g's, then one or more h's, then one character that is not a, b, c, e, i, o or u. String 1 ends in b (excluded); 2 has three i's; 4 has no g; 5 ends in e (excluded).
Matches: 3, 6 and 7
Practice Problems
For "which strings" questions, enter the matching numbers separated by commas, for example 1,3,5.
Problem 1 Junior
Which of the following strings are accepted by the regular expression ab*a?
- aa
- aba
- abba
- ab
- baa
Solution
ab*a is an a, then zero or more b's, then an a. Every accepted string starts and ends with a and has only b's in between.
- aa: zero b's. Accepted.
- aba: one b. Accepted.
- abba: two b's. Accepted.
- ab: does not end with a. Rejected.
- baa: does not start with a. Rejected.
Accepted: 1, 2, 3
Problem 2 Junior
Which of the following strings match the pattern [A-C]+[0-9]?x?
- ABx
- A9x
- x
- AB99x
- C0x
- abx
Solution
The pattern is one or more uppercase letters from A to C, then at most one digit, then a lowercase x.
- ABx: two letters, no digit, x. Matches.
- A9x: one letter, one digit, x. Matches.
- x: needs at least one letter first. No match.
- AB99x: two digits, but
?allows at most one. No match. - C0x: one letter, one digit, x. Matches.
- abx: lowercase letters are not in [A-C]. No match.
Matches: 1, 2, 5
Problem 3 Intermediate
Write the simplified regular expression for the FSA described by this transition table. A is the start state and C is the only final state.
| From | Reads | To |
|---|---|---|
| A | 0 | B |
| B | 1 | B |
| B | 0 | C |
| C | 1 | C |
Solution
Trace the path from the start state to the final state and turn each loop into a Kleene star.
- Leaving A requires a 0.
- In B the machine may read any number of 1's (the B-to-B loop):
1*. - Leaving B for C requires a 0.
- In C the machine may read any number of 1's before the string ends:
1*.
Putting the pieces together gives 01*01*. Example accepted strings: 00, 0100, 0011, 011011.
Regular expression: 01*01*
Problem 4 Intermediate
Which of the following strings are accepted by the regular expression 0(10)*1 U 11*0?
- 01
- 0101
- 01011
- 110
- 10
- 1110
- 00
Solution
Union has the lowest precedence, so this is either 0(10)*1 or 11*0.
0(10)*1: a 0, then zero or more copies of "10", then a 1. Generates 01, 0101, 010101, ...11*0: one or more 1's then a single 0. Generates 10, 110, 1110, ...
- 01: first half with zero repeats. Accepted.
- 0101: 0, "10", 1. Accepted.
- 01011: after 0101 there is an extra 1 that nothing can absorb. Rejected.
- 110: second half. Accepted.
- 10: second half with zero extra 1's. Accepted.
- 1110: second half. Accepted.
- 00: neither half allows two 0's in a row. Rejected.
Accepted: 1, 2, 4, 5, 6
Problem 5 Senior
Which of the following strings match the pattern (ab|ba)+c?[^xyz]. exactly (the whole string must be consumed)?
- abcq1
- babab
- abbac5!
- ababcx9
- bad_
- abc
Solution
Break the pattern into pieces: one or more blocks that are either "ab" or "ba"; an optional c; one character that is not x, y or z; then exactly one more character of any kind. After the blocks there must be exactly two or three characters left.
- abcq1: block "ab", then c, then q (allowed), then 1. Matches.
- babab: "ba" + "ba" leaves only "b", but two characters are required. Using just one block "ba" leaves "bab", which would need c? to be absent, b for [^xyz], a for ., and then an extra b remains. No match.
- abbac5!: "ab" + "ba", then c, then 5, then !. Matches.
- ababcx9: "ab" + "ab", then c, then x, but x is excluded by [^xyz]. Skipping the c instead gives c for [^xyz] and x for ., leaving 9 unmatched. No match.
- bad_: block "ba", no c, d for [^xyz], _ for the dot. Matches.
- abc: block "ab", then only one character remains, but at least two are needed. No match.
Matches: 1, 3, 5