N

Lecture Notes on

Regular Languages
and Finite Automata

for Part IA of the Computer Science Tripos

Prof. Andrew M. Pitts

Cambridge University Computer Laboratory

c A. M. Pitts, 1998-2003
First Edition 1998.
Revised 1999, 2000, 2001, 2002, 2003.
Contents
Learning Guide ii

1 Regular Expressions 1
1.1 Alphabets, strings, and languages . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Pattern matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Some questions about languages . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Finite State Machines 11

2.1 Finite automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Determinism, non-determinism, and
-transitions . . . . . . . . . . . . . . . 14
2.3 A subset construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Regular Languages, I 21
3.1 Finite automata from regular expressions . . . . . . . . . . . . . . . . . . . . 21
3.2 Decidability of matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4 Regular Languages, II 29
4.1 Regular expressions from finite automata . . . . . . . . . . . . . . . . . . . 29
4.2 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Complement and intersection of regular languages . . . . . . . . . . . . . . . 32
4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5 The Pumping Lemma 37

5.1 Proving the Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Using the Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.3 Decidability of language equivalence . . . . . . . . . . . . . . . . . . . . . . 42
5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6 Grammars 45
6.1 Context-free grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 Backus-Naur Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.3 Regular grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
ii

Learning Guide
The notes are designed to accompany six lectures on regular languages and finite automata
for Part IA of the Cambridge University Computer Science Tripos. The aim of this short
course will be to introduce the mathematical formalisms of finite state machines, regular
expressions and grammars, and to explain their applications to computer languages. As such,
it covers some basic theoretical material which Every Computer Scientist Should Know.
Direct applications of the course material occur in the various CST courses on compilers.
Further and related developments will be found in the CST Part IB courses Computation
Theory and Semantics of Programming Languages and the CST Part II course Topics in
Concurrency.
This course contains the kind of material that is best learned through practice. The books
mentioned below contain a large number of problems of varying degrees of difficulty, and
some contain solutions to selected problems. A few exercises are given at the end of each
section of these notes and relevant past Tripos questions are indicated there. At the end
of the course students should be able to explain how to convert between the three ways of
representing regular sets of strings introduced in the course; and be able to carry out such
conversions by hand for simple cases. They should also be able to prove whether or not a
given set of strings is regular.

Recommended books Textbooks which cover the material in this course also tend to
cover the material you will meet in the CST Part IB courses on Computation Theory and
Complexity Theory, and the theory underlying parsing in various courses on compilers.
There is a large number of such books. Three recommended ones are listed below.
 D. C. Kozen, Automata and Computability (Springer-Verlag, New York, 1997).
 T. A. Sudkamp, Languages and Machines (Addison-Wesley Publishing Company,
Inc., 1988).
 J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory,
Languages, and Computation, Second Edition (Addison-Wesley, 2001).

Note The material in these notes has been drawn from several different sources, including
the books mentioned above and previous versions of this course by the author and by others.
Any errors are of course all the author’s own work. A list of corrections will be available
from the course web page (follow links from [Link]/Teaching/). A lecture(r)
appraisal form is included at the end of the notes. Please take time to fill it in and return it.
Alternatively, fill out an electronic version of the form via the URL [Link]/cgi-
bin/lr/login.

Andrew Pitts
[Link]@[Link]
 1

1 Regular Expressions

Doubtless you have used pattern matching in the command-line shells of various operating
systems (Slide 1) and in the search facilities of text editors. Another important example of
the same kind is the ‘lexical analysis’ phase in a compiler during which the text of a program
is divided up into the allowed tokens of the programming language. The algorithms which
implement such pattern-matching operations make use of the notion of a finite automaton
(which is Greeklish for finite state machine). This course reveals (some of!) the beautiful
theory of finite automata (yes, that is the plural of ‘automaton’) and their use for recognising
when a particular string matches a particular pattern.

Pattern matching

What happens if, at a Unix/Linux shell prompt, you type



and press return?


Suppose the current directory contains files called 
  ,
  !
   , 
  ,   , and (strangely)
"
 . What happens if you type
#"

and press return?

Slide 1

1.1 Alphabets, strings, and languages

The purpose of Section 1 is to introduce a particular language for patterns, called regular
expressions, and to formulate some important problems to do with pattern-matching which
will be solved in the subsequent sections. But first, here is some notation and terminology to
do with character strings that we will be using throughout the course.
2 1 REGULAR EXPRESSIONS

Alphabets

An alphabet is specified by giving a finite set, $ , whose elements

