Computer Science 456/656: Automata and Formal Languages
Spring 1999
Homework Assignment 1.
Due January 20, 1999
You may discuss this assignment with other students in the class, or other
persons. But you must actually write the assignment in your own hand.
You must turn in the homework on letter-sized paper, with your name at the
top of each page. Use pen or pencil, any color.
Do not write your homework as a computer file and turn
in a printout.
-
Work problem 1.34 on page 34 of your textbook.
-
Work problem 1.45(a) on page 35 of your textbook.
-
Work problem 2.41 on page 66 of your textbook.
-
Work problem 2.42 on page 67 of your textbook.
-
Let
L be the language over
{a,b} defined recursively as
follows:
-
The empty string is a member of
L .
-
If
x
is a member of
L, then
axb
is a member of
L.
-
If
x and
y
are both members of L,
then xy is a member of
L.
-
Nothing is in
L unless it can be obtained by the previous statements.
Use structural induction to prove that, if
x
is a member of
L,
and if p is any
prefix of x , then
p
has at least as many a's
as b's.
Back to
Course Page