printable version
Review A: Regular expressions & automata
Section A.1:
[1]
[2]
[3]
[4]
Section A.2:
[1]
[2]
[3]
Problem A.1.1.
Write a regular expression for each of the following
concepts.
a. 
strings starting with a digit

b. 
strings containing only alphabetic letters

Problem A.1.2.
Write a regular expression for each of the following
concepts.
a. 
strings containing only alphabetic letters and that start with
the letter c

b. 
strings that containing only digits, but which don't start
with 0

a. 
c[azAZ]*

b. 
[19][09]*

Problem A.1.3.
Write a regular expression that describes strings containing
the lowercase letter e followed by a digit, with
possibly some intervening spaces. Examples include
3e8
,
the 100K
,
and e2
, but not e5
.
.*e *[09].* (There is a space between the e
and the asterisk.)
Problem A.1.4.
Write a regular expression that describes all words of lowercase
letters that begin with w and contain an r. Examples
include weird, word, wrong, and wear, but
not awkward, warweary, or www.hendrix.edu.
(The latter two are bad because they contain characters that are not
lowercase letters.)
w[az]*r[az]*
Problem A.2.1.
Design a finite automaton that accepts strings of
a's and b's that end with two
a's.
Problem A.2.2.
Design a finite automaton that accepts strings of
a's and b's that begin and end with the same
letter.
Problem A.2.3.
Design a finite automaton that accepts strings of
a's and b's that include the substring
abaa.