are called symbols. For us, any set qualifies as a possible
alphabet, so long as it is finite.
%'&)(+*-,.0/1.32.54.768.39.5:.5;.7<.>=?
Examples: /@,
%BAC(+*-D.5E-.5FG.0H0H0H7.>IJ.7K.5L? 2M:
— -element set of decimal digits.
— -element set of lower-case
%ONP(+*GQSof
characters RGQUtheTSEnglish 2 &XW
%'&V? language.
— -element set of all subsets of the alphabet
of decimal digits.

(+*-,.0/1.32.54.0H0H0HZ?
Non-example:
Y
— set of all non-negative whole numbers is not
an alphabet, because it is infinite.

Slide 2

Strings over an alphabet

A string of length [ ( \^] ) over an alphabet $ is just an ordered

[ -tuple of elements of $ , written without punctuation.
%_(+*-D.5EG.5F@? D DE DDF E`EaDF
%
Example: if , then , , , and are strings over
of lengths one, two, three and four respectively.

$cbed-i fhg set of all strings over $ of any finite length.

N.B. there is a unique string of length zero over $ , called the null
string (or empty string) and denoted j (no matter which $ we
are talking about).

Slide 3
 1.1 Alphabets, strings, and languages 3

Concatenation of strings

The concatenation of two strings kml`npoSqsr is the string kJn

obtained by joining the strings end-to-end.

Examples: If tvuxwy , z u}|~w

{ and €ux`w‚ , then z"tvuƒ|Mwwy ,
ttvuxwy`wy and Pz{ux`w‚„|Mw .

This generalises to the concatenation of three or more strings.

E.g. k…n†‡k…n‰ˆ‹ŠŒ-"ŠŽ-ŠŠŒ@"Š .

Slide 4

Slides 2 and 3 define the notions of an alphabet  , and the set ’‘ of finite strings over an
alphabet. The length of a string t will be denoted by “•”a–—~˜š™
›œt . Slide 4 defines the operation
of concatenation of strings. We make no notational distinction between a symbol wŸž‰ and
the corresponding string of length one over  : so  can be regarded as a subset of c‘ . Note
that  ‘ is never empty—it always contains the null string,   , the unique string of length zero.
Note also that for any tJ¡7z¡7}ž‰P‘

t cuƒt¢ux -t and ›œtzh€uƒtz"ƒuƒt£›šz"¤

and “•”a–—~˜š™
›œtz¥u¦“•”`–—~˜š™›št§x“•”a–—~˜š™
›œz .

Example 1.1.1. Examples of  ‘ for different  :

(i) If _u+¨-w© , then P‘ contains

 ¡5w¡5ww¡5www¡5wwww¡0ª`ªVª
(ii) If _u+¨-w¡5y@© , then P‘ contains

 "¡5w¡5yG¡5ww¡5wy-¡5y`w¡5y3yG¡5w"ww¡5w"wyG¡>wy`w¡7wy`yG¡>y`w"w¡7yawy@¡5yayaw¡7yay`y@¡0ªVªVª

(iii) If «u­¬ (the empty set — the unique set with no elements), then ¤‘®u¯¨0 „© , the set just
containing the null string.
4 1 REGULAR EXPRESSIONS

1.2 Pattern matching

Slide 5 defines the patterns, or regular expressions, over an alphabet ° that we will use.
Each such regular expression, ± , represents a whole set (possibly an infinite set) of strings
in °P² that match ± . The precise definition of this matching relation is given on Slide 6. It
might seem odd to include a regular expression ³ that is matched by no strings at all—but it
is technically convenient to do so. Note that the regular expression ´ is in fact equivalent to
³ ² , in the sense that a string µ matches ³ ² iff it matches ´ (iff µv¶€´ ).

Regular expressions over an alphabet ·

¸ each symbol ¹»º_· is a regular expression
¸½¼ is a regular expression
¸¿¾ is a regular expression
¸ if À and Á are regular expressions, then so is ÂXÀ
ÃÁ„Ä
¸ if À and Á are regular expressions, then so is ÀÁ
¸ if À is a regular expression, then so is ÂXÀÄaÅ
Every regular expression is built up inductively, by finitely many
applications of the above rules.

(N.B. we assume ´ , ³ , Æ , Ç , È , and ² are not symbols in ° .)

Slide 5

Remark 1.2.1 (Binding precedence in regular expressions). In the definition on Slide 5

we assume implicitly that the alphabet ° does not contain the six symbols

´ ³ Æ Ç È ²
Then, concretely speaking, the regular expressions over ° form a certain set of strings over
the alphabet obtained by adding these six symbols to ° . However it makes things more
readable if we adopt a slightly more abstract syntax, dropping as many brackets as possible
and using the convention that

É ² binds more tightly than É»É , binds more tightly than É È É .

So, for example, ±ÈËÊVÌ5² means Ɯ±ÈËÊ"ƜÌZÇ5²aÇ , not ƚ±ÈËÊ-ÇVƜÌZÇ5² , or Æ>ƚ±ÈÍÊ0ÌZÇ>Ç5² , etc.
1.2 Pattern matching 5

Matching strings to regular expressions

ÎÐÏ matches ÑÓÒSÔ iff

ÏÖÕ Ñ
ÎÐÏ matches × iff
ÏÖÕ ×
Î no string matches Ø
ÎÐÏ matches ÙÚÛ iff
Ï matches either Ù or Û
ÎÐÏ matches ÙÛ iff it can be expressed as the concatenation of
two strings,
ÏÖÕÝÜÞ , with
Ü matching Ù and
Þ matching Û
ÎÐÏ matches Ùß iff either
Ï½Õ × , or
Ï matches Ù , or
Ï can be
expressed as the concatenation of two or more strings, each
of which matches Ù

Slide 6

The definition of ‘à matches áâ ’ on Slide 6 is equivalent to saying

for some ãåä æ , à can be expressed as a concatenation of ã strings, àèç

à…é>àê¥ë0ë0ëhàì , where each àí matches á .

The case ãîçxæ just means that à®ç€ï (so ï always matches áâ ); and the case ãîçñð just means
that à matches á (so any string matching á also matches áâ ). For example, if òeçôó-õö5÷Gö5ø@ù
and á’çxõ÷ , then the strings matching á â are

ï"ö5õ÷Gö5õ÷aõ÷-ö5õ÷`õ÷`õ÷Gö etcë

Note that we didn’t include a regular expression for the ‘ ú ’ occurring in the UNIX
examples on Slide 1. However, once we know which alphabet we are referring to, òûç
ó-õé`ö5õêGö0ë0ë0ë3ö5õìù say, we can get the effect of ú using the regular expression
ü
õé~ýÍõê"ý5ë0ë0ë@ýÍõì8þ â

which is indeed matched by any string in ò â (because õé~ýÍõê"ý5ë0ë0ë@ýÍõì is matched by any symbol
in ò ).
6 1 REGULAR EXPRESSIONS

Examples of matching, with


ÿ
   is matched by each symbol in ÿ
   is matched by any string in ÿ  that starts with a ‘  ’
     is matched by any string of even length in ÿ 
       is matched by any string in ÿ 
   is matched by just the strings  ,  ,  ,  , and
  is just matched by 

Slide 7

Notation 1.2.2. The notation "!$#

is quite often used for what we write as . &%'#
The notation , for( )+*-,
, is an abbreviation for the regular expression obtained by
)
concatenating copies of . Thus:
. /
20 5-143 6
025 143 <;=(?>@
(87:9
Thus A matches B iff A matches ( for some )C*D, .
We use E7 as an abbreviation for  B . Thus A matches 87 iff it can be expressed as the
concatenation of one or more strings, each one matching .

1.3 Some questions about languages

Slide 8 defines the notion of a formal language over an alphabet. We take a very extensional
view of language: a formal language is completely determined by the ‘words in the
dictionary’, rather than by any grammatical rules. Slide 9 gives some important questions
about languages, regular expressions, and the matching relation between strings and regular
expressions.
1.3 Some questions about languages 7

Languages

A (formal) language F over an alphabet G is just a set of strings

in GIH .

Thus any subset FKJLGMH determines a language over G .

The language determined by a regular expression N over G is

FPONQSRUX TWV YZ\[ G H^] Z matches N&_&`

Two regular expressions N and a (over the same alphabet) are
equivalent iff FPONQ and FPOba8Q are equal sets (i.e. have exactly the
same members).

Slide 8

Some questions

(a) Is there an algorithm which, given a string Z and a regular

N
not Z
expression (over the same alphabet), computes whether or
matches ? N
(b) In formulating the definition of regular expressions, have we
missed out some practically useful notions of pattern?

(c) Is there an algorithm which, given two regular expressions N

and a (over the same alphabet), computes whether or not
they are equivalent? (Cf. Slide 8.)

(d) Is every language of the form FcON<Q ?

Slide 9
 8 1 REGULAR EXPRESSIONS

The answer to question (a) on Slide 9 is ‘yes’. Algorithms for deciding such pattern-
matching questions make use of finite automata. We will see this during the next few sections.
If you have used the UNIX utility d
egfih
, or a text editor with good facilities for regular
expression based search, like fkjml<n
o
, you will know that the answer to question (b) on Slide 9
is also ‘yes’—the regular expressions defined on Slide 5 leave out some forms of pattern
that one sees in such applications. However, the answer to the question is also ‘no’, in the
sense that (for a fixed alphabet) these extra forms of regular expression are definable, up
to equivalence, from the basic forms given on Slide 5. For example, if the symbols of the
alphabet are ordered in some standard way, it is common to provide a form of pattern for
naming ranges of symbols—for example pqlsrutv
might denote a pattern matching any lower-
case letter. It is not hard to see how to define a regular expression (albeit a rather long one)
which achieves the same effect. However, some other commonly occurring kinds of pattern
are much harder to describe using the rather minimalist syntax of Slide 5. The principal
example is complementation, : wyx=zi{
| matches w}x=zE{ iff | does not match z .
It will be a corollary of the work we do on finite automata (and a good measure of its power)
that every pattern making use of the complementation operation can be replaced by w}xWr~{
an equivalent regular expression just making use of the operations on Slide 5. But why do
we stick to the minimalist syntax of regular expressions on that slide? The answer is that it
reduces the amount of work we will have to do to show that, in principle, matching strings
against patterns can be decided via the use of finite automata.
The answer to question (c) on Slide 9 is ‘yes’ and once again this will be a corollary of
the work we do on finite automata. (See Section 5.3.)
Finally, the answer to question (d) is easily seen to be ‘no’, provided the alphabet 
contains at least one symbol. For in that case €
is countably infinite; and hence the number of

languages over , i.e. the number of subsets of €
is uncountable. (Recall Cantor’s diagonal

argument.) But since is a finite set, there are only countably many regular expressions

over . (Why?) So the answer to (d) is ‘no’ for cardinality reasons. However, even amongst
the countably many languages that are ‘finitely describable’ (an intuitive notion that we will
not formulate precisely) many are not of the form ƒ‚ x=zi{
for any regular expression . For z
example, in Section 5.2 we will use the ‘Pumping Lemma’ to see that
„U…†‡†‰ˆUŠŒ‹DgŽ
is not of this form.

1.4 Exercises
Exercise 1.4.1. Write down an ML data type declaration for a type constructor l‘egf8d8’
“8h
whose values correspond to the regular expressions over an alphabet . l
Exercise 1.4.2. Find regular expressions over
„U<”•iŽ that determine the following languages:
(a)
„| ˆ| contains an even number of ’s
• Ž
 1.4 Exercises 9

(b) –k—™˜k— contains an odd number of ’sš ›

Exercise 1.4.3. For which alphabets œ is the set œs of all finite strings over œ itself an
alphabet?

œ
Exercise 1.4.4. If an alphabet contains only one symbol, what does œ
look like? (Answer:
see Example 1.1.1(i).) So if Dœ ž
–Ÿ8›
is the set consisting of just the null string, what is ? œ
(The answer is not –Ÿ8›
.) Moral: the punctuation-free notation we use for the concatenation of
two strings can sometimes be confused with the punctuation-free notation we use to denote
strings of individual symbols.

Tripos questions 1999.2.1(s) 1997.2.1(q) 1996.2.1(i) 1993.5.12

10 1 REGULAR EXPRESSIONS
 11

2 Finite State Machines

We will be making use of mathematical models of physical systems called finite automata,
or finite state machines to recognise whether or not a string is in a particular language.
This section introduces this idea and gives the precise definition of what constitutes a finite
automaton. We look at several variations on the definition (to do with the concept of
determinism) and see that they are equivalent for the purpose of recognising whether or not
a string is in a given language.

2.1 Finite automata

Example of a finite automaton

£ ¢
 ¡ ¢
  ¤ ¢ i  ¥ ¢   ¦
£ £ £
 ¡  
¤  i¥  ¦
States: , , , .
Input symbols: § , ¨ .

 ¡
Transitions: as indicated above.
Start state: .
Accepting state(s): .
 ¦

Slide 10

The key features of this abstract notion of ‘machine’ are listed below and are illustrated
by the example on Slide 10.

© There are only finitely many different states that a finite automaton can be in. In the
ªU« ªi¬ ªk­
example there are four states, labelled , , , and . ª®
© We do not care at all about the internal structure of machine states. All we care about
is which transitions the machine can make between the states. A symbol from some
¯
fixed alphabet is associated with each transition: we think of the elements of ¯
as input symbols. Thus all the possible transitions of the finite automaton can be
specified by giving a finite graph whose vertices are the states and whose edges have
12 2 FINITE STATE MACHINES

°
both a direction and a label (drawn from ). In the example °²±K³U´µ·¶U¸ and the only
possible transitions from state are ¹8º
¹iº™½¼ » ¹¾ and ¹iº™¼½ ¿ ¹kÀÁ
In other words, in state ¹Eºthe machine can either input the symbol and enter state ¶
¹Â¾ ´ ¹À
¹Uà ¼½ ¿ ¹Ã
, or it can input the symbol and enter state . (Note that transitions from a state
back to the same state are allowed: e.g. in the example.)

Ä There is a distinguished start state.1 In the example it is . In the graphical ¹k¾

representation of a finite automaton, the start state is usually indicated by means of
a unlabelled arrow.

Ä The states are partitioned into two kinds: accepting states2 and non-accepting states.
In the graphical representation of a finite automaton, the accepting states are indicated
by double circles round the name of each such state, and the non-accepting states are
indicated using single circles. In the example there is only one accepting state, ; the ¹Ã
other three states are non-accepting. (The two extreme possibilities that all states are
accepting, or that no states are accepting, are allowed; it is also allowed for the start
state to be accepting.)

The reason for the partitioning of the states of a finite automaton into ‘accepting’ and
‘non-accepting’ has to do with the use to which one puts finite automata—namely to recognise
whether or not a string ÅÇÆÈ°ƒÉ
is in a particular language ( subset of ±
). Given we °ƒÉ Å
begin in the start state of the automaton and traverse its graph of transitions, using up the
Å
symbols in in the correct order reading the string from left to right. If we can use up all the
Å Å
symbols in in this way and reach an accepting state, then is in the language ‘accepted’
Å
(or ‘recognised’) by this particular automaton; otherwise is not in that language. This is
summed up on Slide 11.

1
The term initial state is a common synonym for ‘start state’.
2
The term final state is a common synonym for ‘accepting state’.
2.1 Finite automata 13

ÊPËÌÎÍ , language accepted by a finite automaton Ì

consists of all strings Ï over its alphabet of input symbols
satisfying ÐÑ‘Ó ÔÖ Ò Õ Ð with ÐÑ the start state and Ð some accepting
Ð Ñ ÓÔ Ò Õ Ð
state. Here

means, if ϙ×ÙØÛÚ2ØmÜÞÝÝÝÂØ&ß say, that for some states

Ð Úà Ð Ü
à ÝÝÝ à Ð ß ×LÐ (not necessarily all distinct) there are
transitions of the form

Ð ÑâÓáiÔ ã Ð ÚSÓákÔ ä РܑӷákÔ å æææ Ó8ákÔ ç Ð ß ×ÙÐmÝ

èêéâë îì ð^ïï^ð í ññ ìò
N.B.
case : iff ìséâïð ìò
case èêéôó ì²õ ìò : iff ì²õ ìò .

Slide 11

Example 2.1.1. Let ö

be the finite automaton pictured on Slide 10. Using the notation
introduced on Slide 11 we have:

ìÂ÷ïõïõ2ï õ2ð ø ñ ì ù (so úgúgú

û~üÖýÿþ=ö
)
ìÂ÷ ïõïø ï õ2ð õ ñ ì iff ìIé‘ì (so úgû2ú
úüÖ ýÿþ=ö
)
ì ïø ïõï õ2ð õ ñ ì iff ìIé‘ìù (no conclusion about ýƒþ ö
).
In fact in this case

ýÿþ=ö
é 
 contains three consecutive ’s ú 
(For ( ì  é ëó
) corresponds to the state in the process of reading a string in which the

last symbols read were all ’s.) So ú ÿý þ=ö

coincides with the language determined by ýƒþ
the regular expression
séKþ ú
û ñ ú
úgú þ=ú
û ñ
(cf. Slide 8).
14 2 FINITE STATE MACHINES

A non-deterministic finite automaton (NFA),  ,

is specified by
 a finite set !#"$&%'( (of states)
 a finite set ) ( (the alphabet of input symbols)
 for each *,+-!#"$&%' ( and each .+/) ( , a subset
0 (21 *43.65879!#"$&%' ( (the set of states that can be
reached from * with a single transition labelled . )
 an element :( +;!&"$&%'( (the start state)
 a subset <>==%#?@ ( 79A&"$&%'( (of accepting states)

Slide 12

2.2 Determinism, non-determinism, and -transitions B

CED GIJK H GML
Slide 12 gives the formal definition of the notion of finite automaton. Note that the function
F GNLAO
CEDQP G$RTS$U
gives a precise way of specifying the allowed transitions of , via:
.
iff

GVO2W4XZYMX\[] D SO_^ D
The reason for the qualification ‘non-deterministic’ on Slide 12 is because in general,
for each state and each input symbol , we allow the possibilities that
C`DP GaRTSU
there are no, one, or many states that can be reached in a single transition labelled from , S G
corresponding to the cases that has no, one, or many elements. For example, if F
is the NFA pictured on Slide 13, then

CEDQP GbRTcUedgf i.e. in F , no state can be reached from Gb with a transition labelled c ;
CEDQP GbRTS$UedhGiNj i.e. in F , precisely one state can be reached from Gkb with a transition
labelled S ;

CEDQP GlRTS$UedhGlRmGbj i.e. in F , precisely two states can be reached from Gl with a
transition labelled S .
2.2 Determinism, non-determinism, and -transitions n 15

Example of a non-deterministic finite automaton

Input alphabet: okpAqrs .

States, transitions, start state, and accepting states as shown:
v v
tMu v tax v ty v tMz
w w
The language accepted by this automaton is the same as for the
automaton on Slide 10, namely

ok{}|2okpAqrsa~Ea{ p s€
contains three consecutive ’s

Slide 13

When each subset ‚Eƒ…„†$‡Tˆ$‰

has exactly one element we say that Š
is deterministic.
This is a particularly important case and is singled out for definition on Slide 14.

The finite automaton pictured on Slide 10 is deterministic. But note that if we took the
same graph of transitions but insisted that the alphabet of input symbols was ‹ˆ‡TŒN‡TŽ
say,
then we have specified an NFA not a DFA, since for example ‚ƒ…„†‘‡T‰“’I”
. The moral of
this is: when specifying an NFA, as well as giving the graph of state transitions, it is important
to say what is the alphabet of input symbols (because some input symbols may not appear in
the graph at all).

When constructing machines for matching strings with regular expressions (as we will
do in Section 3) it is useful to consider finite state machines exhibiting an ‘internal’ form
of non-determinism in which the machine is allowed to change state without consuming any
n
input symbol. One calls such transitions -transitions and writes them as

†2—– • †N˜š™
This leads to the definition on Slide 15. Note that in an NFA ,
is not an element of the alphabet ›œƒ
of input symbols.
• Š , we always assume that n
16 2 FINITE STATE MACHINES

A deterministic finite automaton (DFA)

¦ Ÿ/§¨¥ , the
is an NFA  with the property that 6
¦ ® for each ž,Ÿ- !¡#¢$¡&£¤k¥ and
finite set ©¥2ª«ž­¬
element—call it ¯¥/ª«ž­¬
°
¦ ® .
contains exactly one

Thus in this case transitions in  are essentially specified by a

next-state function, ¯ ¥ , mapping each (state, input symbol)-pair
ª«ž­¬ ¦°® to the unique state¦ ¯ ¥ ª«ž­¬ ¦6® which can be reached from ž
by a transition labelled :

ž²³´ ± žµ iff žkµ¶·¯ ¥ ª\ž4¬ ¦6®

Slide 14

¸
An NFA with -transitions (NFA ) ¹
is specified by an NFA  together with a binary relation, called
¸
the -transition relation, on the set  A¡&¢$¡&£¤ ¥ . We write

ž ´³ ¹ ž µ
®
to indicate that the pair of states ª«ž­¬ºž µ is in this relation.

¦
Example (with input alphabet = » ¬¼½ ):

± ¹ ža¾ ± ž¿ ± žMÀ ¹ ±

žMÁ žÃ
 ¹ žNÄ Â žÅ  žMÆ ¹ Â

Slide 15
2.3 A subset construction 17

ÇÉÈ\ÊÌË , language accepted by an NFAÍ Ê

consists of all strings Î over the alphabet ÏÑÐ of input symbols
Õ
satisfying ÒMÓÔ Ò with ÒMÓ the initial state and Ò some accepting
Õ
state. Here Ö>× Ö is defined by:

Ò Õ Í ÒØ iff ҏÙÚÒkØ or thereÊ is a sequence Ò ÜÛ Í ÖNÖMÖÒØ of one or

more Ý -transitions in from Ò to Ò Ø

Ò9Õ Þ Ò Ø (for ßQà2Ï Ð ) iff Ò Õ Í Ö>ÜÛ Þ Ö Õ Í Ò Ø

ÒáÕ Þâ Ò Ø (for ß!ãäåà2Ï Ð ) iff Ò Õ Í ÖÉÜÛ Þ Ö Õ Í ÖæÜÛ â Ö Õ Í Ò Ø
and similarly for longer strings

Slide 16

When using an NFA çéè

to accept a string êìëíœî
of input symbols, we are interested in
ê
sequences of transitions in which the symbols in occur in the correct order, but with zero
ï
or more -transitions before or after each one. We write
ð-ò ñ ðMó
to indicate that such a sequence exists from state ð to state ð ó in the NFAç . Then, by definition
ê is accepted by the NFAç è iff ðô ò ñ ð holds for ðô the start state and ð some accepting state:
see Slide 16. For example, for the NFAç on Slide 15, it is not too hard to see that the language
accepted consists of all strings which either contain two consecutive õ ’s or contain two
consecutive ö ’s, i.e. the language determined by the regular expression ÷šõ6øùöú î ÷šõaõø ööú÷šõø öú î .

2.3 A subset construction

Note that every DFA is an NFA (whose transition relation is deterministic) and that every
ç ï
NFA is an NFA (whose -transition relation is empty). It might seem that non-determinism
ï
and -transitions allow a greater range of languages to be characterised as recognisable by a
finite automaton, but this is not so. We can use a construction, called the subset construction,
to convert an NFA çè into a DFA ûüè accepting the same language (at the expense of
increasing the number of states, possibly exponentially). Slide 17 gives an example of this

ó ý þ«ÿMþ
construction. The name ‘subset construction’ refers to the fact that there is one state of ûÑè
ó ýûÑþ«ÿMè þ óè


for each subset
is a transition
of the set
  in

 of states of
just in case

. Given two subsets
è ðó
  , there
consists of all the -states reachable from
18 2 FINITE STATE MACHINES


states  in  via the   relation defined on Slide 16, i.e. such that we can get from  to
 in  via finitely many  -transitions followed by an  -transition followed by finitely many
 -transitions.

Example of the subset construction

  )$*,+  - .

" / / /

0 $#21 0 #!3 3 & 1 0  & 1

!
0  1 0  1 /
%
0  & 1 / 0  & 1

$# " 0 $#!34 0 #!3 0  & 1

1 3 & 1
0  # 34$&51 0  # 3!63'&61 0 '&61
%
0  34 & 1 0  1 0  & 1
'&
0  # 345634$&51 0  # 3!63'&61 0 '&61

Slide 17

By definition, the start state of 78 is the subset of 9;:<$:=>? whose elements are the
states reachable by  -transitions from the start state of  ; and a subset A@B9;:<$:
=>$? is an
accepting state of 7C iff some accepting state of  is an element of  . Thus in the example
on Slide 17 the start state is DEEF'GH'IJGH KL and

!MONQPSRTVU because in  :  F WX   FZXW Y EK\X W [ EK

!MONQPSRT78]U because in 7C : DE F'GH'I GHEKEL WX  DE F'GH$IJGHEKL XW [ DEEKL2^

Indeed, in this case PSR_]Ua`bPSRcedMEdJUa`bPSRT78]U . The fact that  and 7C accept the same
language in this case is no accident, as the Theorem on Slide 18 shows. That slide also gives
the definition of the subset construction in general.
2.3 A subset construction 19

Theorem. For each NFAfhg there is a DFA ijg with the

same alphabet of input symbols and accepting exactly the same
strings as g , i.e. with kml
ijgonOpqkml
grn

Definition of ijg (refer to Slide 12):

sutwvyxzv|{}'~,€E‚|ƒ twv|x†v|{}'Œ‹
p „†…V‡ˆ…Š‰

sŽ ~, €‚ƒ  

p

s ’‘ ~,
…  …”“ in ijg iff …”“wpq•
l|…—–˜™n , where
~, €E‚|ƒ ¡ ‹
• l|…—–˜™n p „ š “ ‡ˆ›œšžu…Ÿlš  š “
5 in gon
sŽ¢ ~£¤€E‚|ƒ ¢  ¡ ‹
p „5š¥‡ f š

sŽ¦¨§J§J{y©v ~, €E‚|ƒ

p
twv|x†v|{} ~, ¦¨§J§J{y©v  ‹
„†…ª ‡†›«š¬­…®l
šQ n

Slide 18

To prove the theorem on Slide 18, given any NFA¯±° we have to show that ²S³_°]´¶µ
²S³_·C°]´ . We split the proof into two halves.

¾ ¿
Proof that ²O³T°]´”¸­²S³_·C°]´ . Consider the case of ¹ first: if ¹»ºŽ²S³_°]´ , then ¼'½ ¯ for
¿
some ºŒÀSÁÂÁÂÃÅÄ«Æ ½ , hence ¼ÇȽ¤ºŽÀSÁÂÁÂÃÅÄœÆ Çw½ and thus ¹žºŸ²S³T·8°]´ . Now given any non-
null string ÉʵÌËÎÍHËzÏÐ Ð ÐyË!Ñ , if É is accepted by ° then there is a sequence of transitions in
° of the form
¾ ¿ ¾ Õ Õ Õ ¾¿
(1) ¼½Ò Ó Í±Ò4Ô Ò4Ö Ñ׺ØÀOÁÁÂÃÅÄ«Æ ½ Ð

Since it is deterministic, feeding Ë«ÍHËzÏÙÐ Ð Ð|Ë!Ñ to ·8° results in the sequence of transitions
ÚÒ Û Ó Ü Í 
Ú4 Õ Õ Õ ÝÚ ÚÞÛ
(2) ¼EÇȽ ÒÛÔ Ò Ö
J Ü Ñ

where Ü ÍßµªàJÇw½®³á¼EÇȽ»âÂËÎÍy´ , Ü ÏOµªàJÇȽʳ Ü Í âˆÏJ´ , etc. By definition of à Çw½ (Slide 18), from
(1) we deduce
¿ Ü Í
Í㺻àJÇw½Ø³á¼EÇw½¥âÂËÎÍy´£µ
¿
so ϶º»àJÇw½Ø³ Ü Í âÂËzÏJ´aµ Ü Ï

Ð Ð Ð
¿
so ўº»àJÇw½Ø³ Ü ÑzäwÍEâÂË!ц´,µ Ü Ñ
20 2 FINITE STATE MACHINES

and hence å
æžçÊèSéÂéÂêÅëœì
íwî (because ïJæžçÊèSéÂéÂêë«ìî ). Therefore (2) shows that ð is accepted
by ñ8ò .

Proof that óOôTñCòVõ—ö­óOôTò]õ . Consider the case of ÷ first: if ÷Aç óOôTñCòVõ , then ø íÈî ç
û
èSéÂéÂêÅëœì íwî and so there is some ïŸçŠø íÈî with ïZçùèSéÂéÂêÅë«ì î , i.e. ø î ú ï\çüèSéÂéêÅë«ì î
and thus ÷ŸçbóOôTò]õ . Now given any non-null string ðuýÿþ
Âþþ!æ , if ð is accepted by
ñCò then there is a sequence of transitions in ñCò of the form (2) with å æŒçbèSéÂéÂêÅëœì íwî ,
i.e. with å
æ containing some ï æBç èSéÂéêÅë«ìî . Now since ï æBç åœæùý íwî ôáåœæ 
Âþ!æ†õ ,
 û
by definition of íÈî there is some ï æ­ç åœæ with ïJæ   ïJæ in ò . Then since
 û
ïJæ ®çBåœæ ý íwî ôcå
æ
Âþ5æHõ , there is some ïJæ\çBåœæ with ïJæ  ïJæ .
Working backwards in this way we can build up a sequence of transitions like (1) until, at the
û
last step, from the fact that ï±çŸåãý íwî ôcø íwî
ÂþÂõ we deduce that ø î  ï . So we get
a sequence of transitions (1) with ïEæ×çÊèSéÂéÂêë«ì î , and hence ð is accepted by ò .

2.4 Summary
The important concepts in Section 2 are those of a deterministic finite automaton (DFA) and
the language of strings that it accepts. Note that if we know that a language ó is of the form
ó ýAóSôTòVõ for some DFA ò , then we have a method for deciding whether or not any given
string ð (over the alphabet of ó ) is in ó or not: begin in the start state of ò and carry out
the sequence of transitions given by reading ð from left to right (at each step the next state is
uniquely determined because ò is deterministic); if the final state reached is accepting, then
ð is in ó , otherwise it is not.
We also introduced other kinds of finite automata (with non-determinism and ÷ -
transitions) and proved that they determine exactly the same class of languages as DFAs.

2.5 Exercises
Exercise 2.5.1. For each of the two languages mentioned in Exercise 1.4.2 find a DFA that
accepts exactly that set of strings.
Exercise 2.5.2. The example of the subset construction given on Slide 17 constructs a DFA
with eight states whose language of accepted strings happens to be óSôcþ4õ . Give a DFA
with the same language of accepted strings, but fewer states. Give an NFA with even fewer
states that does the same job.
Exercise 2.5.3. Given a DFA ò , construct a new DFA ò! with the same alphabet of input
symbol " î and with the property that for all ðùç#"$î , ð is accepted by ò% iff ð is not
accepted by ò .
Exercise 2.5.4. Given two DFAs ò&
Hò' with the same alphabet " of input symbols,
construct a third such DFA ò with the property that ðqç("  is accepted by ò iff it is
accepted by both ò& and ò) . [Hint: take the states of ò to be ordered pairs ôTï
Hï õ of
states with ï ç+*;ì-,$ìê. î and ïSç/*Îì0,$ì
ê1. î$2 .]

Tripos questions 2001.2.1(d) 2000.2.1(b) 1998.2.1(s) 1995.2.19 1992.4.9(a)
 21

3 Regular Languages, I
Slide 19 defines the notion of a regular language, which is a set of strings of the form 35476!8
for some DFA 6 (cf. Slides 11 and 14). The slide also gives the statement of Kleene’s
Theorem, which connects regular languages with the notion of matching strings to regular
expressions introduced in Section 1: the collection of regular languages coincides with the
collection of languages determined by matching strings with regular expressions. The aim of
this section is to prove part (a) of Kleene’s Theorem. We will tackle part (b) in Section 4.

Definition
A language is regular iff it is the set of strings accepted by some
deterministic finite automaton.

Kleene’s Theorem
(a) For any regular expression 9 , :<;=9?> is a regular language
(cf. Slide 8).

(b) Conversely, every regular language is the form :@;=9?> for

some regular expression 9 .

Slide 19

3.1 Finite automata from regular expressions

Given a regular expression A , over an alphabet B say, we wish to construct a DFA 6 with
alphabet of input symbols B and with the property that for each CEDFBHG , C matches A iff C is
accepted by 6 —so that 3$47A8JI&35476!8 .
Note that by the Theorem on Slide 18 it is enough to construct an NFAK@L with the
property 3547LM8NI&3$47A8 . For then we can apply the subset construction to L to obtain a DFA
6 IPOQL with 35476!8RIS3547OTLM8RIS3547LM8RIS3$4UAV8 . Working with finite automata that
are non-deterministic and have W -transitions simplifies the construction of a suitable finite
automaton from A .
Let us fix on a particular alphabet B and from now on only consider finite automata
whose set of input symbols is B . The construction of an NFAK for each regular expression A
over B proceeds by recursion on the syntactic structure of the regular expression, as follows.
22 3 REGULAR LANGUAGES, I

(i) For each atomic form of regular expression, X ( X'Y&Z ), [ , and \ , we give an NFA]
accepting just the strings matching that regular expression.

(ii) Given any NFA] s ^`_ and ^'a , we construct a new NFA] , bcedgfch7^`_ij^'ak with the
property
l l l
hbcedgfch7^`_ij^)amknkNoqpr+srEY h7^`_tk or rEY h7^)amk1uv
l l l l l l
Thus h7wV_s wxakJo hbcedgfch7^`_ij^'amknk when 7h wV_tkNo hU^y_tk and hUwamkJo h7^'ak .

(iii) Given any NFA] s ^`_ and ^'a , we construct a new NFA] , z{fc
|j}~h7^`_ij^)ak with the
property

l l l
hzfc|j}~1h7^`_ij^)aknkNo#pr€_nra@sxr€_Y h7^`_tk and r
a$Y h7^'ak1uv
l l l l l l
Thus h7wV_nwxakNo hzfc
|j}~mhU^y_ij^'aknk when Uh w_tkJo hU^y_tk and h7wxak‚o h7^'ak .

(iv) Given any NFA] ^ , we construct a new NFA] , ƒ~0}„h7^!k with the property

l l
h=ƒ…~0}„h7^#knkoqpr€_jr
avvv†r‡FsˆŠ‰Œ‹ and each r…NY h7^!ktuv
l l l l
Thus h7wŽmkJo hƒ~-}„hU^!knk when Uh wVkNo h7^#k .

