Those who cannot remember the past are condemned to repeat it.
— Jorge Agustín Nicolás Ruiz de Santayana y Borrás, The Life of Reason, Book I:
Introduction and Reason in Common Sense (1905)
Those who cannot remember the past are condemned to repeat it.
— Jorge Agustín Nicolás Ruiz de Santayana y Borrás, The Life of Reason, Book I:
Introduction and Reason in Common Sense (1905)
Those who cannot remember the past are condemned to repeat it.
— Jorge Agustín Nicolás Ruiz de Santayana y Borrás, The Life of Reason, Book I:
Introduction and Reason in Common Sense (1905)

C
Dynamic Programming for FormalLanguages and Automata[Read Chapter 3 ﬁrst.]
Status: UnﬁnishedThis chapter describes dynamic programming algorithms for several problems involving formal languages and finite-state automata. Although I have strived for aself-contained presentation, this material will likely make sense only to people who arealready somewhat familiar with formal languages and dynamic programming.

C.1

DFA MinimizationÆÆÆWrite this.

C.2

NFA Acceptance

Recall that a nondeterministic finite-state automaton—or NFA for short—can bedescribed as a directed graph, whose edges are called states and whose edges have labels© 2018 Jeff Erickson

http://algorithms.wtf

1

C. DYNAMIC PROGRAMMING FOR FORMAL LANGUAGES AND AUTOMATA

