1
• •
• •
•
• •
2
•
• •
Regular Expressions and NFAs
Peter Dixon April 24, 2021
Previously on Yu-Gi-Oh!
Regular expressions are simple pattern-matching tools. Pick some alpha- bet Σ.
A regular expression is a string made out of symbols in Σ, the special symbols ∅,λ,#,@, and the operations +,∩, concatenation,∼, ∗, +, and parentheses for marking order of operations.
Not all of these are necessary: all you need is a symbol for each symbol in Σ, ∅, and the operations +, concatenation, ∗, and parentheses.
A pattern “matches” a set of strings. For example, if Σ = {a,b}, then p =∼ (a∗b∗) matches any string containing ba.
We say L(p) = {x|x contains ba as a substring}
We want to show that regular expressions match regular languages. It’s a two step process:
First, we start with a regex p and build an NFA that accepts L(p). Second, we start with a DFA D and build a regex that matches L(D).
Regex to NFA
How do we build a NFA for a regex? We’ll break the regex down into pieces.
First, we’ll show that we can build a NFA for the basic patterns.
Then we’ll show that if we can build an NFA for the inputs to an operation, we can build an NFA for the operation. (That is, let p, q be patterns. If we can build NFAs for p and q, then we can build NFAs for p+q,p∗, and so on.
1
• Basic patterns: a ∈ Σ, ∅
• Regular languages are closed under union, Kleene star, complement, and concatenation QED
• Ok, fine, we can actually show that stuff. Suppose we have NFAs for patterns p and q.
• (p + q): epsilon transition to the start states of p and q pstart
λ
λ
qstart
• p∗: epsilon transitions from the accept states back to the start state; start state accepts
λ
…
λ
2
a
pstart
… …
λ
…
• ∼ p: convert to a DFA using NFA-DFA equivalence, swap the accept and reject states.
• pq: connect every accept state of the p NFA to the start state of the q NFA
… …
pacc
pacc
…
pstart
λ
λ
qstart
…
…
λ pacc
• Intuitively, every formula is made out of combining ”things you can do with an NFA” using ”operations you can do with an NFA”, so any formula can be done with an NFA
• Formally, use induction on the formula
• Example: Regex is (010 + 11)∗101
• Concatenation of (010 + 11)∗ and 101 – need NFAs for those, then apply the concatenation construction
• NFA for (010 + 11)∗ means I need an NFA for (010 + 11), then apply the ∗ construction
• NFA for (010 + 11) means I need NFAs for 010 and 11, then apply the + construction
• 010 and 11:
s010
s11
010
11
3
• (010+11):
s010 λ
λ
s11
010
11
• (010+11)∗:
1 00
s010 λλ
λ s11
11
1 00
s010 λλ
λ
λ
λ
•
(010 + 11)∗101:
λ
s11
s101
11
10
1
3
DFA to regex
• We need to build a regex that matches the set of strings accepted by D 4
• We’ll think of L(D) as ”every string that takes us from the start state to an accept state”
• and then we’ll start small and build up.
• We’ll limit ourselves by which states we’re allowed to ”go through”
• Example first this time. Here’s our DFA:
01
10
abc
10
• What we need at the end is “all paths from a back to a”. What we’ll start with is “all paths from a to a using no states in between”. That’s obviously just the string 0.
• We’ll do this for all pairs of states.
– (a,b)=1 – (a,c)=∅ – (b,a)=1 – (b,b)=∅ – (b,c)=0 – (c,a)=∅ – (c,b)=0 – (c,c)=1
• What about “all paths from b to b using only a in between?”
• Well,wecangofrombtoa,thengofromatoaasmuchaswewant,then
go from a to b
• So it’s (b,a), then (a,a)∗, then (a,b)
• We’re gonna need some better notation: DX is the regex for “strings that uv
go from u to v, using only states in X in between”
• The first nine we did are D∅ ,D∅ ,…D∅ .
• The next one was D{a} bb
• Now we gotta extend our logic for D{a} to a general input bb
• We’ll pick a state w in X (in our example, there was only one choice, it was a)
5
aaab cc
• Wecangofromutow,thenwecangofromwtoitself,thenwecango from w back to v, all without using w “in between”
• (in other words, we’re splitting the sequence of states we visit by w)
• Now, the regex for DX can be recursively defined as
X−{w} Duv
0+1
DX= 0 uv
1
uv
X−{w} X−{w} ∗ X−{w}
w∈X
X = ∅,δ(u,0) = v,δ(u,1) = v X = ∅,δ(u,0) = v,δ(u,1) ̸= v X = ∅,δ(u,0) ̸= v,δ(u,1) = v X = ∅,δ(u,0) ̸= v,δ(u,1) ̸= v
+Duw
(Dww
) Dwv
∅
• Now we get the final answer by applying this definition for DQ with each
f ∈ F , and +ing together each expression • Example again:
01
10
abc
10
sf
• We’ll pull the states out in the order b, a, c Q {a,c} {a,c} {a,c} ∗ {a,c}
• Daa =Daa +Dab (Dbb ) Dba {a,c} {c} {c} {c} ∗ {c}
• Dab =Dab +Daa (Daa ) Dab {c}∅∅∅∗∅ ∗
• Daa =Daa +Dac(Dcc) Dca =0+∅(1) ∅=0
• D{c} =D∅ +D∅ (D∅ )∗D∅ =1+∅(1)∗0=1
ab ab ac cc cb
{a,c} {c} {c} {c}∗ {c} ∗ ∗
• Dab =Dab +Daa (Daa ) Dab =1+0(0) 1=0 1
• Ok, that’s one of the top level terms done… We still have 3 more of these
to go.
{a,c}
• Daa
{a,c}
• Dbb
∗
{c} {c} {c} ∗ {c} =Dbb +Dba (Daa ) Dab
=0 justbylookingatit
• D{c} =D∅ +D∅ (D∅ )∗D∅ =∅+0(1)∗0=01∗0 bb bb bc cc cb
• D{c} =D∅ +D∅ (D∅ )∗D∅ =1+0(1)∗∅=1 ba ba bc cc ca
6
4
{c} {c} • and we already did Daa and Dab
• D{a,c} = 01∗0 + 1(0∗)∗1 = (01∗0 + 10∗1) bb
{a,c} {c} {c} {c} ∗ {c} • Lastone! Dba =Dba +Dba (Daa ) Daa
• We already have all of these: D{a,c} = 1 + 1(0∗)∗0∗ = 10∗ ba
Q {a,c} {a,c} {a,c} ∗ {a,c} • Daa =Daa +Dab (Dbb ) Dba
• DQ = 0∗ + 0∗1(01∗0 + 10∗1)∗10∗ aa
• Different orders of states will give different (but equivalent) regex • Some orders will be easier to expand than others
NFA to DFA: exponential blowup is necessary
Bit of backtracking to the NFA-DFA conversion. The subset construction gives you 2n states, but often many are useless or redundant. Not always, though: we’ll show that, for any n, there’s a language with a n + 1-state NFA, but every DFA for it has ≥ 2n states.
Where are NFAs better than DFAs? Where you have to make a decision NOW, but you don’t know if you made the right decision until much later. Ex. L1 ∪ L2 with a NFA, you guess L1 or L2 at the start, and you know you’re right at the end; with a DFA you have to keep track of all the combinations of states.
Here’s the language: Ln = {x ∈ {0, 1}∗|the nth symbol from the end of x is 1}
Here’s a NFA with n + 1 states 00
0 1 1
0,1
1
2 0,1 … 0,1 n
1
So why does a DFA need 2n states?
• Suppose there’s a DFA with less than 2n states
• There’s 2n n-bit strings, so two of them x and y go to the same state q.
7
• Soforanyz,xzandyzgotothesamestate
• Also x ̸= y, so there has to be at least one bit where they’re different
• Let’ssaytheydifferattheith bit,andassumeWLOGxi =0andyi =1
• Then pick z to be some (n − i)-bit string
• xz ̸∈ L and yz ∈ L, but the DFA has to accept both or reject both, contradiction
8