Thus starting with step (i) and applying the constructions in steps (ii)–(iv) over and over
again, we eventually build NFA] s with the required property for every regular expression w .
Put more formally, one can prove the statement

for all ˆ+‰y‹ , and for all regular expressions of size Œˆ , there exists an NFA]
l l
^ such that h7wVkNo h7^!k

by mathematical induction on ˆ , using step (i) for the base case and steps (ii)–(iv) for the
induction steps. Here we can take the size of a regular expression to be the number of
occurrences of union ( ‘’s“‘ ), concatenation ( ‘/‘ ), or star ( ‘QŽ ) in it.

l
Step (i) Slide 20 gives NFAs whose languages of accepted strings are respectively
l l h7X?ko
pxXu (any X”YFZ ), h•[kNo%p[u , and h–\kNo—\ .
3.1 Finite automata from regular expressions 23

NFAs for atomic regular expressions

˜™ š ˜›

just accepts the one-symbol string œ

˜™

just accepts the null string, 

˜™

accepts no strings

Slide 20

Step (ii) Given NFAž s Ÿ`  and Ÿ)¡ , the construction of ¢£e¤g¥£¦7Ÿy §jŸ)¡¨ is pictured on
Slide 21. First, renaming states if necessary, we assume that ©ª-«ª=¬1­®Q¯ and ©ª-«ª=¬1­®$° are
disjoint. Then the states of ¢£e¤g¥£¦7Ÿy §jŸ)¡m¨ are all the states in either Ÿy  or Ÿ)¡ , together
with a new state, called ±² say. The start state of ¢ £¤g¥£¦UŸ& §jŸ'¡¨ is this ±² and its accepting
states are all the states that are accepting in either Ÿ—  or Ÿ)¡ . Finally, the transitions of
¢£e¤g¥£¦7Ÿ` §jŸ'¡¨ are given by all those in either Ÿ&  or Ÿ)¡ , together with two new ³ -
transitions out of ±² to the start states of Ÿy  and Ÿ'¡ .
¼
Thus if ´¶µ¸·5¦7Ÿy t¨ , i.e. if we have ¹®Q¯»º ±  for some ± ½µ¿¾$ÀtÀt¬0Áª ®Q¯ , then we
à ¼
get ±²  ž ¹x®Q¯ º ±  showing that ´ µÄ·5¦¢£e¤g¥£¦7Ÿy §jŸ'¡¨ . Similarly for Ÿ)¡ . So
·5¦¢£e¤g¥£¦7Ÿ` §jŸ'¡m¨n¨ contains the union of ·5¦7Ÿ& t¨ and ·$¦7Ÿ'¡¨ . Conversely if ´ is accepted by
¢£e¤0¥£¦7Ÿy m§jŸ)¡¨ , there is a transition sequence ±² ¼ º ± with ±ÅµM¾$ÀtÀt¬-Áª ®Q¯ or ±ÅµM¾5À1Àt¬0Áª ®$° .
Clearly, in either case this transition sequence has to begin with one or other of the ³ -
transitions from ±² , and thereafter we get a transition sequence entirely in one or other of
Ÿ`  or Ÿ)¡ finishing in an acceptable state for that one. So if ´MµM·5¦¢£e¤g¥£ ¦7Ÿ— §jŸ'¡m¨n¨ , then
either ´ÆµE·5¦7Ÿy j¨ or ´EµÆ·5¦7Ÿ)¡m¨ . So we do indeed have