drawn from a finite set Σ called the alphabet. Every NFA has a designated start state
and a subset of accepting states. Every walk in this graph has a label, which is a string
formed by concatenating the labels of the edges in the walk. A string w is accepted byan NFA if and only if there is a walk from the start state to one of the accepting states
whose label is w.
More formally (or at least, more symbolically), an NFA consists of a finite set Q of states,
a start state s ∈ Q, a set of accepting states A ⊆ Q, and a transition function δ : Q×Σ → 2Q .
We recursively extend the transition function to a function δ∗ : Q × Σ∗ → 2Q over strings
by defining
{q}[δ∗ (q, w) =

if w = ",δ∗ (r, x) if w = a x for some a ∈ Σ and x ∈ Σ∗r∈δ(q,a)

Our NFA accepts string w if and only if the set δ∗ (s, w) contains at least one acceptingstate.
We can express this acceptance criterion more directly in terms of the originaltransition function δ as follows. Let Accepts?(q, w) = True if our NFA would accept
string w if it started in state q (instead of the usual start state s), and Accepts?(q, w) =False otherwise. The function Accepts? has the following recursive definition:True
if w = " and q ∈ A

False
if w = " and q 6∈ AAccepts?(q, w) :=_Accepts?(r, x) if w = a x for some a ∈ Σ and x ∈ Σ∗r∈δ(q,a)

Then our NFA accepts w if and only if Accepts?(s, w) = True.

Backtracking
In the magical world of non-determinism, we can imagine that the NFA always makes
the right decision when faced with multiple transitions, or perhaps spawns off an
independent parallel thread for each possible choice. Alas, real computers are neither
clairvoyant nor (despite the increasing use of multiple cores) infinitely parallel. To
simulate the NFA’s behavior directly, we must recursively explore the consequences ofeach choice explicitly.
Before we can turn our recursive definition(s) into an algorithm, we need to nail
down the precise input representation. Let’s assume, without loss of generality, that thealphabet is Σ = {1, 2, . . . , |Σ|}, the state set is Q = {1, 2, . . . , |Q|}, the start state is state 1,and our input consists of three arrays:• A boolean array A[1 .. |Q|], where A[q] = True if and only if q ∈ A.
2

C.2. NFA Acceptance• A boolean array δ[1 .. |Q|, 1 .. |Σ|, 1 .. |Q|], where δ[p, a, q] = True if and only ifp ∈ δ(q, a).
• An array w[1 .. n] of symbols, representing the input string.
Fixing the input string w[1 .. n] lets us simplify the definition of the acceptance functionslightly. For any state q and index i, define Accepts?(q, i) = True if the NFA accepts thesuffix w[i .. n] starting in state q, and Accepts?(q, i) = False otherwise.
Trueif i > n and q ∈ AFalse
if i > n and q 6∈ AAccepts?(q, i) :=_
Accepts?(r, i + 1) otherwiser∈δ(q,a)

In particular, the NFA accepts w if and only if Accepts?(s, 1) = True. This is only a minor
notational change from the previous definition, but it makes the recursive calls moreefficient (passing just an integer instead of a string) and eventually easier to memoize.
Our new recursive definition translates directly into the following backtracking algorithm.

Accepts?(q, i):
if i > nreturn A[q]for r ← 1 to |Q|
if δ[q, w[i], r] and Accepts?(r, i + 1)
return True
return False

Dynamic Programming
The previous algorithm runs in O(|Q|n ) time in the worst case; fortunately, everything is
set up to quickly derive a faster dynamic programming solution. The Accepts? function
can be memoized into a two-dimensional array Accepts?[1 .. |Q|, 1 .. n + 1]. Each entry
Accepts?[q, i] depends only on entries of the form Accepts?[r, i + 1], so we can fill thememoization table by considering indices i in decreasing order in the outer loop, andstates q in arbitrary order in the inner loop. Evaluating each entry Accepts?[q, i] requires
O(|Q|) time, using an even deeper loop over all states r, and there are O(n|Q|) suchentries. Thus, the entire dynamic programming algorithm requires O(n|Q|2 ) time.
3

C. DYNAMIC PROGRAMMING FOR FORMAL LANGUAGES AND AUTOMATANFAaccepts?(A[1 .. |Q|], δ[1 .. |Q|, 1 .. |Σ|, 1 .. |Q|], w[1 .. n]):for q ← 1 to |Q|
Accepts?[q, n + 1] ← A[q]for i ← n down to 1for q ← 1 to |Q|
Accepts?[q, i] ← Falsefor r ← 1 to |Q|
if δ[q, w[i], r] and Accepts?[r, i + 1]
Accepts?[q, i] ← True
return Accepts?[1, 1]

C.3

Regular Expression MatchingÆÆÆ

Write this. Assume given an expression tree.

C.4

CFG Parsing

Another problem from formal languages that can be solved via dynamic programmingis the parsing problem for context-free languages. Given a string w and a context-freegrammar G, does w belong to the language generated by G? Recall that a context-freegrammar over the alphabet Σ consists of a finite set Γ of non-terminals (disjoint from Σ)and a finite set of production rules of the form A → w, where A is a nonterminal and w isa string over Σ ∪ Γ . The length of a context free grammar is the number of production
rules.
Real-world applications of parsing normally require more information than just asingle bit. For example, compilers require parsers that output a parse tree of the input
code; some natural language applications require the number of distinct parse trees for agiven string; others assign probabilities to the production rules and then ask for the most
likely parse tree for a given string. However, once we have an algorithm for the decision
problem, it it not hard to extend it to answer these more general questions.
For any nonterminal A and any string x, define Gen?(A, x) = True if x can be derived
from A and Gen?(A, x) = False otherwise. At first glance, it seems that the production
rules of the CFL immediately give us a (rather complicated) recursive definition for thisfunction. Unfortunately, there are a few subtle problems.1• Consider the context-free grammar S → " | SS | (S ) that generates all properly
balanced strings of parentheses. The most straightforward recursive algorithm forGen?(S, w) recursively checks whether x ∈ L(S) and y ∈ L(S), for every possible
partition w = x • y, including the trivial partitions w = " • w and w = w • ". Thus,
Gen?(S, w) can call itself, leading to an infinite loop.
14

Similar subtleties arise in induction proofs about context-free grammars.

C.4. CFG Parsing• Consider another grammar that includes the productions S → A, A → B, and B → S,
possibly among others. The “obvious” recursive algorithm for Gen?(S, w) must callGen?(A, w), which calls Gen?(B, w), which calls Gen?(S, w), and we are again in an
infinite loop.
To avoid these issues, we will make the simplifying assumption that our input grammar
is in Chomsky normal form, which means that it has the following special structure:• The starting non-terminal S does not appear on the right side of any production rule.
• The grammar may include the production rule S → ", where S is the starting
non-terminal, but does not contain the rule A → " for any other non-terminal A 6= S.
• Otherwise, every production rule has the form A → BC (two non-terminals) or A → a(one terminal).
Any context-free grammar can be converted into an equivalent grammar Chomsky normalform; moreover, if the original grammar has length L, an equivalent CFG grammarof length O(L 2 ) can be computed in O(L 2 ) time. The conversion algorithm is fairly
complex, and we haven’t yet seen all the algorithmic tools needed to understand it; forpurposes of this chapter, it’s enough to know that such an algorithm exists. For example,
the language of all properly balanced strings of parentheses is generated by the CNF
grammarS → " | AA | BC

A → AA | BC

B → LAC → RA

L→(R→)〈〈This is incorrect.〉〉
With this simplifying assumption in place, the function Gen? has a relatively straightforward recursive definition.
Trueif |x| ≤ 1 and A → xFalseif |x| ≤ 1 and A 6→ x
Gen?(A, x) =_ _Gen?(B, y) ∧ Gen?(C, z) otherwiseÃÃÃÃÃA→BC y•z=x

The first two cases take care of terminal productions A → a and the "-production S → "(if the grammar contains it). Here the notation A 6→ x means that A → x is not a
production rule in the given grammar. In the third case, for all production rules A → BC,and for all ways of splitting x into a non-empty prefix y and a non-empty suffix z, werecursively check whether y ∈ L(B) and z ∈ L(C). Because we pass strictly smaller
strings in the second argument of these recursive calls, every branch of the recursion
tree eventually terminates.
This recurrence was transformed into a dynamic programming algorithm by Tadao
Kasami in 1965, and again independently by Daniel Younger in 1967, and again independently by John Cocke in 1970, so of course the resulting algorithm is known as“Cocke-Younger-Kasami”, or more commonly the CYK algorithm, with the names listed
in reverse chronological order.
5C. DYNAMIC PROGRAMMING FOR FORMAL LANGUAGES AND AUTOMATA

We can derive the CYK algorithm from the previous recurrence as follows. As usual forrecurrences involving strings, we modify the function to accept index arguments insteadof strings, to ease memoization. Fix the input string w, and then let Gen?(A, i, j) = True
if and only if the substring w[i .. j] can be derived from non-terminal A. Now our earlier
recurrence can be rewritten as follows:Trueif i = j and A → w[i]Falseif i = j and A 6→ w[i]Gen?(A, i, j) =j−1_ _Gen?(B, i, k) ∧ Gen?(C, k + 1, j) otherwise
A→BC k=iThen w lies in the language of the grammar if and only if either Gen?(A, 1, n) = True,or w = " and the grammar includes the production S → ".
We can memoize the function Gen? into a three-dimensional boolean array Gen[1 .. |Γ |,1 .. n, 1 .. n], where the first dimension is indexed by the non-terminals Γ in the input
grammar. Each entry Gen[A, i, j] in this array depends on entries of the form Gen[ · , i, k]
for some k < j, or Gen[ · , k + 1, j] for some k ≥ i. Thus, we can fill the array byincreasing j and decreasing i in two outer loops, and considering non-terminals A inarbitrary order in the inner loop. The resulting dynamic programming algorithm runs inO(n 3 L) time, where L is the length of the input grammar.
CYKParse(w, G):
if w = "if G contains the production S → "return True
else
return False
for i ← 1 to nfor all non-terminals A
if G contains the production A → w[i]Gen[A, i, i] ← Trueelse
Gen[A, i, i] ← False
for j ← 1 to nfor i ← n down to j + 1
for all non-terminals A
Gen[A, i, j] ← False
for all production rules A → BCfor k ← i to j − 1
if Gen[B, i, k] and Gen[C, k + 1, j]
Gen[A, i, j] ← True
return Gen[S, 1, n]

6

C.4. CFG Parsing

ExercisesÆÆÆAdd some exercises!

© 2018 Jeff Erickson

http://algorithms.wtf7