4. More on FSAs: Limitations and closure properties
1 Interchangeable subexpressions
Now forget about FSAs for a moment, and just consider sets of strings “out of the blue”. We’ll connect things back to FSAs shortly, in section 2.
(1) Given some stringset L ⊆ Σ∗, the L-remainders of a string u are all the strings v such that uv ∈ L. I’ll write remL(u) for the set of L-remainders of u, so we can write this definition in symbols as: remL(u) = {v | v ∈ Σ∗,uv ∈ L}.
This definition may seem unfamiliar and a bit awkward, but the underlying idea is quite simple and very powerful — you will probably recognize that it’s been hiding somewhere inside your existing understanding of how grammars (of any sort!) work. Roughly, remL(u) gives us a handle on “all the things we’re still allowed to do, if we’ve done u so far”. Some examples will clarify.
(2) If L1 = {cat, cap, cape, cut, cup, dog}, then: a. remL1(ca)={t,p,pe}
b. remL1(c)={at,ap,ape,ut,up}
c. remL1(cap)={ε,e}
d. remL1(d)={og}
(3) If L2 = {ad, add, baa, bad, cab, cad, dab, dad}, then:
a. remL2(c)=remL2(d)={ab,ad} b. remL2(a)={d,dd}
c. remL2(da)={b,d}
d. remL2(ad)={ε,d}
When we notice that remL2(c) = remL2(d), this tells us something useful about how we can go about designing a grammar to generate the stringset L2: such a grammar doesn’t need to care about the distinction between starting with ‘c’ and starting with ‘d’, because for any string v that you choose, cv and dv will either both be in L2 or both not be in L2. An initial ‘c’ and an initial ‘d’ are interchangeable subexpressions.
(4) Given a stringset L ⊆ Σ∗ and two strings u ∈ Σ∗ and v ∈ Σ∗, we define a relation ≡L such that: u ≡L v iff remL(u) = remL(v).
Some slightly more linguistics-ish examples:
(5) Suppose that Σ = {C, V}, and L is the subset of Σ∗ containing all strings that contain at least one ‘V’. Then:
a. C ≡L CC, because both can only be followed by strings that fulfill the requirement for a ‘V’. b. VC ≡L CV, because both can be followed by anything at all.
c. So two strings are L-equivalent iff they either both do or both don’t contain a ‘V’.
Ling185A, Winter 2021 — Tim Hunter, UCLA
(6) Suppose that Σ = {C, V}, and L is the subset of Σ∗ containing all strings that have two adjacent ‘C’s or two adjacent ‘V’s (or both). Then
a. C ≡L CVC ≡L CVCVC, because these all require remainders that have two adjacent ‘C’s or two adjacent ‘V’s or an initial ‘C’.
b. V ≡L VCV ≡L VCVCV, because these all require remainders that have two adjacent ‘C’s or two adjacent ‘V’s or an initial ‘V’.
c. CC ≡L VCVCVVCVC
(7) Suppose that Σ = {C,V}, and L is the subset of Σ∗ containing all strings that do not have two adjacent occurrences of ‘V’. Then:
a. CCCC ≡L VC, because both can be followed by anything without adjacent ‘V’s.
b. CCV ≡L V, because both can be followed by anything without adjacent ‘V’s that does not begin
with ‘V’.
c. CCV ̸≡L CCC, because only the latter can be followed by ‘VC’.
d. In fact: two strings are L-equivalent iff they end with the same symbol!
(8) Suppose that Σ is the set of English words, and L is the set of all grammatical English word- sequences. Then (probably?):
a. John ≡L the brown furry rabbit b. John ≡L Mary thinks that John c. John ̸≡L the fact that John
2 The Myhill-Nerode Theorem
We can connect this idea of equivalent subexpressions back to forward values in an FSA. Recall that fwdM(u)(q) is a boolean, true or false; so we can think of fwdM(u) as a set of states, namely all those states reachable from an initial state of M by taking transitions that produce the string u. I’ll sometimes call this a forward set (for lack of a better name).
Now here’s the important connection:
(9) For any FSA M = (Q,Σ,I,F,∆) and for any two strings u ∈ Σ∗ and v ∈ Σ∗, if fwdM(u) = fwdM(v)
then u ≡L(M) v.
Given any particular stringset L, we can think of the relation ≡L as sorting out all possible strings into buckets (or “equivalence classes”): two strings belong in the same bucket iff they are equivalent prefixes. So what (9) says is that for an FSA to generate L it must be arranged so that fwd only maps two strings to the same state-sets if those two strings are equivalent prefixes; the machine can ignore distinctions between bucket-mates, but only between bucket-mates.
This idea of ignoring at least some distinctions is exactly what makes a grammar different from a list of strings. The challenge in writing grammars is always about ignoring the “irrelevant” distinctions in order to allow creativity, while tracking the “relevant” distinctions.1
And now we can put our finger on the capacities/limitations of finite-state automata.
(10) The Myhill-Nerode Theorem: Given a particular stringset L, there is an FSA that gen- erates L iff the relation ≡L sorts strings into only finitely-many buckets.
Why is this, exactly?
1McCulloch & Pitts (1943, pp.130–131) put this nicely in their classic paper (you should go and read it!): “our knowledge of the world including ourselves, is incomplete . . . This ignorance, implicit in all our brains, is the counterpart of abstraction which renders our knowledge useful.” See also chapters 2–4 of Minsky’s book Computation: Finite and Infinite Machines (1967) for good discussion of this very general point.
Ling185A, Winter 2021 — Tim Hunter, UCLA
2.1 Why do FSAs make only finitely-many distinctions?
Well, if we have a particular FSA whose set of states is Q, then there are only finitely many distinct subsets of Q that fwdM can map strings to; specifically, there are 2|Q| of them. So there are only finitely-many “candidate forward sets”, meaning that the FSA is necessarily making only those finitely-many distinctions.
Having noticed this, it’s very easy to convince ourselves that no FSA can generate the stringset L = {anbn | n > 0}. Notice that a ̸≡L aa, and aa ̸≡L aaa, and so on. In fact any string of ‘a’s is non-equivalent to each of the different-length strings of ‘a’s, so this stringset sorts strings into infinitely-many buckets, one bucket for each length. There is no way for an FSA M to be set up such that fwdM(aj) ̸= fwdM(ak) whenever j ̸= k; any FSA will incorrectly collapse the distinction between two such strings of ‘a’s.
2.2 Why can any finitely-many distinctions be captured with an FSA?
On the other hand, if we have a particular stringset L whose equivalence relation ≡L makes only finitely- many distinctions, then there is a straightforward way to construct a minimal FSA whose states track exactly those distinctions.
Consider again the stringset from (6), consisting of all strings with either two adjacent ‘C’s or two adjacent ‘V’s (or both). This stringset’s equivalence relation sorts strings into four buckets:
(11) a. a bucket containing strings that have either two adjacent ‘C’s or two adjacent ‘V’s; b. a bucket containing strings that don’t have two adjacent ‘C’s or ‘V’s, but end in ‘C’; c. a bucket containing strings that don’t have two adjacent ‘C’s or ‘V’s, but end in ‘V’; d. a bucket containing only the empty string.
Having noticed this we can mechanically construct an appropriate FSA — known as the minimal FSA for this stringset — which has one state corresponding to each bucket. The crucial idea here is that if u ≡L v, then ux ≡L vx for any x ∈ Σ, i.e. adding a symbol at the end can’t “break” an equivalence; and similarly, for any FSA M , if fwdM (u) = fwdM (v) then fwdM (ux) = fwdM (vx).
(12)
(11d)
(11b) CC
C V VV
(11c)
C
(11a)
V
This strategy produces a specific kind of automaton, a deterministic automaton. In a deterministic au- tomaton, there are never two arcs leading out of the same state that are labeled with the same symbol; each string corresponds to at most one path through the states, and so fwd only ever produces singleton sets or the empty set.
2.3 One loose end: determinization and minimization
Any FSA M can be converted into an equivalent deterministic one M′, by setting up the states of M′ to correspond to sets of the states of M. Then, for any string u, the one state in fwdM′(u) will be the one corresponding to the set fwdM(u). Working out the transitions of the new automaton M′ for a symbol x amounts to working out how to calculate fwdM (ux) from fwdM (u), which we saw last week.
Applying this procedure to the FSA in (13), which generates the stringset in (6), produces the new FSA in (14).
Ling185A, Winter 2021 — Tim Hunter, UCLA
41
CC CC
(13)
40
43
VV
VV 42
{40,41} C
{40,41,43} C
C
(14)
{40} CV CV V
{40,42} V {40,42,43} V
To see the connection, here’s the table of forward values for the string ‘CVCCV’ using the FSA in (13).
(15) State C V C C V
40 111111 41 010110 42 001001 43 000011
It turns out that the two states {40, 41, 43} and {40, 42, 43} in (14) “do the same thing”: in either case, it’s possible to end, it’s possible to transition to state {40, 41, 43} on a ‘C’, and it’s possible to transition to state {40, 42, 43} on a ‘V’ (and that’s all). Collapsing these two states will produce the minimal FSA in (12).
3 Intersection of FSAs
The stringsets generated by FSAs are closed under intersection. This means that, if there is an FSA that generates the stringset L and there is an FSA that generates L′, then there is also an FSA that generates the stringset L ∩ L′. In other words, intersecting two FSA-describable stringsets will never produce a non-FSA-describable stringset.
One way to convince ourselves of this is to see that, given any two FSAs, we can construct a third FSA that generates the intersection of the original two FSAs’ stringsets. The important ideas here will be that:
(16) the states of the new FSA are pairs, consisting of a state from the first FSA and a state from the second; and
(17) each transition emitting a symbol x in the new FSA must connect two states which
• have as their first components states connected by an x-emitting transition in the first FSA,
and
Ling185A, Winter 2021 — Tim Hunter, UCLA
• have as their second components states connected by an x-emitting transition in the second FSA.
The new FSA will “simulate” the workings of both of the two original FSAs simultaneously. Here’s the picture to have in mind:
M
(18)
M′
Here’s the general “recipe”:
(19)
4
(20)
Given two FSAs M = (Q,Σ,I,F,∆) and M′ = (Q′,Σ,I′,F′,∆′), the FSA M′′ = (Q × Q′,Σ,I × I′,F ×F′,∆′′) will generate L(M)∩L(M′), where the new transition set ∆′′ is defined by:
• (⟨q1,q1′ ⟩,x,⟨q2,q2′ ⟩) ∈ ∆′′ iff both (q1,x,q2) ∈ ∆ and (q1′ ,x,q2′ ) ∈ ∆′ Finite-state automata with epsilon transitions
A finite-state automaton with epsilon transitions (ε-FSA) is a five-tuple (Q, Σ, I, F, ∆) where:
• Q is a finite set of states;
• Σ, the alphabet, is a finite set of symbols;
• I ⊆ Q is the set of initial states;
• F ⊆ Q is the set of ending states; and
• ∆⊆Q×(Σ∪{ε})×Qisthesetoftransitions.
q1 x q2
The difference from what we’ve seen before is that transitions are labeled not with an element of Σ, but rather with either an element of Σ or ε. (Note that ε is a member of the set Σ∗, but it is not a member of Σ.)
a
εb
10 30 31
⟨q1, q1′ ⟩ x ⟨q2, q2′ ⟩
q1′ x q2′
(21)
ε
bb 32
b
20
b
21
Ling185A, Winter 2021 — Tim Hunter, UCLA
abc
εε
(22)
The key idea in dealing with epsilon transitions is the “epsilon-closure” of a state: in the automaton in (21), the epsilon-closure of state 10, which we’ll write as cl∆(10), is the set {10,20,30}; and in the automaton in (22), cl∆(0) = {0, 1, 2} and cl∆(1) = {1, 2}.
(23) If ∆ is the transition function of some ε-FSA, then cl∆(q) is the set of all states reachable from q by a sequence of zero-or-more ε-transitions according to ∆.
It turns out that, given some ε-FSA that contains epsilon transitions, we can always construct another FSA that does not contain any epsilon transitions but generates exactly the same stringset. So the ability to include epsilon transitions doesn’t bring any “extra expressive power”. Allowing epsilon transitions does sometimes make automata easier to design, however.
012
(24)
5 5.1
Given an ε-FSA M = (Q, Σ, I, F, ∆) (which may contain epsilon transitions), we can construct an FSA M′ = (Q,Σ,I,F′,∆′) (which does not contain epsilon transitions) that will generate the same stringset as M as follows:
• The new set of end states, F ′, contains all states q such that cl∆(q) ∩ F ̸= ∅.
• The new transition table ∆′ contains a transition (q1, x, q3) iff there is some q2 ∈ cl∆(q1) such
that (q2, x, q3) ∈ ∆. Regular expressions
Defining regular expressions and their denotations
First we’ll define what regular expressions are, i.e. what counts as a regular expression. That’s all we’re saying in (25).
(25) Given an alphabet Σ, we define RE(Σ), the set of regular expressions over Σ, as follows:
• ifx∈Σ,thenx∈RE(Σ)
• ifr1 ∈RE(Σ)andr2 ∈RE(Σ),then(r1 |r2)∈RE(Σ)
• ifr1 ∈RE(Σ)andr2 ∈RE(Σ),then(r1·r2)∈RE(Σ)
• ifr∈RE(Σ),thenr⋆ ∈RE(Σ)
• 0 ∈ RE(Σ)
• 1 ∈ RE(Σ)
So if we have the alphabet Σ = {a, b, c}, then here are some elements of RE(Σ):
(26) a. (a|b)
b. ((a|b)·c)
c. ((a|b)·c)⋆
Now, any regular expression r ∈ RE(Σ) denotes a particular subset of Σ∗, i.e. denotes a stringset. We’ll
write r for the stringset denoted by r.
(27) Given a regular expression r ∈ RE(Σ), we define the set r ⊆ Σ∗ as follows: a. x={x}
b. (r1 |r2)=r1∪r2
c. (r1 ·r2)={u+v|u∈r1,v∈r2}
Ling185A, Winter 2021 — Tim Hunter, UCLA
⋆
d. r is the smallest set such that: ⋆
• ε ∈ r
⋆⋆
• ifu∈randv∈r ,thenu+v∈r e. 0=∅={}
f. 1={ε}
The tricky part here is the r case. It says roughly that r is the set comprising all strings that we can
⋆⋆
get by concatenating zero or more strings from the set r. Concatenating zero such strings produces ε, ⋆
so ε ∈ r . Concatenating n such strings, where n is non-zero, really means concatenating some string u, which is in r, with some string v, which is the result of concatenating some n − 1 such strings.
We can use this definition to work out the stringsets denoted by the regular expressions in (26).
(28) a. (a|b)=a∪b = {a} ∪ {b}
= {a, b}
b. ((a|b)·c)={u+v|u∈(a|b),v∈c}
= {u + v | u ∈ {a, b}, v ∈ {c}} = {a + c, b + c}
= {ac, bc}
⋆
5.2
c. ((a|b)·c) ={ε,ac,bc,acac,acbc,bcac,bcbc,acacac,acacbc,…} Relating regular expressions to FSAs
It turns out that given any regular expression r, we can construct an ε-FSA M such that L(M) = r, i.e. we can construct an ε-FSA that generates exactly the stringset denoted by r.
To do this we need to proceed recursively on the structure of the regular expression — because there are unboundedly many regular expressions to deal with. The diagrams below give the important ideas for how this works, but to avoid clutter assume unique starting states and ending states; once you understand what’s going on, it’s relatively easy to generalize to multiple starting and/or ending states.
(29) a.
We can construct an ε-FSA that generates the stringset x, for any x ∈ Σ, as follows: x
b. We can construct an ε-FSA that generates the stringset (r1 | r2), if we are given an ε-FSA M1 that generates r1 and an ε-FSA M2 that generates r2, as follows:
NB: This will usually produce an au- tomaton that has multiple start states and multiple end states.
c. We can construct an ε-FSA that generates the stringset (r1 · r2), if we are given an ε-FSA M1
Ling185A, Winter 2021 — Tim Hunter, UCLA
that generates r1 and an ε-FSA M2 that generates r2, as follows:
NB: This requires an ε-transition link- ing every ending state of M1 to every starting state of M2.
⋆
NB: This requires an ε-transition linking every ending state of M to every start- ing state of M, and an ε-transition link- ing the new state to every starting state of M.
e. We can construct an ε-FSA that generates the stringset 0 as follows:
f. We can construct an ε-FSA that generates the stringset 1 as follows:
6 Summing up: Regular languages
A stringset S ⊆ Σ∗ is a regular stringset (or regular language) iff there is some regular expression r ∈ RE(Σ) such that r = S.
We’ve just seen that, given any regular expression r, we can construct an ε-FSA M such that L(M) = r. This tells us that any stringset that can be described by a regular expression — any regular language — can also be described by an ε-FSA.
It turns out — surprisingly, perhaps — that we can also go the other way: given an ε-FSA M, there is a method for constructing a regular expression r such that r = L(M).2 So any stringset that can be described by an ε-FSA is also a regular language.
d. We can construct an ε-FSA that generates the stringset r , if we are given an ε-FSA M that generates r, as follows:
2This is a bit trickier to prove, but see e.g. pages 33–34 of Hopcroft & Ullman (1979), or pages 69–74 of Sipser (1997).
Ling185A, Winter 2021 — Tim Hunter, UCLA
So for any stringset S, either all of the following are true or all are false:
(30) a.
b. There is some regular expression r such that r = S.
c. There is some ε-FSA M such that L(M) = S.
d. There is some FSA M such that L(M) = S.
e. The number of distinct classes of S-equivalent prefixes, i.e. the number of buckets into which
strings are sorted by the relation ≡S, is finite.
f. The number of distinct classes of S-equivalent suffixes is finite.3
For more on these topics, two good textbooks are:
• Hopcroft & Ullman 1979, Introduction to Automata Theory, Languages and Computation,
chapters 2 and 3.
• Sipser 1997, Introduction to the Theory of Computation, chapter 1.
S is a regular language.
3This is just the obvious parallel to the idea of S-equivalent prefixes: two strings u and v are S-equivalent suffixes iff, for all strings w, wu and wv are either both in S or both not in S.
Ling185A, Winter 2021 — Tim Hunter, UCLA