·5¦¢£e¤g¥£¦7Ÿ` §jŸ'¡¨n¨NÇqÈ´ŠÉx´ÆµE·$¦UŸy n¨ or ´EµÊ·$¦7Ÿ'¡¨1ËÌ

24 3 REGULAR LANGUAGES, I

ÍÎÐÏ-ÑÎÓÒ=Ô%ÕVÖmÔØ×VÙ

ÚÛ”Ü Ô Õ
ß
ÝÞ
ß Ú ÛÅà Ô ×

Set of accepting states is union of áÅâmâãnäå Û”Ü and áÅââãnäå ÛÅà .

Slide 21

Step (iii) Given NFAæ s çyè and ç)é , the construction of êëì
íjîïmð7ç&èmñjç)éò is pictured on
Slide 22. First, renaming states if necessary, we assume that óï-îï=ô1õöQ÷ and óï-îï=ô1õö$ø are
disjoint. Then the states of êëì
íjîïmðUç&èñjç'éò are all the states in either çyè or ç'é . The start
state of êëìíjîïðUçyèñjç'émò is the start state of çyè . The accepting states of êëì
íjîïð7çyèñjç)éò
are the accepting states of çé . Finally, the transitions of êëì
íjîïð7çyèñjç)éò are given by all
those in either ç&è or ç)é , together with new ù -transitions from each accepting state of çúè to
the start state of ç)é (only one such new transition is shown in the picture).
Thus if û èQüMý$ð7ç`ètò and û
é@üŠý5ð7ç'éò , there are transition sequences þöQ÷@ÿ
÷
è in ç`è


 
with è ü 5í1ítô ï öQ÷ , and þö$ø ÿ
ø

 
é in ç'é with éHü 5í1ítô ï ö$ø . These combine to yield

þxöQ÷$

ÿ è  æ þö$øH

÷ ø
ÿ é
in êëì
ítîïð7çyèmñjç)éò witnessing the fact that û èjû
é is accepted by ê{ëì
íjîïmð7çyèñjç'éò . Con-

versely, it is not hard to see that every )ü—ý5ðêëìíjîïð7ç—èmñjç)éònò is of this form. For any

transition sequence witnessing the fact that is accepted starts out in the states of çØè but
finishes in the disjoint set of states of çé . At some point in the sequence one of the new
ù -transitions occurs to get from ç&è to ç'é and thus we can split as 

ûèjûé with û è
accepted by çyè and û
é accepted by ç)é . So we do indeed have

ý$ðêëì
íjîïð7ç`èñjç'éònò
 û èjûéû èüÆý$ð7ç`ètò and û
é üÆý$ðUç)éò
3.1 Finite automata from regular expressions 25

!#"%$'&("*),+

-'.0/ " $ 1 -2.43 " )

Set of accepting states is 5 (687 . 3 .

Slide 22

Step (iv) Given an NFA 9;:

, the construction of <>=@?2ACBD:FE
is pictured on Slide 23. The
states of >< =?'ABD:GE
are all those of :
together with a new state, called say. The start state !H I
of<>=@?2ACBJ:GE HKI
is and this is also the only accepting state of <>=?'ABD:FE
. Finally, the transitions
of <>=@?2ACBD:FE
are all those of : L
together with new -transitions from to the start state of H!I :
and from each accepting state of : HMI
to (only one of this latter kind of transition is shown
in the picture).

Clearly, <>=@?2ACBJ:GE L
accepts (since its start state is accepting) and any concatenation of
:
one or more strings accepted by . Conversely, if is accepted by N
, the occurrences <>=@?2ACBD:FE
HKI
of in a transition sequence witnessing this fact allow us to split into the concatenation of N
zero or more strings, each of which is accepted by . So we do indeed have :
O BP<>=@?2ABD:GE8EQRTSVUWSYXZKZKZPS\[^]T_`ba and each S\ced O BD:FEgfZ
26 3 REGULAR LANGUAGES, I

hji8klnmPoqp

r2s t u2v o

t
The only accepting state of
j
h 8
i 
k n
l P
m q
o p is r s .

Slide 23

This completes the proof of part (a) of Kleene’s Theorem (Slide 19). Figure 1 shows how
the step-by-step construction applies in the case of the regular expression wyx{z}|(~gx
to produce
ˆ
an NFA €‚
satisfying ƒ„wJG~†…ƒ„w‡wyxVz |~gxC~
. Of course an automaton with fewer states and
-transitions doing the same job can be crafted by hand. The point of the construction is that
it provides an automatic way of producing automata for any given regular expression.

3.2 Decidability of matching

The proof of part (a) of Kleene’s Theorem provides us with a positive answer to question (a)
Š Š ‰
on Slide 9. In other words, it provides a method that, given any string and regular expression
‰
, decides whether or not matches . The method is:
‹ construct a DFA  satisfying ƒ„wDF~e…Œƒ„w Š ~ ;
‹ 
beginning in ’s start state, carry out the sequence of transitions in 
corresponding
‰
to the string , reaching some state of (because   
is deterministic, there is a
unique such transition sequence);
‹  is acceptingŠ or not: if it is, then ‰^Š ŽƒwDG~…*ƒw Š ~ , so ‰ matches Š ;
check whether
‰‘Ž’ ƒ„wDF~e…Œƒ„w ~ , so ‰ does not match .
otherwise

Note. The subset construction used to convert the NFA€ resulting from steps (i)–(iv) of
Section 3.1 to a DFA produces an exponential blow-up of the number of states. (“” has
3.2 Decidability of matching 27

Step of type (i): • –

Step of type (i): — ˜

Step of type (ii): •V™ — –

š
š ˜
Step of type (iv): ›D•V™}—(œ
š
š –
š
š ˜
š
Step of type (iii): ›y•V™ —œg•
š
š –
– š š
š ˜
š

Figure 1: Steps in constructing an NFA for

š ›y•{™}—(œž•
28 3 REGULAR LANGUAGES, I

Ÿ2  states if ¡ ¢
has .) This makes the method described above very inefficient. (Much more
efficient algorithms exist.)

3.3 Exercises
Exercise 3.3.1. Why can’t the automaton £>¤@¥2¦C§D¡F¨
required in step (iv) of Section 3.1 be
¡
constructed simply by taking , making its start state the only accepting state and adding
©
new -transitions back from each old accepting state to its start state?

« §J¡G¨e¬ « §8§­©>® ¯¨°±±¯K°(¨

Exercise 3.3.2. Work through the steps in Section 3.1 to construct an NFA ª¡ satisfying
. Do the same for some other regular expressions.

Exercise 3.3.3. Show that any finite set of strings is a regular language.

Tripos question 1992.4.9(b) [needs Slide 26 from Section 4]

 29

4 Regular Languages, II
The aim of this section is to prove part (b) of Kleene’s Theorem (Slide 19).

4.1 Regular expressions from finite automata

² ³
Given any DFA , we have to find a regular expression (over the alphabet of input symbols
²
of ) satisfying ´„µJ³,¶·Œ´„µD²F¶
. In fact we do something more general than this, as described
1
in the Lemma on Slide 24. Note that if we can find such regular expressions for any ³¹¸ º ¹»
¼ ½ ½'¾
choice of , , and , then the problem is solved. For taking to be the whole of ¼ ¿>ÀÁ'À@ÂgÃ2Ä
½ Å
and to be the start state, say, then by definition of Ƴ Çg¸ º ¹»
, a string matches this regular È
expression iff there is a transition sequence ÅÊË ÌÎÉ Í ½ ¾ ²
in . As ranges over the finitely ½¾
many accepting states, ½,ÏKÐKÑKÑKÑgÐW½KÒ
say, then we match exactly all the strings accepted by . ²
In other words the regular expression ³ Ǹ º}¹WÓ!ÔÕKÕKÕTÔ ³ Çg¸ º ¹‡Ö
has the property we want for part (b)
of Kleene’s Theorem. (In case ×ηFØ
, i.e. there are no accepting states in , then is ² ´„µD²F¶
empty and so we can use the regular expression .) Ù

Lemma Given an NFA Ú , for each subset ÛÝÜßÞáà‡âà‡ãMäÆå

and each pair of states ænç(æèéêÞjà‡âà8ãMä å , there is a regular
expression ëíKì î}ígï satisfying

ðòñ ë íKì î}í ïóõô÷öÆø é ñ8ù å óWúüû æþÿ ý ú æÆè in Ú with all inter-
mediate states of the sequence
Û
.
in
ðòñ Ú ó ô ðòñ ë ó , where ë ô ë ûû ë  and

ô number of accepting states,
Hence

ë  ô ë gì î}í with Û ô Þjà‡âCà‡ãMä å ,

ô start state,
æ  ô th accepting state.
(In case ×4· Ø , take ³ to be the regular expression Ù .)

Slide 24

Proof of the Lemma on Slide 24. The regular expression ³Æ¹¸ º}¹» can be constructed by induc-
tion on the number of elements in the subset . ¼
1
The lemma works just as well whether
     
is deterministic or non-deterministic; it also works for

NFA s, provided we replace by (cf. Slide 16).
30 4 REGULAR LANGUAGES, II


Base case, is empty. In this case, for each pair of states  , we are looking for a regular
expression to describe the set of strings
"!$# &' (*% )   with no intermediate states +,
So each element of this set is either a single input symbol - (if  ' ( .   holds in / ) or
possibly 0 , in case *12  . If there are no input symbols that take us from  to   in / , we
can simply take ACB
3 574 685:9<;>1 =@? if E1F
D 
0 if G1F .
On the other hand, if there are some such input symbols, -IH,,,J:-LK say, we can take
A #:OOO"#
3 574 685 9 ;M1 =@? -NH #:OOO"# -K # if E1F D 
-NH -K 0 if G1F  .
Induction step. Suppose we have defined the required regular expressions for all subsets
P  PRQTS UWVX
ZY "U+*1
 V[ # \1
of states with elements. If is a subset with elements, choose some element
and consider the -element set P . Then for any pair of states D 7U+
L  V$]_^a`^cbJd"e
, by inductive hypothesis we have already constructed the regular expressions

3 H ;>1 =@? 3 57fh685:gM9i 5ajk  m3 l >; 1 =@? 3 57fn685cgMj i 5aj:k  3"o >; 1 =@? 3 5afnj>gM685ai j 5cjk  and 3 p >; 1 =@? 3 a5fnj>gM685:i 9 5cjk ,

3 ;M1 =@? 3 H # m3 lqr3"o"s ) 3p ,

Consider the regular expression

Clearly every string matching is in the set 3

"!t#  ' (*% )   with all intermediate states in this sequence in u+,
!
Conversely, if is in this set, consider the number of times ! the sequence of transitions
3 ' ( % )   passes through state "U . If this number is zero then VZv qr3 H s (by definition of
H ). Otherwise this number is w*xZS and the sequence splits into wyQ&S pieces: the first piece
is in v qr3ml7s (as the sequence goes from  to the first occurrence of U ), the next w ' S pieces
are in v qz3mo7s (as the sequence goes from one occurrence of mU to the next), and the last! piece
is in v qr3pms (as the sequence goes! from the last occurrence of U to   ). So in this case is in
v3 qz3ml qr3"o"s ) 3pms . So in either case is3 in 3 v qr# 3 3msl .qr3"Soo"s to3p complete the induction step we can define
57f 685 9 to be this regular expression 1 H ) .
4.2 An example
Perhaps an example will help to understand the rather clever argument in Section 4.1. The
example will also demonstrate that we do not have to pursue the inductive construction of the B
3 57f 685:9
regular expression to the bitter end (the base case ): often it is possible to find some of {1
the regular expressions one needs by ad hoc arguments.
4.2 An example 31

Note also that at the inductive steps in the construction of a regular expression for |
}m~
we are free to choose which state to remove from the current state set . A good rule of 
thumb is: choose a state that disconnects the automaton as much as possible.

Example €


‚ ƒ 
 ƒ „
€ €
Direct inspection yields: ‘˜’ ˜‘ ’”
…‡‹†‰€ Œ ˆŽ Š ‚  ‘„ —
Œ –
…•r‹ †Œ ˆŽ€ Š ‚ „
‚ ‘N‘“’ “‘ ’m”  ‚
„ „

Slide 25

As an example, consider the NFA shown on Slide 25. Since the start state is and this ™
š~7› ~7œ8~ œžœ8ŸJ 
is also the only accepting state, the language of accepted strings is that determined by the
regular expression . Choosing to remove state from the state set, we have ¡
(3) ¢¤£zš¥~7› ~7œ ~ œžœ—ŸJ  ¦¨§ ¢¤£zš¥~7› ~7œ8~ œ—ŸJ  © š¥~7› ~7œž œ—ŸJ  £rš› ~7œª«œ—ŸJ  ¦:¬ š¥› ~7œ8~ œ—ŸJ  ¦M­
Direct inspection shows that ¢y£rš~7› œ8~ ¦X§ ¢¤£® ¬ ¦ and ¢y£rš¥~7› œž ¦¯§ y
~7œ8ŸJ  ~7œ—ŸJ  ¢ £® M¬ ° ¦ . To calculate
¢¤£zš¥› œž~7 œ—ŸJ  ¦ , and ¢y£rš¥› ~7œ ~ œ—ŸJ  ¦ , we choose to remove state ± :
¢¤£zš¥› ~7œž œ—ŸJ  ¦¨§ ¢¤£zš¥› ~Mœž   © š› ~Mœ—Ÿ   £zš¥Ÿ>› ~Mœ—Ÿ   ¦:¬ š¥Ÿ>› ~Mœž   ¦
¢¤£zš¥› ~7œ8~ œ—ŸJ  ¦¨§ ¢¤£zš¥› ~Mœ8~   © š› ~Mœ—Ÿ   £zš¥Ÿ>› ~Mœ—Ÿ   ¦:¬ š¥Ÿ>› ~Mœ8~   ¦M­
These regular expressions can all be determined by inspection, as shown on Slide 25. Thus

¢y£rš¥› ~7œž œ—ŸJ  ¦¨§ ¢y£z² © ®“£³² ¦¬ £® ¬ ° ¦‰¦

and it’s not hard to see that this is equal to ¢¤£z² © ®L® ¬M° ¦ ; and

¢y£rš¥› ~7œ8~ œ—ŸJ  ¦¨§ ¢y£´ © ®˜£z² ¦:¬ £®L® ¬>¦¦

32 4 REGULAR LANGUAGES, II

which is equal to µy¶·L··_¸M¹ . Substituting all these values into (3), we get
µ¤¶zº¥¼7»‰¼7½8¼ ½ž¾½—¿JÀ ¹¨ÁFµy¶· ¸ · ¸Mà ¶³Ä  ·L· ¸Mà ¹ ¸ ··L· ¸ ¹JÅ
So · ¸ Â · ¸ Ã ¶zÄ Â ·L· ¸ Ã ¹ ¸ ·L·· ¸
is a regular expression whose matching strings comprise the
language accepted by the NFA on Slide 25. (Clearly, one could simplify this to a smaller, but
equivalent regular expression (in the sense of Slide 8), but we do not bother to do so.)

4.3 Complement and intersection of regular languages

We saw in Section 3.2 that part (a) of Kleene’s Theorem allows us to answer question (a)
on Slide 9. Now that we have proved the other half of the theorem, we can say more about
question (b) on that slide.

Complementation Recall that on page 8 we mentioned that for each regular expression º
Æ
over an alphabet , we can find a regular expression ÇȶrºÉ¹
that determines the complement
of the language determined by : º
µy¶@ÇȶrºÉ¹¹ÊÁÌË"Í
ÎXÆ ¸Ï Í[ÎÑÐ µ¤¶rº ¹JÒÅ
As we now show, this is a consequence of Kleene’s Theorem.

ÕÓ ÔLÖ×cØÚÙ
Û&Ü ÖÝL։ÞmßàâáJãåäçæXèâé"ì ê‰ë Ü ÖÝL։Þmß æ
Ûîí àâáJãåäçæXèâé"ì ê‰ë í æ
Û transitions of ÓÕÔLÖm×åØïÙ = transitions of Ø
Û start state of ÓÕÔLÖ"×åØïÙ = start state of Ø
Ûîðòñ7ñ ÞónÖ àôáMãcäõæXè ì÷ö¥øEù Ü Ö‰ÝL։Þmß æ ú ø[ù û ðòñ>ñ ÞónÖ æ[ü .
Ø is a deterministic finite automaton, then ý is
Provided
accepted by
ÓÕÔLÖ"×åØïÙ iff it is not accepted by Ø :
þ×ÓÕÔLÖ×cØÚÙJÙ ì÷ö ý ù íWÿ ú ý ù û þÏ×cØÚÙ ü .

Slide 26
4.3 Complement and intersection of regular languages 33

Lemma 4.3.1. If is a regular language over alphabet
, then its complement 


  is also regular.
 

Proof. Since is regular, by definition there is a DFA  such that  . Let 
be the DFA constructed from  as indicated on Slide 26. Then 

!
 " is the set
of strings accepted by #$ and hence is regular.

Given a regular expression % , by part (a) of Kleene’s Theorem there is a DFA  such
that &$%'()$* . Then by part (b) of the theorem applied to the DFA  , we can
find a regular expression +,$%- so that .+/$%-012345$*0 . Since

2345$*067

 
 897:

;<
 &$%'=?>

this +/$%- is the regular expression we need for the complement of % .

Note. The construction given on Slide 26 can be applied to a finite automaton  whether or
not it is deterministic. However, for &2#0 to equal <
(
@A
 8 we need
 to be deterministic. See Exercise 4.4.2.

Intersection As another example of the power of Kleene’s Theorem, given regular expres-
sions %'B and %;C we can show the existence of a regular expression $%DB=E(%;CF with the property:

 matches %?BGE(%;C iff  matches %?B and  matches %C .

This can be deduced from the following lemma.

Lemma 4.3.2. If &B and HC are a regular languages over an alphabet
, then their
intersection
N.O :

;:9B and :HC
9BJIKHCML#P

is also regular.

Proof. Since &B and QC are regular languages, there are DFA RB and !C such that
TS1U SV (WXZY'>8[ ). Let \9]_^`$aB>G!C# be the DFA constructed from B and C as on
Slide 27. It is not hard to see that \9]_^b$B>G!C has the property that any :
 is accepted
by \9]_^b$cB#>GC iff it is accepted by both B and C . Thus 9B_I,HC2\9]_^d$cB#>GC50
is a regular language.
34 4 REGULAR LANGUAGES, II

ef1g1hjilk-mion'p

q erfsg6hti*k-mion'p h2u@k-m5u-n?p
states of are all ordered pairs with
u kvawJx0y@x{z;|-}~ u n/vcwJx{y€x{z;|-}r
and
q erfsgshji*k-mion?p ik
alphabet of is the common alphabet of
i n
and
q htu‚k'm#u4n'pƒ h2u‚†k m#u‚n† p erfsg6hti*k4mion'p uDk‡ƒ u‚†k ilk
„… in iff …„ in
u-nƒ u?n† iAn
and …„ in
q efsg6hti k m#i n p h{ˆ }~ mFˆ }r p
start state of is
q htu‚k'm#u4n'p erfsgshji*k-mion?p uDk i*k
accepting in iff accepting in
u-n iAn
and accepting in .

Slide 27

Thus given regular expressions ‰‚Š and ‰;‹ , by part (a) of Kleene’s Theorem we can find
DFA ŒcŠ and Œ!‹ with Ž$‰FV‘Z&Ž$Œ V (’‘”“'•8– ). Then by part (b) of the theorem we can
find a regular expression ‰?ŠG—(‰;‹ so that &Ž$‰?Š0— ‰;‹F˜‘™&Ž2š9›bœbŽ$ŒaŠ•GŒ!‹0 . Thus  matches
‰'Š=—(‰;‹ iff š9›_œ`Ž$ŒaŠ•GŒ!‹ accepts  , iff both ŒŠ and Œ!‹ accept  , iff  matches both ‰?Š and
‰;‹ , as required.

4.4 Exercises
Exercise 4.4.1. Use the construction in Section 4.1 to find a regular expression for the DFA
Œ whose state set is ž;Ÿ€•F“'•8–D  , whose start state is Ÿ , whose only accepting state is – , whose
alphabet of input symbols is ž;¡¢•=£;  , and whose next-state function is given by the following
table. ¤¥§¦
¡ £
Ÿ “ –
“ – “
– – “

Exercise 4.4.2. The construction Œ ¨© ª«¬Ž$Œ* given on Slide 26 applies to both DFA and
NFA; but for Ž2ª3«4¬5Ž$Œ*0 to be the complement of Ž$Œ* we need Œ to be deterministic.
Give an example of an alphabet ­ and a NFA Œ with set of input symbols ­ , such that
± &Ž$Œ=  is not the same set as &Ž2ª«¬#ŽŒ0 .
ž:®­9¯3° ®
4.4 Exercises 35

Exercise 4.4.3. Let ²´³ µV¶¸· ¹º8»5¶@¹4µV¶¸· ¹º=» . Find a complement for ² over the alphabet
¼ ¼
³Z½;¶¿¾=¹;À , i.e. a regular expressions Á˜µ$²'º over the alphabet satisfying Â&µ.Á˜µ²'º0ºH³Z½ÃÅÄ
¼
Æ Âµ²'º8À . Do the same for the alphabet ½;¶¢¾=¹¾=ÇÀ .
» ·;Ã Ä:

Tripos questions 1995.2.20 1994.3.3 1988.2.3 2000.2.7

36 4 REGULAR LANGUAGES, II
 37

5 The Pumping Lemma

In the context of programming languages, a typical example of a regular language (Slide 19)
is the set of all strings of characters which are well-formed tokens (basic keywords, identifiers,
etc) in a particular programming language, Java say. By contrast, the set of all strings which
represent well-formed Java programs is a typical example of a language that is not regular.
Slide 28 gives some simpler examples of non-regular languages. For example, there is no
way to use a search based on matching a regular expression to find all the palindromes in a
piece of text (although of course there are other kinds of algorithm for doing this).

Examples of non-regular languages

È
The set of strings over É¢Ê=ËÌË#ÍJËÎ?Ë4ÏÏ4Ï?Ë#ÐbÑ in which the
parentheses ‘ Ê ’ and ‘ Ì ’ occur well-nested.
È
The set of strings over ɂÍJËÎ?Ë4ÏÏ4Ï-Ë5ÐdÑ which are palindromes,
i.e. which read the same backwards as forwards.
È
ɂ͢ҢÎFÒÓDÔÖÕ×_Ñ

Slide 28

The intuitive reason why the languages listed on Slide 28 are not regular is that a machine
for recognising whether or not any given string is in the language would need infinitely many
different states (whereas a characteristic feature of the machines we have been using is that
they have only finitely many states). For example, to recognise that a string is of the form ؿـÚ5Ù
one would need to remember how many Ø s had been seen before the first Ú is encountered,
requiring countably many states of the form ‘just seen Û Ø s’. This section make this intuitive
argument rigorous and describes a useful way of showing that languages such as these are
not regular.
The fact that a finite automaton does only have finitely many states means that as we look
at longer and longer strings that it accepts, we see a certain kind of repetition—the pumping
lemma property given on Slide 29.
38 5 THE PUMPING LEMMA

The Pumping Lemma

For every regular language Ü , there is a number Ý,Þ´ß satisfying

the pumping lemma property :

all à´á!Ü with âäã;å¢æèçêé6ë2à,ì(Þ7Ý can be expressed as a

concatenation of three strings, à)íïîXðFñ¿îJò , where î6ð , ñ and î¸ò
satisfy:
ó
âôã;å¿æèçêé6ëtñbì(Þ´ß
(i.e. õ÷c ö ø )
ó
âôã;å¿æèçêé6ëtî1ðFñbì(ù7Ý
ó
for all úÖÞû , î6ðñ¿ü¿î¸ò,á!Ü

 ,
(i.e. ý¸þGýbÿ  [but we knew that anyway],
ý þGõ‚ý_ÿ
J
ýJþGõ‚õ‚ýbÿ
 ,
 , etc).
ý¸þGõDõ‚õDý_ÿ

Slide 29

5.1 Proving the Pumping Lemma

Since  is regular, it is equal to the set 
  of strings accepted by some DFA  . Then we
can take the number
mentioned on Slide 29 to be the number of states in  . For suppose
 ÷  þ  ÿ  with 
. If    , then there is a transition sequence as shown at
the top of Slide 30. Then  can be split into three pieces as shown on that slide. Note that
by choice of  and  ,  "!$#%&$õ' ÷ )(+* and  "!$#%&$ý þ0õ" ÷ -,.
. So it just remains
to check that ýJþGõ ý_ÿ/ for all 021 . As shown on the lower half of Slide 30, the string
 the machine  from state 34 back÷ to the same state (since 34 ÷ 365 ). So for any  ,
õ takes
ý¸þGõ ý_ÿ takes us from the initial state 7$8 39 to 3:4 , then  times round the  loop from 3;4 to
itself, and then 
 from 34 to 3 <
=>=>@?A# 8 . Therefore for any 21 , ý þGõ ýbÿ is accepted by
 , i.e. ýJþGõ ýbÿ
 .

Note. In the above construction it is perfectly possible that  ÷ 1 , in which case ý6þ is the
null-string, ø .
5.2 Using the Pumping Lemma 39

If B CFE)G number of states of H , then in

D
I$J G+\ K$LPRMOQ N KSTP>M;Q U ]Y^ KOVXWYW$W P@M:Q Z K;_ [ W$WYW PcM;Q b K$dfeDg)h h:ikjl J
[a` S states
K$suLt m$nYn$vxnow [ can’t
m K yf t E . allSobethedistinct states. So KopqG+Kr for some
above transition sequence looks like
|

I J G+K$LP:z QN { KYp G K;r { :P z QU { K$d}eDg)h h:ikjl J

where
~ S;G €a ‚ƒS„nYn$n‚…p †‡ˆG €‰ ‚…p ` S„n$nYn‚Šr ~ V‹ˆG €‰ ‚'r ` S„n$n$n‚…dƒn

Slide 30

Remark 5.1.1. One consequence of the pumping lemma property of Œ and  is that if there
is any string Ž in Œ of length . , then Œ contains arbitrarily long strings. (We just ‘pump
up’ Ž by increasing  .)
If you did Exercise 3.3.3, you will know that if Πis a finite set of strings then it is regular.
In this case, what is the number  with the property on Slide 29? The answer is that we can
take any  strictly greater than the length of any string in the finite set Œ . Then the Pumping
Lemma property is trivially satisfied because there are no Ž’‘“Œ with ”• –"—$˜™&šŽ›œ+ for
which we have to check the condition!

5.2 Using the Pumping Lemma

The Pumping Lemma (Slide 5.1) says that every regular language has a certain property—
namely that there exists a number  with the pumping lemma property. So to show that
a language Œ is not regular, it suffices to show that no  ž possesses the pumping
lemma property for the language Π. Because the pumping lemma property involves quite a
complicated alternation of quantifiers, it will help to spell out explicitly what is its negation.
This is done on Slide 31. Slide 32 gives some examples.
40 5 THE PUMPING LEMMA

How to use the Pumping Lemma to prove

that a language Ÿ is not regular

For each  ¢¡¤£ , find some ¥§¦Ÿ of length ¡F  so that

©ªª
no matter how ¥ is split into three, ¥®­+¯q°:±²¯ƒ³ ,
«
¨
( ) ªª¬ with ´¶µˆ·…¸Š¹»º½¼¾¯ ° ±À¿
ÁF  and ´¶µˆ·…¸Š¹»º½¼¾±À¿¡¤£ ,

there is some ÂD¡ à for which ¯ ° ±…Ä…¯ ³ is not in Ÿ .

Slide 31

Examples

(i) ŸÅ°Æ;­ ÇaÈ ÉËʲIJÌÄÎÍ"ÂD¡ ÃAÏ is not regular.

[For each ÐÑÓÒ , ÔËÕkÖ6ÕØ×ÙxÚ is of length ÑÐ and has property ( )Û
on Slide 31.]

(ii) Ÿ ³ Æ;­ ÇaÈ ÉË¥¤¦ÜÉËÊÞÝ:ÌOÏßàÍ¥ a palindromeÏ is not regular.

[For each ÐÑÓÒ , ÔËÕkÖ ÔËÕØ×ÙáÚ is of length ÑÐ and has property
( Û ).]

(iii) Ÿxâ Æ;­ ÇaÈ ÉËÊã-Íä prime Ï is not regular.

[For each ÐÑÓÒ , we can find a prime å with åæÜçˆÐ and then
Ô$èœ×éÙëê has length ÑÐ and has property (Û ).]

Slide 32
 5.2 Using the Pumping Lemma 41

Proof of the examples on Slide 32. We use the method on Slide 31.

(i) For any ìÎíïî , consider the string ðòñïóôRõ>ô . It is in öx÷ and has length íøì . We show
that property ( ù ) holds for this ð . For suppose ð ñ ó"ôRõ>ô is split as ð ñ úÞ÷kûËúÀü with
ýþ ÿ
 úƒ÷kû 
¤ì and ýþ ÿ
 û  íòî . Then ú ÷Rû must consist entirely of ó s, so ú ÷ ñòó
and û/ñó say, and hence úÀüáñócô 6õ6ô . Then the case ñ of úÞ÷Rû"úÀü is not in öx÷ since

úÞ÷kû:úAüáñúƒ÷kúÀüáñó  ó ô  õ ô ½ñó ô õ ô

and ócô õ6ô öx÷ because ì"!$#&ñÜ
% ì (since #
ñ
ýþ ÿ û

' í2î ).
(ii) The argument is very similar to that for example (i), but starting with the palindrome
ð ñ’óËôkõ ócô . Once again, the 2ñ( of úÞ÷Rû"úÀü yields a string úÞ÷RúAüñòócô õ óËô which is
not a palindrome (because ì"!)#*ñÜ% ì ).

(iii) Given ìàí î , since there are infinitely many primes + , we can certainly find one satisfying
+-,/.ˆì . I claim that ðñ®ó0 has property ( ù ). For suppose ð+ñ+ó0 is split as ðñ+úƒ÷kûúAü
with
ýþ ÿ
' úƒ÷kû 1
ì and ýþ ÿ
' ûí î . Letting 243ñ 576 ýþ ÿ
' úƒ÷8 and #93ñ 576 ýþ ÿ
' û  , so
that
ýþ ÿ
' úÀü:½ñ)+&!;21!)# , we have

úÞ÷Rû 0  úÀüáñó ó =< 0 > ó 0   ñó  0 @?BA 0  ñó <CA
÷ >D< 0 >BE

Now  #9F+îG  +H!I#G is not prime, because #F+îJ, î (since # ñ

ýþ ÿ

' û  í î ) and
+K!L#K,M.ˆìN!ìàñ¤ìí î (since +J,M.ˆì by choice, and #O
P2QR F # ñ 
ý þ ÿ 

'
 
 ú ÷kû *
ì ).
Therefore úÞ÷kû'
 úAü& öTS when uñ)+*!)# .

Remark 5.2.1. Unfortunately, the method on Slide 31 can’t cope with every non-regular
language. This is because the pumping lemma property is a necessary, but not a sufficient
condition for a language to be regular. In other words there do exist languages ö for which a
number ì/íî can be found satisfying the pumping lemma property on Slide 29, but which
nonetheless, are not regular. Slide 33 gives an example of such an ö .
42 5 THE PUMPING LEMMA

Example of a non-regular language

that satisfies the ‘pumping lemma property’

UWVY[ XZ \]G^`_bacYa;de fMg and h f/ikj

l
\_^`c:a$deLm h fnikj

satisfies the pumping lemma property on Slide 29 with o [pg .

[For any qsrut of length vRw , can take xzyT{J| , }4{ first letter of q ,
xk~{ rest of q .]
U
But is not regular. [See Exercise 5.4.2.]

Slide 33

5.3 Decidability of language equivalence

The proof of the Pumping Lemma provides us with a positive answer to question (c) on
Slide 9. In other words, it provides a method that, given any two regular expressions €y and
€G~ (over the same alphabet  ) decides whether or not the languages they determine are equal,
t1‚€ƒy8„…{Wt†‚'€G~‡„ .
First note that this problem can be reduced to deciding whether or not the set of
strings accepted by any given DFA is empty. For t1‚'€y8„&{ˆt1‚'€G~‡„ iff t†‚'€ƒy8„‰pt1‚'€G~‡„ and
t†‚'€G~‡„Š‰‹t1‚'€ƒyŒ„ . Using the results about complementation and intersection in Section 4.3, we
can reduce the question of whether or not t1‚€y8„N‰st†‚'€G~:„ to the question of whether or not
t1‚€ƒyŒ*‚Ž€G~:„B„‘{’ , since
t1‚'€ƒyŒ„"‰‹t†‚'€G~‡„ iff t1‚€ƒy8„“•”YxKr•–9—Gx-ru
˜ t†‚'€G~‡„=™†{’š
By Kleene’s theorem, given €y and €G~ we can first construct regular expressions €y8›‚7ŽN€G~‡„
and €G~‡›‚7Ž€ƒy8„ , then construct DFAs œJy and œ~ such that t1‚'œJy8„{ t†‚'€ƒyŒ›‚7Ž1€G~:„B„ and
t1‚œ~‡„Q{žt1‚'€G~›‚7ŽN€ƒy=„B„ . Then €Ÿy and €G~ are equivalent iff the languages accepted by œy
and by œ~ are both empty.
The fact that, given any DFA œ , one can decide whether or not t1‚'œ „¡{’ follows from
the Lemma on Slide 34. For then, to check whether or not t1‚œn„ is empty, we just have to
check whether or not any of the finitely many strings of length less than the number of states
of œ is accepted by œ .
5.4 Exercises 43

Lemma If a DFA ¢ accepts any string at all, it accepts one

whose length is less than the number of states in ¢ .

Proof. Suppose ¢ has £ states (so £›¤M¥ ). If ¦¨§@¢ª© is not

empty, then we can find an element of it of shortest length,
«­¬«k®Š¯°¯¯:«b± say (where ²³¤n´ ). Thus there is a transition
sequence
µ¶ ·¹¸ºJ½8»¾ ¼ ¸ ¬ 8½ »Y¾ ¿ ¸ ®ŠÀÀÀ`½ƒ»Y¾ Á ¸ ±Ã³Ä`ŇŇÆBÇÉÈ ¶ .

If ²³¤s£ , then not all the ²OÊP¥ states in this sequence can be
distinct and we can shorten it as on Slide 30. But then we would
obtain a strictly shorter string in ¦9§¢Ë© contradicting the choice of
«­¬«k®Š¯°¯¯:«b± . So we must have ²³Ìs£ .

Slide 34

5.4 Exercises
Exercise 5.4.1. Show that the first language mentioned on Slide 28 is not regular.

Exercise 5.4.2. Show that there is no DFA Í for which Î1ÏÍnÐ is the language on Slide 33.
[Hint: argue by contradiction. If there were such an Í , consider the DFA ÍÒÑ with the same
states as Í , with alphabet of input symbols just consisting of Ó and Ô , with transitions all
those of Í which are labelled by Ó or Ô , with start state ÕGÖ×Ï7ØGÖOÙ8ÚÐ (where Ø°Ö is the start
state of Í ), and with the same accepting states as Í . Show that the language accepted by
ÍÛÑ has to be ÜGÓÝÞÔßݕàYáHâ³ã ä and deduce that no such Í can exist.]

Exercise 5.4.3. Check the claim made on Slide 33 that the language mentioned there satisfies
the pumping lemma property of Slide 29 with åçæÛè .

Tripos questions 2002.2.9 2001.2.7 1999.2.7 1998.2.7 1996.2.1(j) 1996.2.8

1995.2.27 1993.6.12 1991.4.6 1989.6.12
44 5 THE PUMPING LEMMA
 45

6 Grammars
We have seen that regular languages can be specified in terms of finite automata that accept
or reject strings, and equivalently, in terms of patterns, or regular expressions, which strings
are to match. This section briefly introduces an alternative, ‘generative’ way of specifying
languages.

6.1 Context-free grammars

Some production rules for ‘English’ sentences

éƒêëìêë íƒê&î é°ïðbñGêíŸì4òêóð*ôðñGêíŸì
é°ï ðñGêíŸì*î õŸó ìbö°íŸ÷ê*ë ô°ïÞëŸøùóõéê
ôðñGêíŸì*î õŸó ìbö°íŸ÷ê*ë ô°ïÞëŸøùóõéê
õŸóìö°íŸ÷ê&î ú
õŸóìö°íŸ÷ê&îüûŸýÿþ
ëô°ïëøùóõ éƒê î
ëô°ïëøùóõ éƒê î

ë ôïë
õ ñGê íìböGòê&ë ô°ïÞë



õ ñGê íìböGòê&î
õ ñGê íìböGòê&î


kú
ë ôïë›î
ë ôïë›î  
úƒû

òêóð*î 
þúƒû

Slide 35

element alphabet
ú

   !" # 
$ &%('
Slide 35 gives an example of a context-free grammar for generating strings over the seven

ƒúû =þúƒû ú BûŸýÿþ

The elements of the alphabet are called terminals for reasons that will emerge below. The
grammar uses finitely many extra symbols, called non-terminals, namely the eight symbols
õ
)   !  *  '
ñGêíŸìböGòê Œõóìböíƒ÷ê Œëô°ïë Œë ôïëøùó õ éƒê =ôƒðbñ°ê íŸì =éê ëìêëíŸê =é°ï ðñGêíŸì Bòêóð

éêëìŸê ëíƒê
One of these is designated as the start symbol. In this case it is (because we are
interested in generating sentences). Finally, the context-free grammar contains a finite set
,
of production rules, each of which consists of a pair, written
î
, where is one of the
non-terminals and is a string of terminals and non-terminals. In this case there are twelve
+ , +
productions, as shown on the slide.
46 6 GRAMMARS

The idea is that we begin with the start symbol -.#/0.$/$1(.
and use the productions to
continually replace non-terminal symbols by strings. At successive stages in this process we
have a string which may contain both terminals and non-terminals. We choose one of the
non-terminals in the string and a production which has that non-terminal as its left-hand side.
Replacing the non-terminal by the right-hand side of the production we obtain the next string

2
in the sequence, or derivation as it is called. The derivation stops when we obtain a string
containing only terminals. The set of strings over that may be obtained in this way from
the start symbol is by definition the language generated the context-free grammar.

A derivation

-3.$/$0(.$/#13. 4 - 5&67.#1(0 8.$96;:367<.&1(0

4>=(9#0?13@. /#:5&/(A$B9#=#-.;8.$96;:367.#1(0
4C(DFEG/#:5&/AB9#=#-3.H8$.96 :67.#10
4C(DFEG/#:5&/AB9#=#-3. E$ICJG:67.#10
4C(DFEG=(K7<.&1(0?<8. /#:5/HEI3CJL:367.#1(0
4C(DFENMOPQ/#:5&/ E$ICJN:67.#10
4C(DFENMOPSRI3CHEI3CJL:367<.&1(0
4C(DFENMOPSRI3CHEI3CJT=9$0?13@$. /#:5&/AB9#=#-3.
4C(DFENMOPSRI3CHEI3CJLIL/&:5&/AB$9$=#-3.
4C(DFENMOPSRI3CHEI3CJLIL=K7<.&1(0?U8. /#:5&/
4C(DFENMOPSRI3CHEI3CJLIHJ VIW$WG/#:5&/
4C(DFENMOPSRI3CHEI3CJLIHJ VIW$WGXYP
Slide 36

For example, the string

C(DFENMOPZRICZEICJLIHJ
VIW$WGXYP
is in this language, as witnessed by the derivation on Slide 36, in which we have indicated
left-hand sides of production rules by underlining. On the other hand, the string

(4) CDELXYPHI
is not in the language, because there is no derivation from -.#/0.$/$1(. to the string. (Why?)

Remark 6.1.1. The phrase ‘context-free’ refers to the fact that in a derivation we are allowed
to replace an occurrence of a non-terminal by the right-hand side of a production without

[
regard to the strings that occur on either side of the occurrence (its ‘context’). A more general
form of grammar (a ‘type grammar’ in the Chomsky hierarchy—see page 257 of Kozen’s
6.2 Backus-Naur Form 47

book, for example) has productions of the form ^\ ] _ \ _ are arbitrary strings of
where and
terminals and non-terminals. For example a production of the form

`La(bc<d#efg<hd^i3`j ] klm

would allow occurrences of ‘a(bcd#efgUh$d ’ that occur between ‘ ` ’ and ‘ i`3j ’ to be replaced
by ‘klm ’, deleting the surrounding symbols at the same time. This kind of production is not
permitted in a context-free grammar.

Example of Backus-Naur Form (BNF)

Terminals: n oqp r s t u
Non-terminals: vw x$y z n y
Start symbol: zny
Productions:
$v w |{ {~} €n  vw o
x$y |{ {~} qp rs
z n y |{ {~} v w  z n y‚x$y‚z n y t z n y u

Slide 37

6.2 Backus-Naur Form

It is quite likely that the same non-terminal will appear on the left-hand side of several
productions in a context-free grammar. Because of this, it is common to use a more compact
notation for specifying productions, called Backus-Naur Form (BNF), in which all the

] ƒ „~„†…
productions for a given non-terminal are specified together, with the different right-hand
sides being separated by the symbol ‘ ’. BNF also tends to use the symbol ‘ ’ rather than
‘ ’ in the notation for productions. An example of a context-free grammar in BNF is given
on Slide 37. Written out in full, the context-free grammar on this slide has eight productions,
48 6 GRAMMARS

namely:
‡ ˆŠ‰ ‹
‡ˆŠ‰ ‡ˆŒ
Ž ‰ 
Ž ‰ 
Ž ‰ ‘
’‹Ž ‰ ‡ˆ
’‹Ž ‰ ’ ‹ ŽSŽ;’ ‹ Ž
’‹Ž ‰ “ ’ ‹ Ž”
The language generated by this grammar is supposed to represent certain arithmetic expres-
sions. For example

(5)
‹T•“–‹ Œ— ”
is in the language, but

(6)
‹T•“–‹ ” Œ˜
is not. (See Exercise 6.4.2.)

™š›œ›€ž$Ÿ¡ £¢¤
A context-free grammar for the language

Terminals:
š œ
Non-terminal: ¥
Start symbol: ¥
Productions: ¥§¦|¦~¨ª© žš ¥ œ

Slide 38
6.3 Regular grammars 49

6.3 Regular grammars

« ¬ ¬ «
A language over an alphabet is context-free iff is the set of strings generated by

generates the language ­<®#¯°±¯³²µ´·¶¹¸#º

some context-free grammar (with set of terminals ). The context-free grammar on Slide 38
. We saw in Section 5.2 that this is not a regular
language. So the class of context-free languages is not the same as the class of regular
languages. Nevertheless, as Slide 39 points out, every regular language is context-free. For

symbol to a string in ¬¼»

the grammar defined on that slide clearly has the property that derivations from the start
must be of the form of a finite number of productions of the first
kind followed by a single production of the second kind, i.e.

½<¾À¿ ®ÁÃÂÁ ¿ ®ÁÄ®#űÂUÅ ¿ ƝƝÆ(¿ ®ÁÄ®#ÅÈǝǝÇî ¯  ¯ ¿ ®ÁÄ®#ÅÉǝǝÇî ¯

where in Ê the following transition sequence holds

½<¾ Í UË ¿ Ì Â Á Í Ë
¿ Î Æ ƝÆÏ~Í Ë
Í ¿ Ð Â ^¯ тÒÏÓÄÓÄÔÖÕ× ¾ Ç
Thus a string is in the language generated by the grammar iff it is accepted by Ê .

Every regular language is context-free

Given a DFA Ø , the set ÙGÚÛØÝÜ of strings accepted by Ø can be

generated by the following context-free grammar:

set of terminals = ÞNß

set of non-terminals = àµáâ#áã<ä ß
start symbol = start state of Ø
çå æ èåé å·ëæ ê å(é Ø
productions of two kinds:

åçæ ì whenever
whenever
åîíðïQñ ñ ãÃòÈá ß
in

Slide 39
 50 6 GRAMMARS

Definition A context-free grammar is regular iff all its

productions are of the form
ó€ô ÷õ ö
or
óøô õ
where
õ is a string of terminals and
ó and
ö are non-terminals.

Theorem

(a) Every language generated by a regular grammar is a

regular language (i.e. is the set of strings accepted by some
DFA).
(b) Every regular language can be generated by a regular
grammar.

Slide 40

It is possible to single out context-free grammars of a special form, called regular (or
right linear), which do generate regular languages. The definition is on Slide 40. Indeed, as
the theorem on that slide states, this type of grammar generates all possible regular languages.

proved, because the context-free grammar generating ù¼úüû£ý

Proof of the Theorem on Slide 40. First note that part (b) of the theorem has already been
on Slide 39 is a regular grammar
(of a special kind).
To prove part (a), given a regular grammar we have to construct a DFA whose set û
of accepted strings coincides with the strings generated by the grammar. By the Subset

û
Construction (Theorem on Slide 18), it is enough to construct an NFA with this property. þ
This makes the task much easier. We take the states of to be the non-terminals, augmented
by some extra states described below. Of course the alphabet of input symbols of should û
transitions and the accepting states of û
be the set of terminal symbols of the grammar. The start state is the start symbol. Finally, the
are defined as follows.
 with 
 úý , say  "! with
# $ #&% 
(i) For each production of the form
, we add fresh states
ÿ


 ÿ
ÿ'("ÿ)("ÿ*(+("ÿ,!
-. to the automaton and transitions
ÿ% /10 2ÿ 3% /54 ,ÿ *6% /7 888Û,ÿ !
-.3%:/5% >ÿ9  
(ii) For each production of the form ; ÿ ÿ  with  2 ú <ý >= , i.e. with ?A@ , we add an
@ -transition
ÿ %þ ÿ  
 6.4 Exercises 51

(iii) For each production of the form DB CFE with GH5I

J2KLNMEPORQTS , say E&UWVPXV
YZZZ V\[ with ]
QTS ,
]
we add fresh states B'X^B1Y_^B`^ZZZ^B5[ to the automaton and transitions
Bc aCF b BX3c aCF
d B1Yec a+CF
f B`hgggica,c CF
j B,[NZ
Moreover we make the state B1[ accepting.
(iv) For each production of the form BkC E with GH5I
J2KLPMElOmUon , i.e. with EpU$q , we do not add
in any new states or transitions, but we do make B an accepting state.
If we have a transition sequence in r of the form st
v u B with BAw xiy+yzH|{lK t , we
can divide it up into pieces according to where non-terminals occur and then convert each
piece into a use of one of the production rules, thereby forming a derivation of E in the
grammar. Reversing this process, every derivation of a string of terminals can be converted
into a transition sequence in the automaton from the start state to an accepting state. Thus
}
this NFA does indeed accept exactly the set of strings generated by the given regular
grammar.

6.4 Exercises
Exercise 6.4.1. Why is the string (4) not in the language generated by the context-free
grammar in Section 6.1?
Exercise 6.4.2. Give a derivation showing that (5) is in the language generated by the
context-free grammar on Slide 37. Prove that (6) is not in that language. [Hint: show that
E
if is a string of terminals and non-terminals occurring in a derivation of this grammar and
~ E €~ \~~ \~~‚~
that ‘ ’ occurs in , then it does so in a substring of the form , or , or , etc., where is 
either or .] ƒ „)…
† V^z‡1ˆ
Exercise 6.4.3. Give a context-free grammar generating all the palindromes over the alphabet
(cf. Slide 28).

alphabet .
† V‰^z‡_ˆ
Exercise 6.4.4. Give a context-free grammar generating all the regular expressions over the

Exercise 6.4.5. Using the construction given in the proof of part (a) of the Theorem on
Slide 40, convert the regular grammar with start symbol and productions B)Š
B,ŠiC‹q
B,ŠiC V
‡B,Š
B,ŠiC ŒBX
B2XC V
‡
}
into an NFA whose language is that generated by the grammar.
Exercise 6.4.6. Is the language generated by the context-free grammar on Slide 35 a regular
language? What about the one on Slide 37?

Tripos questions 2002.2.1(d) 1997.2.7 1996.2.1(k) 1994.4.3 1991.3.8

1990.6.10
52 6 GRAMMARS