• Home

test

*

Construction Techniques

*

Section 3.1 Inductively Defined Sets

To define a set S inductively is to do three things:

Basis: Specify one or more elements of S.

Induction: Specify one or more rules to construct elements of S from existing elements of S.

Closure: Specify that no other elements are in S (always assumed).

Note: The basis elements and the induction rules are called constructors.

Example 1. Find an inductive definition for S = {3, 16, 29, 42, …}.

Solution: Basis: 3  S.

Induction: If x  S then x + 13  S.

The constructors are 3 and the operation of adding 13. Also, without closure, many sets

would satisfy the basis and induction rule. e.g., 3  Z and x  Z implies x + 13  Z.

Example 2. Find an inductive definition for S = {3, 4, 5, 8, 9, 12, 16, 17, 20, 24, 33,…}.

Solution: To simplify things we might try to “divide and conquer” by writing S as the union

of more familiar sets as follows:

S = {3, 5, 9, 17, 33, …}  {4, 8, 12, 16, 20, 24, …}.

Basis: 3, 4  S.

Induction: If x  S then (if x is odd then 2x – 1  S else x + 4  S).

Example 3. Describe the set S defined inductively as follows:

Basis: 2  S;

Induction: x  S implies x  3  S.

Solution: S = {2, 5, 8, 11, … }  {–1, –4, –7, –10, … }.

*

*

Example 4. Find an inductive definition for S = {L, ac, aacc, aaaccc, …} = {ancn | n  N}.

Solution: Basis: L  S.

Induction: If x  S then axc  S.

Example 5. Find an inductive definition for S = {an+1bcn | n  N}.

Solution: Basis: ab  S.

Induction: If x  S then axc  S.

Example 6. Describe the set S defined by: Basis: a, b  S

Induction: x  S implies ƒ(x)  S.

Solution: S = {a, ƒ(a), ƒ(ƒ(a)), …}  {b, ƒ(b), ƒ(ƒ(b)), …}, which could also be written as

S = {ƒn(a) | n  N}  {ƒn(b) | n  N} = {ƒn(x) | x  {a, b} and n  N}.

Example 7. Describe the set S defined by: Basis:  0   S

Induction: x  S implies cons(1, x)  S.

Solution: S = { 0 ,  1, 0 , 1, 1, 0 , …}.

Infix notation

cons(h, t) = h :: t. Associate to the right. e.g., x :: y :: z = x :: (y :: z).

Example 8. Find an inductive definition for S = { ,  a, b , a, b, a, b , …}.

Solution: Basis:    S.

Induction: x  S implies a :: b :: x  S.

Example 9. Find an inductive definition for S = { ,    ,      , …}.

Solution: Basis:    S.

Induction: x  S implies x ::    S.

*

*

Notation for Binary Trees

Let t(L, x, R) denote the tree with root x, left subtree L, and right subtree R. Let   denote the

empty binary tree. If T = t(L, x, R), then root(T) = x, left(T) = L, and right(T) = R.

Example 10. Describe the set S defined inductively as follows:

Basis: t( , •,  )  S.

Induction: T  S implies t(T, •, t( , •,  ))  S.

Solution (picture): The first few trees constructed from the definition are pictured as follows:

Example 11. Find an inductive definition for the set S of binary trees indicated by the

following picture.

Solution: Basis: t( , •,  )  S.

Induction: T  S implies t(t(left(T), •,  ), •, t( , •, right(T)))  S.

and so on.

and so on.

*

*

Example 12. Find an inductive definition for the set S = {a}*  N.

Solution: Basis: (, 0)  S.

Induction: (s, n)  S implies (as, n), (s, n + 1)  S.

Example 13. Find an inductive definition for the set S = {(x, –y) | x, y  N and x ≥ y}.

Solution: To get an idea about S we can write out a few tuples:

(0, 0), (1, 0), (1, –1), (2, 0), (2, –1), (2, –2), and so on.

Quiz (2 minutes). Try to find a solution that does not construct repeated elements.

Solution: We might use two separate rules. One rule to construct the diagonal points and one

rule to construct horizontal lines that start at the diagonal points.

Basis: (0, 0)  S.

Induction: 1. (x, y)  S implies (x + 1, y)  S.

2. (x, –x)  S implies (x + 1, – (x + 1))  S.

We can also get an idea about S by graphing a few points,

as indicated in the picture.

One solution can be written as follows:

Basis: (0, 0)  S.

Induction: (x, y)  S implies (x + 1, y), (x + 1, y – 1)  S.

Notice that this definition constructs some repeated points.

For example, (2, –1) is constructed twice.

*

*

Section 3.2 Recursively Defined Functions and Procedures

A function ƒ is recursively defined if at least one value ƒ(x) is defined in terms of another

value ƒ(y), where x ≠ y. Similarly, a procedure P is recursively defined if the action of P(x)

is defined in terms of another action P(y), where x ≠ y.

Technique for recursive definitions when the argument domain is inductively defined.

1. Specify a value ƒ(x), or action P(x), for each basis element x of S.

2. Specify rules that, for each inductively defined element x in S, define the value ƒ(x), or

action P(x), in terms of previously defined values of ƒ, or actions of P.

Example 1. Find a recursive definition for the function ƒ : N  N defined by

ƒ(n) = 0 + 3 + 6 + … + 3n.

Solution: Notice that N is an inductively defined set: 0  N; n  N implies n + 1  N. So

we need to give ƒ(0) a value in N and we need to define ƒ(n + 1) in terms of ƒ(n). The given

definition of ƒ tells us to set ƒ(0) = 0. To discover a definition for ƒ(n + 1) we can write

ƒ(n + 1) = (0 + 3 + 6 + … + 3n) + 3(n + 1)

= ƒ(n) + 3(n + 1).

So we have a recursive definition for ƒ:

ƒ(0) = 0

ƒ(n + 1) = ƒ(n) + 3(n + 1).

Two alternative definitions:

  • ƒ(0) = 0

ƒ(n) = ƒ(n – 1) + 3n (n > 0).

  • (if-then-else form): ƒ(n) = if n = 0 then 0 else ƒ(n – 1) + 3n.

*

*

Example 2. Find a recursive definition for cat : A*  A*  A* defined by cat(s, t) = st.

Solution: Notice that A* is inductively defined: L  A*; a  A and x  A* imply ax  A*,

where ax denotes the string version of cons. We can define cat recursively using the first

argument. The definition of cat gives cat(L, t) = Lt = t. For the recursive part we can write

cat(ax, t) = axt = a(xt) = acat(x, t). So we have a definition:

cat(L, t) = t

cat(ax, t) = acat(x, t).

If-then-else form using head and tail for strings:

cat(s, t) = if s = L then t else head(s)cat(tail(s), t).

Example 3. Find a definition for ƒ : lists(Q)  Q defined by ƒ(x1, …, xn) = x1 + … + xn.

Solution: The set lists(Q) is inductively defined:

   lists(Q); h  Q and t  lists(Q) imply h :: t  lists(Q).

To discover a recursive definition, we can use the definition of ƒ as follows:

ƒ(x1, …, xn) = x1 + … + xn

= x1 + (x2 + … + xn)

= x1 + ƒ(x2, …, xn)

= head(x1, …, xn) + ƒ(tail(x1, …, xn).

So if we let ƒ( ) = 0, we have a recursive definition:

ƒ( ) = 0

ƒ(h :: t) = h + ƒ(t).

If-then-else form: ƒ(L) = if L =   then 0 else head(L) + ƒ(tail(L)).

*

*

Example 4. Given ƒ : N  N defined recursively by

ƒ(0) = 0

ƒ(1) = 0

ƒ(x + 2) = 1 + ƒ(x).

The if-then-else form for ƒ can be written as follows:

ƒ(x) = if x = 0 or x = 1 then 0 else 1 + ƒ(x – 2).

What does ƒ do?

Answer: List a few values to get the idea. For example,

map(ƒ, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) = 0, 0, 1, 1, 2, 2, 3, 3, 4, 4.

So ƒ(x) returns the floor of x/2. i.e., ƒ(x) = x/2.

Example 5. Find a recursive definition for ƒ : lists(Q)  Q defined by

ƒ(x1, …, xn) = x1x2 + x2x3 + … + xn–1xn.

Solution: Let ƒ( ) = 0 and ƒ(x) = 0. Then for n ≥ 2 we can write

ƒ(x1, …, xn) = x1x2 + (x2x3 + … + xn–1xn) = x1x2 + ƒ(x2, …, xn).

So we have the following recursive definition.

ƒ( ) = 0

ƒ(x) = 0

ƒ(h :: t) = h · head(t) + ƒ(t).

If-then-else form:

ƒ(L) = if L =   or tail(L) =   then 0 else head(L) · head(tail(L)) + ƒ(tail(L)).

*

*

Example 6. Find a recursive definition for isin : A  lists(A)  {true, false} where isin(x, L)

means that x is in the list L.

Solution: isin(x,  ) = false

isin(x, x :: t) = true

isin(x, h :: t) = isin(x, t).

If-then-else form:

isin(x, L) = if L =   then false else if x = head(L) then true else isin(x, tail(L)).

Example 7. Find a recursive definition for sub : lists(A)  lists(A)  {true, false} where

sub(L, M) means the elements of L are elements of M.

Solution: sub( , M) = true

sub(h :: t, M) = if isin(h, M) then sub(t, M) else false.

If-then-else form:

sub(L, M) = if L =   then true else if isin(head(L), M) then sub(tail(L), M) else false.

Example 8. Find a recursive definition for intree : Q  binSearchTrees(Q)  {true, false}

where intree(x, T) means x is in the binary search tree T.

Solution: intree(x,  ) = false

intree(x, tree(L, x, R)) = true

intree(x, tree(L, y, R)) = if x < y then intree(x, L) else intree(x, R).

If-then-else form: intree(x, T) = if T =   then false

else if x = root(T) then true

else if x < root(T) then intree(x, left(T))

else intree(x, right(T)).

*

*

Graph Traversals

A graph traversal starts at some vertex v and visits all the vertices on the paths that start at v. If a vertex has al­ready been visited, it is not visited again. It follows that any traversal of a connected graph will visit all its vertices. A depth-first traversal starts by visiting v. Then it calls itself on each vertex adjacent to v that has not already been visited. Here’s a recursive procedure to do a depth-first traversal that starts at vertex v.

D(v): if v has not been visited then

visit(v);

for each edge from v to x do D(x) od

fi

Quiz (1 minute). Find a depth-first traversal of the pictured graph that starts at F.

One answer: F, H, G, D, B, A, C, E.

Quiz (1 minute). Find a depth-first traversal of the pictured graph that starts at E.

One answer: E, D, F, H, G, A, C, B.

F

D

E

B

C

A

G

H

*

*

Traversing Binary Trees

The three standard procedures to traverse a binary tree are defined recursively as follows:

preorder(T): if T ≠   then visit root(T); preorder(left(T)); preorder(right(T)) fi.

inorder(T): if T ≠   then inorder(left(T)); visit root(T); inorder(right(T)) fi

postorder(T): if T ≠   then postorder(left(T)); postorder(right(T)); visit root(T) fi.

Example 9. Traverse the following tree in each of the three orders.

Solution:

Preorder: a b c d e

Inorder: b a d c e

Postorder: b d e c a

Example 10. Find a recursive definition for post : binaryTrees(A)  lists(A) where post(T) is

the list of nodes from a postorder traversal of T.

Solution: post( ) =  

post(tree(L, x, R)) = cat(post(L), cat(post(R),  x ))

where cat concatenates two lists and can be defined by,

cat( , L) = L

cat(h :: t, L) = h :: cat(t, L).

a

b

c

d

e

*

*

Example 11. Find a recursive definition for ƒ : binaryTrees(Q)  Q where ƒ(T) is the sum

of the nodes in T.

Solution: ƒ( ) = 0

ƒ(tree(L, x, R)) = x + ƒ(L) + ƒ(R).

Infinite Sequences

We can construct recursive definitions for infinite sequences by defining a value ƒ(x) in

terms of x and ƒ(y) for some value y in the sequence.

Example 12. Suppose we want to represent the infinite sequence ƒ(x) = x, x2, x4, x8, … .

Solution: Use the definition to discover a solution as follows:

ƒ(x) = x, x2, x4, x8, …  = x :: x2, x4, x8, …  = x :: ƒ(x2).

So define ƒ(x) = x :: ƒ(x2).

Example 13. What sequence is defined by g(x, k) = xk :: g(x, k + 1)?

Answer: g(x, k) = xk :: g(x, k + 1) = xk :: xk+1 :: g(x, k + 2) =… = xk, xk+1, xk+2, … .

Example 14. How do we obtain the sequence x, x3, x5, x7, … ?

A Solution. Define ƒ(x) = h(x, 1), where h(x, k) = xk :: h(x, k + 2).

Example 15. How do we obtain the sequence 1, x2, x4, x6, x8, … ?

A Solution: Use h(x, 0) from Example 14.

*

*

Section 3.3 Computer Science: Grammars

A grammar is a finite set of rules, called productions, that are used to describe the strings of

a language.

Notational Example. The productions take the form a  b, where a and b are strings over

an alphabet of terminals and nonterminals. Read a  b as, “a produces b,” “a derives b,”

or “a is replaced by b.” The following four expressions are productions for a grammar.

Terminals: {a, b}, the alphabet of the language.

Nonterminals: {S, B}, the grammar symbols (uppercase letters), disjoint from terminals.

Start symbol: S, a specified nonterminal alone on the left side of some production.

Sentential form: any string of terminals and/or nonterminals.

Derivation: a transformation of sentential forms by means of productions as

follows: If xay is a sentential form and a  b is a production, then the replacement

of a by b in xay to obtain xby is a derivation step, which we denote by xay  xby.

Example Derivation: S  aSB  aaSBB  aaBB  aabBB  aabbB  aabbb.

This is a leftmost derivation, where each step replaces the leftmost nonterminal.

The symbol + means one or more steps and * means zero or more steps. So we could

write S + aabbb or S * aabbb or aSB * aSB, and so on.

S  aSB

S  L

B  bB

B  b.

Alternative Short Form

S  aSB | L

B  bB | b.

*

*

The Language of a Grammar

The language of a grammar is the set of terminal strings derived from the start symbol.

Example. Can we find the language of the grammar S  aSB | L and B  bB | b?

Solution: Examine some derivations to see if a pattern emerges.

S  L

S  aSB  aB  ab

S  aSB  aB  abB  abbB  abbb

S  aSB  aaSBB  aaBB  aabB  aabb

S  aSB  aaSBB  aaBB  aabBB aabbBB  aabbbB aabbbb.

So we have a pretty good idea that the language of the grammar is {anbn+k | n, k  N}.

Quiz (1 minute). Describe the language of the grammar S  a | bcS.

Solution: {(bc)na | n  N}.

Construction of Grammars

Example. Find a grammar for {anb | n  N}.

Solution: We need to derive any string of a’s followed by b. The production S  aS can be

used to derive strings of a’s. The production S  b will stop the derivation and produce the

desired string ending with b. So a grammar for the language is S  aS | b.

Quiz (1 minute). Find a grammar for {ban | n  N}.

Solution: S  Sa | b.

Quiz (1 minute). Find a grammar for {(ab)n | n  N}.

Solution: S  Sab | L or S  abS | L.

*

Rules for Combining Grammars

Let L and M be two languages with grammars that have start symbols A and B, respectively,

and with disjoint sets of nonterminals. Then the following rules apply.

  • L  M has a grammar starting with S  A | B.
  • LM has a grammar starting with S  AB.
  • L* has a grammar starting with S  AS | L.

Example. Find a grammar for {ambmcn | m, n  N}.

Solution: The language is the product LM, where L = {ambm | m  N} and M = {cn | n  N}.

So a grammar for LM can be written in terms of grammars for L and M as follows.

S  AB

A  aAb | L

B cB | L.

Example. Find a grammar for the set Odd, of odd decimal numerals with no leading zeros,

where, for example, 305  Odd, but 0305  Odd.

Solution: Notice that Odd can be written in the form Odd = (PD*)*O, where

O = {1, 3, 5, 7, 9}, P = {1, 2, 3, 4, 5, 6, 7, 8, 9}, and D = {0}  P.

Grammars for O, P, and D can be written with start symbols A, B, and C as:

A  1 | 3 | 5 | 7 | 9, B  A | 2 | 4 | 6 | 8, and C  B | 0.

Grammars for D* and PD* and (PD*)* can be written with start symbols E, F, and G as:

E  CE | L, F  BE, and G  FG | L.

So a grammar for Odd with start symbol S is

S  GA.

*

Example. Find a grammar for the language L defined inductively by,

Basis: a, b, c  L.

Induction: If x, y  L then ƒ(x), g(x, y)  L.

Solution: We can get some idea about L by listing some of its strings.

a, b, c, ƒ(a), ƒ(b), …, g(a, a), …, g(ƒ(a), ƒ(a)), …, ƒ(g(b, c)), …, g(ƒ(a), g(b, ƒ(c))), …

So L is the set of all algebraic expressions made up from the letters a, b, c, and the function

symbols ƒ and g of arities 1 and 2, respectively. A grammar for L can be written as

S  a | b | c | ƒ(S) | g(S, S).

For example, a leftmost derivation of g(ƒ(a), g(b, ƒ(c))) can be written as

S  g(S, S)  g(ƒ(S), S)  g(ƒ(a), S)  g(ƒ(a), g(S, S))

 g(ƒ(a), g(b, S))  g(ƒ(a), g(b, ƒ(S)))  g(ƒ(a), g(b, ƒ(c))).

A Parse Tree is a tree that represents a derivation. The root is the

start symbol and the children of a nonterminal node are the symbols

(terminals, nonterminals, or L) on the right side of the production

used in the derivation step that replaces that node.

Example. The tree shown in the picture is the parse tree for the

following derivation:

S  g(S, S)  g(ƒ(S), S)  g(ƒ(a), S)  g(ƒ(a), b).

S

g ( S , S )

ƒ ( S ) b

a

*

*

Example. Is the grammar S  SaS | b ambiguous?

Solution: Yes. For example, the string babab has two distinct

leftmost derivations:

S  SaS  SaSaS  baSaS  babaS  babab.

S  SaS  baS baSaS  babaS  babab.

The parse trees for the derivations are pictured.

Ambiguous Grammar: Means there is at least one string with two distinct parse trees,

or equivalently, two distinct leftmost derivations or two distinct rightmost derivations.

Quiz (2 minutes). Show that the grammar S  abS | Sab | c is ambiguous.

Solution: The string abcab has two distinct leftmost derivations:

S  abS  abSab  abcab and S  Sab  abSab  abcab.

Unambiguous Grammar: Sometimes one can find a grammar that is not ambiguous for

the language of an ambiguous grammar.

Example. The previous example showed S  SaS | b is ambiguous. The language of the

grammar is {b, bab, babab, …}. Another grammar for the language is S  baS | b. It is

unambiguous because S produces either baS or b, which can’t derive the same string.

Example. The previous quiz showed S  c | abS | Sab is ambiguous. Its language is

{(ab)mc(ab)n | m, n  N}. Another grammar for the language is

S  abS | cT and T  abT | L.

It is unambiguous because S produces either abS or cT, which can’t derive the same string.

Similarly, T produces either abT or L, which can’t derive the same string.

S

S a S

S a S

b

b

b

S

S a S

S a S

b

b

b

*

test

*

Elementary Notions and Notations

*

Section 1.1 A Proof Primer

A proof is a demonstration that some statement is true. We normally demonstrate proofs

by writing English sentences mixed with symbols.

We’ll consider statements that are either true or false. If A and B be are statements, then

“not A,” “A and B,” and “A or B,” are called negation, conjunction, and disjunction,

respectively. “not A” is opposite in truth value from A. “A and B” is true exactly when

both A and B are true “A or B” is true except when both A and B are false.

Conditionals: “if A then B” (or “A implies B”) is a

conditional statement with antecedent A and consequent B. It’s contrapositive is “if not B then not A” and it’s converse is “if B then A”. Statements with the same truth table are said to be equivalent. The table shows that a conditional and it’s contrapositive are equivalent.

A conditional is vacuously true if its antecedent is false.

A conditional is trivially true if its consequent is true.

Proof Techniques: We’ll give sample proofs about numbers. Here are some definitions.

  • integers: …, -2, -1, 0, 1, 2, …
  • odd integers: …, -3, -1, 1, 3, … (have the form 2k + 1 for some integer k).
  • even integers:…, -4, -2, 0, 2, 4, … (have the form 2k for some integer k).
  • m | n (read m divides n) if m ≠ 0 and n = km for some integer k.
  • p is prime if p > 1 and its only divisors are 1 and p.

*

Notice that the converse of “if A then B” is “if B then A” and they have DIFFERENT truth tables.

*

Exhaustive Checking

Some statements can be proven by exhaustively checking a finite number of cases.

Example 1. There is a prime number between 200 and 220.

Proof: Check exhaustively and find that 211 is prime. QED.

Example 2. Each of the numbers 288, 198, and 387 is divisible by 9.

Proof: Check that 9 divides each of the numbers. QED.

Conditional Proof

Most statements we prove are conditionals. We start by assuming the antecedent is true.

Then we try to find a statement that follows from the assumption and/or known facts. We

continue in this manner until we reach the consequent.

Example 3. If x is odd and y is even then x – y is odd.

Proof: Assume x is odd and y is even. Then x = 2k + 1 and y = 2m for some

integers k and m. So we have

x – y = 2k + 1 – 2m = 2(k – m) + 1,

which is an odd integer since k – m is an integer. QED.

Example 4. If x is odd then x2 is odd.

Proof: Assume x is odd. Then x = 2k + 1 for some integer k. So we have

x2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1,

which is an odd integer since 2k2 + 2k is an integer. QED.

*

Example 5. If x is even then x2 is even.

Proof: Class do as one minute quiz.

Example 6. If x2 is odd then x is odd.

Proof: The contrapositive of this statement is “if x is even, then x2 is even,” which is

true by Example 5. QED.

Example 7. If x2 is even then x is even.

Proof: This is the contrapositive of Example 4, which has been shown to be true. QED.

If And Only If (Iff) Proofs

A statement of the form “A if and only if B” means “A implies B” and “B implies A.” So

there are actually two proofs to give. Sometimes the proofs can be written as a single

proof of the form “A iff C iff D iff … iff B,” where each iff statement is clear from

previous information.

Example 8. x is even if and only if x2 – 2x + 1 is odd.

Proof: x is even iff x = 2k for some integer k (definition)

iff x – 1 = 2k – 1 for some integer k (algebra)

iff x – 1 = 2(k – 1) + 1 for some integer k – 1 (algebra)

iff x – 1 is odd (definition)

iff (x – 1)2 is odd (Examples 4 and 6)

iff x2 – 2x + 1 is odd (algebra). QED.

*

Proof By Contradiction

A false statement is called a contradiction. For example, “S and not S” is a

contradiction for any statement S. A truth table will show us that “if A then B,” is

equivalent to “A and not B implies false.” So to prove “if A then B,” it suffices to

assume A and also to assume not B, and then argue toward a false statement. This

technique is called proof by contradiction or reductio ad absurdum.

Example 9. If x2 is odd then x is odd.

Proof: Assume, BWOC, that x2 is odd and x is even. Then x = 2k for some integer k.

So we have

x2= (2k)2 = 4k2 = 2(2k2),

which is even since 2k2 is an integer. So we have

x2 is odd and x2 is even, a contradiction. So the statement is true. QED.

Example 10. If 2 | 5n then n is even.

Proof: Assume, BWOC, that 2 | 5n and n is odd. Since 2 | 5n, we have 5n = 2d for some

integer d. Since n is odd, we have n = 2k + 1 for some integer k. Then we have

2d = 5n = 5(2k + 1) = 10k + 5.

So 2d = 10k + 5. Solve for 5 to get

5 = 2d – 10k = 2(d – 5k).

But this says that 5 is an even number, a contradiction. So the statement is true. QED.

*

Section 1.2 Sets

A set is a collection of things.

  • If S is a set and x is a member or element of S we write x  S. Othewise we write x  S.
  • The set with elements x1, …, xn is denoted {x1, …, xn}.
  • The empty set with no elements is denoted { } or .
  • A set with one element is called a singleton. e.g., {a} is a singleton.
  • The set of integers is denoted by Z, the natural numbers {0, 1, …} by N, the rational

numbers by Q, and the real numbers by R.

Equal Sets

Two sets A and B are equal, denoted A = B if they have the same elements.

e.g., {a, b, c} = {c, b, a} (no ordering).

e.g., {a, a, b, c} = {a, b, c} (no repetitions)

  • Sets can be described by properties that the elements satisfy. If P is a property, then the

expression {x | P} denotes the set of all x that satisfy P.

e.g., The set of odd natural numbers can be represented by the following equal sets.

{x | x = 2k + 1 for some k  N} = {1, 3, 5, …}.

Subsets

The set A is a subset of B, denoted A  B, means every element of A is an element of B.

e.g., N  Z  Q  R.

e.g., S  S for any set S.

e.g.,   S for any set S.

*

The power set of a set S, denoted power(S) is the set of all subsets of S.

e.g., power({a, b}) = {, {a}, {b}, {a, b}}.

Example(Comparing sets). Let A = {2k + 7 | k  Z} and B = {4k + 3 | k  Z}.

Quiz. Is A  B?

Answer: No. For example, 9  A but 9  B.

Quiz. Is B  A?

Answer: Yes. Let x  B. Then x = 4k + 3 for some k  Z. But we can write

x = 4k + 3 = 4k – 4 + 7 = 2(2k – 2) + 7.

Since 2k – 2  Z, it follows that x  A. Therefore B  A. QED.

Equality in terms of subsets: A = B iff A  B and B  A.

Example. Let A = {2k + 5 | k  Z} and B = {2k + 3 | k  Z}.

Show that A = B.

Proof: First show A  B. Let x  A. Then x = 2k + 5 for some k  Z. So we have

x = 2k + 5 = 2k + 2 + 3 = 2(k + 1) + 3.

Since k + 1  Z, it follows that x  B. Therefore A  B.

Now show the other direction B  A.

…….Class fill in the proof (2 minute quiz).

Since A  B and B  A it follows that A = B. QED.

*

Operations on Sets

Union: A  B = {x | x  A or x  B}.

Intersection: A  B = {x | x  A and x  B}.

Difference: A – B = {x | x  A and x  B}.

Symmetric Difference: A  B = {x | x  A or x  B but not both}

Note: A  B = (A – B)  (B – A) = (A  B) – (A  B ) .

Universal Complement: Given a universe U and A  U, we write

A’ = U – A.

Example. For each n  N let Dn = {x  N | x divides n}. So Dn is the set of positive

divisors of n. Here are some expressions involving these sets.

  • D0 = {1, 2, 3, … } = N – {0}, D5 = {1, 5}, D6 = {1, 2, 3, 6}, and D9 = {1, 3, 9}.
  • D5  D6 = {1, 2, 3, 5, 6}
  • D5  D6 = {1}
  • D9 – D6 = {9}
  • D5  D6 = {2, 3, 5, 6}
  • Let N be the universe. Then D0′ = N – D0 = {0}, and {0}’ = D0.

Quiz (2 minutes). Draw a Venn diagram for three sets A, B, C with some areas shaded.

Then find an expression to represent the shaded area.

*

*

Properties of Set Operations

Union and intersection are commutative, associative, and distribute over each other. There

are many other properties too. For example,

  • Absorption: A  (A  B) = A and A  (A  B) = A.
  • De Morgan’s Laws: (A  B)’ = A’  B’ and (A  B)’ = A’  B’.

Counting Sets

The cardinality of a set S is denoted by | S |. Two useful rules for counting finite sets are:

  • Inclusion-Exclusion principle: | A  B | = | A | + | B | – | A  B |.
  • Difference Rule: | A – B | = | A | – | A  B |.

Quiz (2 minutes). Find a rule for the union of three sets: | A  B  C | = ?

Quiz (3 minutes). Three programs use a collection of processors in the following way,

where A, B, and C represent the sets of processors used by the three programs:

| A | = 20, | B | = 40, | C | = 60, | A  B | = 10, | A  C | = 8, | B  C | = 6.

If there are 100 processors available, what could | A  B  C | be?

Answer: 100 ≥ | A  B  C | = 20 + 40 + 60 – 10 – 8 – 6 + | A  B  C | . So

| A  B  C | ≤ 4.

Bags (Multisets) are like sets but can contain repeated elements. e.g., [t, o, o, t] = [o, t, t, o].

Union and intersection can be defined by taking the maximum and minimum occurrences of

each element, respectively.

Quiz (2 minutes). Let A = [m, i, s, s, i, s, s, i, p, p, i] and B = [s, i, p, p, i, n, g].

What are A  B and A  B?

Answer: A  B = [m, i, s, s, i, s, s, i, p, p, i, n, g] and A  B = [s, i, p, p, i].

*

*

Section 1.3 Ordered Structures

Tuples: Have order and can have repetitions. For example, (6, 7, 6) is a 3-tuple and ( ) is

the empty tuple. We write (x1, …, xn) = (y1, …, yn) to mean xi = yi for 1 ≤ i ≤ n.

Cartesian Product: A  B = {(x, y) | x  A and y  B}. The definition extends to more than

two sets. For example, A  B  C = {(x, y, z) | x  A, y  B, z  C}.

  • Notation: A0 = {( )}, A1 = {(x) | x  A}, and in general, An = {(x1, …, xn) | xi  A}.

Quiz (1 minute). Does (A  B)  C = A  (B  C)?

Lists: Are like tuples but there is no random access. For example, a, b, a, c is a list with 4

elements and   is the empty list.

  • The operations on lists are head, tail, and cons. For example,

head(a, b, a, c) = a, tail(a, b, a, c) = b, a, c, cons(a, b, a, c) = a, b, a, c.

  • The set of lists whose elements are in A is denoted by lists(A).

Quiz (1 minute). For L =  a, b, c, d , find head(L) and tail(L).

Strings: Are like lists, but are represented as juxtaposed elements from a given alphabet.

For example, if A = {a, b}, then some strings over A are: a, b, aa, ab, ba, bb, aaa, bbb.

  • The empty string is denoted by L.
  • The concatenation of two strings is their juxtaposition. For example, the concatenation of

ab and bab is abbab.

  • For any string s we have sL = Ls = s.
  • If s is a string, sn denotes the concatenation of s with itself n times. Also s0 = L. For

example, (ab)3 = ababab.

*

*

Languages

A language is a set of strings, usually taken over some alphabet.

Notation: If A is an alphabet, then the set of all strings over A is denoted by A*.

Example. Some languages over A are: , {L}, A, and A*.

Example. {abna | n  N} = {aa, aba, abba, abbba, … } is a language over {a, b}.

Language Operations

Let L and M be languages. The product of L and M, denoted LM, is the language

LM = {st | s  L and t  M}.

  • Notation: L0 = {L}; and Ln = {s1…sn | si  L}.

Quiz (1 minute). What are the products L and L{L}?

Quiz (1 minute). Solve for L in the equation {L, a, b}L = {L, a, b, aa, ba, aba, bba}.

  • The closure L* is the set of all possible concatenations of strings in L. So

L* = L0  L1  …  Ln  …

Quiz (1 minute). What are {L}* and *?

Example. Examine the structure of an arbitrary string x  L*(ML)*.

A solution: Use the definitions to write x in terms of strings in L and M.

1. Since x  L*(ML)*, it follows that x = uv where u  L* and v  (ML)*.

2. Since u  L*, either u = L or u = s1…sn for some n where si  L.

3. Since v  (ML)*, either v = L or v = r1t1 …rktk for some k where ri  M and ti  L.

So x has one of four forms: L, s1…sn, r1t1 …rktk, or s1…snr1t1 …rktk.

*

*

Relations.

A relation is a set of tuples. If R is a relation and (x1, …, xn)  R, we write R(x1, …, xn).

We can usually represent a relation as a subset of some cartesian product.

Example. Let R = {(0, 0), (1, 1), (4, 2), (9, 3), …, (n2, n), …} = {(n2, n) | n  N}. We might

call R the “is square of” relation on N. Notice also that R  N  N.

Notation: If R is binary, we can use infix to represent pairs in R. For example, from the

previous example, we have (9, 3)  R. So we can also write

R(9, 3) or 9 R 3 or 9 is square of 3.

Relational Databases

A relational database is a relation where the indexes of a tuple have associated names

called attributes.

Example. Let Students = {(x, y, z) | x is a Name, y is a Major, and z is Credits}.

Who are the people majoring in CS?

{x | (x, CS, z)  Students, for some z}.

Note: We need “for some z” to indicate that z is a variable.

How many math majors are upper division students?

| {x | (x, math, z)  Students and z ≥ 90} |.

What is the major of AbeLincoln?

{y | (AbeLincoln, y, z)  Students, for some z}.

What is the history department database of names and their credits?

{(x, z) | (x, history, z)  Students}.

*

*

Counting Tuples (or strings or lists)

Product Rule: | A  B | = | A | | B | and | An | = | A |n.

Example. If A = {a, b} and B = {1, 2, 3}, then

A  B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}.

So | A  B | = 6 = (2)(3) = | A | | B |.

Example. Count the number of strings of length 8 over A = {a, b, c} that begin with either

a or c and have at least one b.

It is easy to calculate the cardinality of U – B:

| U – B | = | U | – | U  B | = | U | – | B | (since B is a subset of U)

It is also easy to count U because it has the same cardinality as the set {a, c}  A7, which is

| {a, c}  A7 | = | {a, c} | | A7 | = | {a, c} | | A |7 = (2)37.

It is also easy to count B because it has the same cardinality as the set {a, c}8, which is

| {a, c}8 | = | {a, c} |8 = 28.

So we have the answer:

| U – B | = | U | – | U  B | = | U | – | B | = (2)37 – 28, which is 4118.

A Solution: Split the problem up into easier problems and combine

the results (divide and conquer). Let U be the universe consisting

of the strings over A of length 8 that begin with either a or c. Let B

be the subset of U consisting of strings with no b’s. Then the set of

strings to count is U – B, as pictured.

U

U – B

B

*

*

Section 1.4 Graphs and Trees

A graph is set of objects called vertices or nodes where some pairs of objects may be

connected by edges. (A directed graph has edges that point in one direction.)

Example. Draw a graph of the South American countries that touch the Pacific Ocean and

their neighbors, where the vertices are countries and an edge indicates a common border.

Vertices = {Co, V, E, Br, P, Bo, Ch, A}

Edges = {{Co, V}, {Co, E}, ….}.

A path from vertex x0 to xn is a sequence of edges

that we denote by (x0, x1, …, xn) where

there is an edge from xi–1 to xi for 1≤ i ≤ n.

The length of a path is the number of edges.

A cycle is a path with distinct edges that begins

and ends at the same vertex.

Example. (A, Bo, A) is not a cycle since the edge

{A, Bo} occurs twice. (A, Bo, Br, A) is a cycle.

Quiz (1 minute). What is a longest path from A to V with distinct edges and no cycles?

Answer: The length is 6. For example, (A, Bo, Br, P, E, Co, V).

A graph is connected if there is a path between every pair of vertices. The example graph is connected. A graph of the United States is not connected. Hawaii and Alaska are isolated vertices.

Bo

Br

P

V

E

Co

Ch

A

*

*

Trees

A tree is a connected graph (a path between any two points) with no

cycles. Most trees are oriented so that they look like upside-down

trees, such as the tree pictured.

The top node is the root, the nodes directly below a node are its

children, the node directly above a node is the parent, the bottom

nodes are leaves, and the height or depth of the tree is the length of

the longest path of distinct edges from root to a leaf.

Any algebraic expression can be represented as a tree. For

example, the tree for the expression (x – y) + log(z + w) is

pictured to the right.

Quiz (1 minute). Do a depth-first (left to right) traversal.

Answer: + – x y log + z w. This is the prefix form of the

expression.

Example. For this tree the root is A. The children of A are B, C, D. D is the

parent of G. The height or depth of the tree is 3. The leaves are E, F, C, H, I.

Any node of a tree is the root of a subtree. One way to represent a tree is as a

list whose head is the root of the tree and whose tail is the list of subtrees, where

each subtree is represented in the same way.

Example. The pictured tree can be represented by the list

 A,  B,  E ,  F  ,  C ,  D,  G,  H ,  I    .

y

log

x

_

+

+

z

w

F

D

E

B

C

A

G

H

I

*

*

Binary Trees

A binary tree is either empty, denoted by  , or each node has two subtrees that are binary

trees and are called the left and right subtrees of the node. If a binary tree is not empty,

we’ll represent it as a list of the form L, x, R, where x is the root and L and R are the left

and right subtrees, respectively.

Spanning Trees

A spanning tree for a connected graph is a tree whose nodes are the nodes of the graph and

whose edges are a subset of the edges of the graph. A minimal spanning tree minimizes the

sum of weights on the edges of all spanning trees.

Example. The binary tree with a single node x is denoted by  , x,  .

A binary search tree represents ordered information, where the predecessors

and successors of a node are in its left and right subtrees, respectively.

Example. A binary search tree for the first six prime numbers is pictured.

Example. Use Prim’s algorithm to construct a minimal spanning tree

for the pictured graph, starting with node D.

Solution: A minimal spanning tree is constructed in 4 steps:

5

2

3

7

11

13

C

E

D

B

A

1

1

2

2

3

3

3

C

E

D

B

A

1

1

2

2

C

D

B

A

1

1

2

C

D

B

1

2

D

B

1

*

test

*

Languages and Automata  

*

Section 11.1 Regular Languages

Problem: Suppose the input strings to a program must be strings over the alphabet {a, b}

that contain exactly one substring bb. In other words, the strings must be of the form xbby,

where x and y are strings over {a, b} that do not contain bb, x does not end in b, and y does

not begin with b. In a few minutes, we’ll see how to describe the strings formally.

A regular language over alphabet A is a language constructed by the following rules:

  •  and {} are regular languages.
  • {a} is a regular language for all a  A.
  • If M and N are regular language, then so are M  N, MN, and M*.

Example. Let A = {a, b}. Then the following languages are a sampling of the regular

languages over A:

, {}, {a}, {b}, {a, b}, {ab}, {a}* = {, a, aa, aaa, …, an, … }.

A regular expression over alphabet A is an expression constructed by the following rules:

  •  and  are regular expressions.
  • a is a regular expression for all a  A.
  • If R and S are regular expressions, then so are (R), R + S, R·S, and R*.

The hierarchy in the absence of parentheses is, * (do it first), ·, + (do it last). Juxtaposition will be used in place of ·.

Example. Let A = {a, b}. Then the following expressions are a sampling of the regular

expressions over A:

, , a, b, ab, a + ab, (a + b)*.

*

*

Regular expressions represent regular languages

Regular expressons represent regular languages by the following correspondence, where

L(R) denotes the regular language of the regular expression R.

L() = ,

L() = {},

L(a) = {a} for all a  A,

L(R + S) = L(R)  L(S),

L(RS) = L(R)L(S),

L(R*) = L(R)*.

Example. The regular expression ab + a* represents the following regular language:

L(ab + a*) = L(ab)  L(a*)

= L(a)L(b)  L(a)*

= {a}{b}  {a}*

= {ab}  {, a, aa, aaa, …, an, … }

={ab, , a, aa, aaa, …, an, … }.

Example. The regular expression (a + b)* represents the following regular language:

L((a + b)*) = (L(a + b))* = {a, b}*, the set of all possible strings over {a, b}.

Back to the Problem: Suppose the input strings to a program must be strings over the

alphabet {a, b} that contain exactly one substring bb. In other words, the strings must be of

the form xbby, where x and y are strings over {a, b} that do not contain bb, x does not end

in b, and y does not begin with b. How can we describe the set of inputs formally?

Solution: let x = (a + ba)* and y = (a + ab)*.

*

Quiz. Find a regular expresson for {abn | n  N}  {ban | n  N}.

Answer. ab* + ba*.

Quiz. Use a sentence to describe the language of (b + ab)*( + a).

Answer. All strings over {a, b} whose substrings of a’s have length 1.

The Algebra of Regular Expressions

Equality: Regular expressions R and S are equal, written R = S, when L(R) = L(S).

Examples. a + b = b + a, a + a = a, aa* = a*a, ab ≠ ba.

Properties of +, ·, and closure

+ is commutative, associative,  is identity for +, and R + R = R.

· is associative,  is identity for ·, and  is zero for ·.

· distributes over +

(closure properties)

* = * = .

R* = R*R* = (R*)* = R + R*.

R* =  + R* =  + RR* = ( + R)* = ( + R)R*.

R* = (R + R2 + … + Rk)* =  + R + R2 + … + Rk–1 + RkR* for any k ≥ 1.

R*R = RR*.

(R + S)* = (R* + S*)* = (R*S*)* = (R*S)*R* = R*(SR*)*.

R(SR)* = (RS)*R.

(R*S)* =  + (R + S)*S and (RS*)* =  + R(R + S)*.

Proof: All properties can be verified by showing that the underlying regular languages are

equal as sets. QED.

*

Quiz. Explain each inequality.

(1). (a + b)* ≠ a* + b*. (2) (a + b)* ≠ a*b*.

Answers. (1) ab  L((a + b)*) – L(a* + b*).

(2) ba  L((a + b)*) – L(a*b*).

Quiz. Simplify the regular expression aa(b* + a) + a(ab* + aa).

Answer. aa(b* + a) + a(ab* + aa)

= aa(b* + a) + aa(b* + a) · distributes over +

= aa(b* + a) R + R = R.

Example/Quiz. Show that (a + aa)(a + b)* = a(a + b)*.

Proof: (a + aa)(a + b)* = (a + aa)a*(ba*)* (R + S)* = R*(SR*)*

= a( + a)a*(ba*)* R = R and · distributes over +

= aa*(ba*)* ( + R)R* = R*

= a(a + b)* (R + S)* = R*(SR*)* QED.

Example/Quiz. Show that a*(b + ab*) = b + aa*b*.

Proof: a*(b + ab*) = ( + aa*)(b + ab*) R* =  + RR*

= b + ab* + aa*b + aa*ab* · distributes over +

= b + (ab* + aa*ab*) + aa*b + is commutative and associative

= b + ( + aa*)ab* + aa*b R = R and · distributes over +

= b + a*ab* + aa*b R* =  + RR*

= b + aa*b* + aa*b R*R = RR*

= b + aa*(b* + b) · distributes over +

= b + aa*b*. R* = R* + R QED.

*

Example. Show that a* + abb*a = a* + ab*a.

Proof: Starting on the RHS, we have

a* + ab*a = a* + a( + bb*)a R* =  + RR*

= a* + aa + abb*a · distributes over +

= ( + aa*) + aa + abb*a R* =  + RR*

=  + (aa* + aa) + abb*a + is associative

=  + a(a* + a) + abb*a · distributes over +

=  + aa* + abb*a R* = R + R*

= a* + abb*a R* =  + RR* QED.

Example. Show that (a + aa + … + an)(a + b)* = a(a + b)* for all n ≥ 1.

Proof (by induction): If n = 1, the statement becomes a(a + b)* = a(a + b)*, which is true. If

n = 2, the statement becomes (a + aa)(a + b)* = a(a + b)*, which is true by a previous

example. Let n > 2 and assume the statement is true for 1 ≤ k < n. We need to prove the

statement is true for n. The LHS of the statement for n is

(a + aa + … + an)(a + b)*

= a(a + b)* + (aa + … + an)(a + b)* · distributes over +

= a(a + b)* + a(a + aa + … + an–1)(a + b)* · distributes over +

= a(a + b)* + aa(a + b)* induction assumption

= (a + aa)(a + b)* · distributes over +

= a(a + b)* induction assumption

The last line is the RHS of the statement for n. So the statement is true for n. Therefore, the

statement is true for all n ≥ 1. QED.

*

Example/Quiz: Use regular algebra to show that R + (R + S)* = (R + S)*.

Proof:

R + (R + S)* = R + [L + (R + S) + (R + S)(R+ S)*] R* =  + R + R2 + … + Rk–1 + RkR*

= L + (R + R) + S + (R + S)(R+ S)* + is associative

= L + R + S + (R + S)(R+ S)* R + R = R

= L + (R + S) + (R + S)(R+ S)* + is associative

= (R+ S)* R* =  + R + R2 + … + Rk–1 + RkR*

QED.

Take-home quiz: Use regular algebra to show that (a + ab)*a = a(a + ba)*.

*

Section 11.2 Finite Automata

Can a machine(i.e., algorithm) recognize a regular language? Yes!

Deterministic Finite Automata

A deterministic finite automaton (DFA) over an alphabet A is a finite digraph (where

vertices or nodes are called states) for which each state emits one labeled edge for each

letter of A. One state is designated as the start state and a set of states may be final states.

Example. Either of the following alternatives is acceptable for representing a DFA, where

final states are indicated by double circles.

The Execution of DFA for input string w  A* begins at the start state and follows a path

whose edges concatenate to w. The DFA accepts w if the path ends in a final state.

Otherwise the DFA rejects w. The language of a DFA is the set of accepted strings.

Example. The example DFA accepts the strings

a, b, ab, bb, abb, bbb, …, abn, bbn, ….

So the language of the DFA is given by the regular expression (a + b)b*.

Start

0

1

2

a

a

b

b

b

a

Start

0

1

2

a, b

a

b

a, b

*

*

Quiz. Find a DFA for the language of a + aa*b.

Theorem (Kleene) The class of regular languages is exactly the same as the class of

languages accepted by DFAs.

Quiz. Find an DFA for each of the following languages over the alphabet {a, b}.

(a) . (b) {}. (c) {(ab)n | n  N}, which has regular expression (ab)*.

Start

0

1

4

a, b

a

a

a, b

b

a

b

b

2

3

Solution:

Start

a, b

a, b

(b):

Start

a, b

Solutions: (a):

Start

b

a, b

a

a

b

(c):

*

*

Table Representation of a DFA

A DFA over A can be represented by a transition function T : States  A  States, where

T(i, a) is the state reached from state i along the edge labeled a, and we mark the start and

final states. For example, the following figures show a DFA and its transition table.

Note: T can be extended to T : States  A*  States by

T(i, L) = i and T(i, aw) = T(T(i, a), w) for a  A and w  A*.

Quiz: Calculate T(0, bba).

Solution: T(0, bba) = T(1, ba) = T(1, a) = T(2, L) = 2.

Example/Quiz. Back to the problem of describing input strings over {a, b} that contain

exactly one substring bb. We observed that the strings could be described by the regular

expression (a + ba)*bb(a + ab)*. Find a DFA to recognize the language.

Start

0

1

2

a, b

a

b

a, b

Start

a

a

b

a

b

A solution:

b

a

b

a, b

*

*

Nondeterministic Finite Automata

A nondeterministic finite automaton (NFA) over an alphabet A is similar to a DFA except

that L-edges are allowed, there is no requirement to emit edges from a state, and multiple

edges with the same letter can be emitted from a state.

Example. The following NFA recognizes the language of a + aa*b + a*b.

Table representation of NFA

An NFA over A can be represented by a function T : States  A  {L}  power(States),

where T(i, a) is the set of states reached from state i along the edge labeled a, and we mark

the start and final states. The following figure shows the table for the preceding NFA.

Start

0

2

1

a

a

L

a

b

*

*

Theorem (Rabin and Scott) The class of regular languages is exactly the same as the

class of languages accepted by NFAs.

Quizzes. Find an NFA for each of the following languages over {a, b}.

(a) . (b) {}. (c) {(ab)n | n  N}, which has regular expression (ab)*.

ExampleQuiz. Back to the problem of describing input strings over {a, b} that contain

exactly one substring bb. We observed that the strings could be described by the regular

expression (a + ba)*bb(a + ab)*. Find an NFA to recognize the language.

Start

Solutions: (a):

Start

(b):

Start

b

a

(c):

Start

a

b

a

b

b

a

a

b

A solution:

*

*

Algorithm: Transform a Regular Expression into a Finite Automaton

Start by placing the regular expression on the edge between a start and final state:

Apply the following rules to obtain a finite automaton after erasing any -edges.

Quiz. Use the algorithm to construct a finite automaton for (ab)* + ba.

Start

Regular expression

R + S

i

j

R

i

j

S

transforms to

RS

i

j

i

j

R

S

transforms to

R*

i

j

i

j

L

L

R

transforms to

Start

a

b

b

a

L

L

Answer:

*

*

Algorithm: Transform a Finite Automaton into a Regular Expression

Connect a new start state s to the start state of the FA and connect each final state of the FA

to a new final state ƒ as shown in the figure.

If needed, combine all multiple edges between the same two nodes into one edge with label

the sum of the labels on the multiple edges. If there is no edge between two states, assume

there is an -edge.

Now eliminate each state k of the FA by constructing a new edge (i, j) for each pair of edges

(i, k) and (k, j) where i ≠ k and j ≠ k. The new label new(i, j) is defined in terms of the old

labels by the formula

new(i, j) = old(i, j) + old(i, k)old(k, k)*old(k, j)

L

L

Given

FA

Connect to start state of FA

s

ƒ

Connect from each final state of FA

D

A

C

B

i

k

j

A + BC*D

i

j

Example.

becomes

*

*

Quiz. Use the algorithm to transform the following NFA into a regular expression. (Half the

class eliminate state 0 then state 1 and half the class eliminate state 1 then state 0.)

Solution: Connect the NFA to new a start

state s and a new final state f as pictured.

First Solution: Eliminate state 0 to obtain:

new(s, 1) =  + La*a = a*a.

new(1, 1) =  + ba*a = ba*a.

Second Solution: Eliminate state 1 to obtain:

new(0, f) =  + a*L = a.

new(0, 0) = a + a*b = a + ab.

Eliminate state 1 to obtain:

new(s, f) =  + a*a(ba*a)*L = a*a(ba*a)*.

Eliminate state 0 to obtain:

new(s, f) =  + L(a + ab)*a = (a + ab)*a.

Start

a

a

b

0

1

a

a

b

0

1

s

ƒ

L

L

s

ƒ

1

a*a

ba*a

L

s

ƒ

a*a(ba*a)*

s

ƒ

0

L

a + ab

a

s

ƒ

(a + ab)*a

*

*

Quiz. Use regular algebra to show the following equality from the previous quiz.

a*a(ba*a)* = (a + ab)*a.

Proof: a*a(ba*a)* = a*[a((ba*)a)*] · is associative

= a*[(a(ba*))*a] R(SR)* = (RS)*R

= a*[((ab)a*)*a] · is associative

= [a*((ab)a*)*]a · is associative

= (a + ab)*a R*(SR*)* = (R + S)*. QED.

Automata with Output (Mealy and Moore)

Mealy machine: Associate an output action with each

transition between states.

Challenge: Describe a two-floor elevator system with a Mealy or Moore machine.

Moore machine: Associate an output action with each state.

Theorem: Mealy and Moore machines are equivalent.

Example/Quiz. Output the complement of a binary number.

i/A

a

j/B

a/A

i

j

Start

0/1

0

1/0

Start

0/L

2/0

1/1

0

1

0

1

0

1

Solutions:

*

*

Section 11.3 Constructing Efficient Finite Automata

First we’ll see how to transform an NFA into a DFA. Then we’ll see how to transform a

DFA into a minimum-state DFA.

Transforming an NFA into a DFA

The l-closure of a state s, denoted l(s), is the set consisting of s together with all states that

can be reached from s by traversing l-edges. The l-closure of a set S of states, denoted

l(S), is the union of the l-closures of the states in S.

Example. Given the following NFA as a graph and as a transition table.

Some sample l-closures for the NFA are as follows:

l(0) = {0, 1, 2}

l(1) = {1, 2}

l(2) = {2}

l() = 

l({1, 2}) = {1, 2}

l({0, 1, 2}) = {0, 1, 2}.

S

0

2

1

b

b

L

a

L

a

*

*

Algorithm: Transform an NFA into a DFA

Construct a DFA table TD from an NFA table TN as follows:

1. The start state of the DFA is l(s), where s is the start state of the NFA.

2. If {s1, …, sn} is a DFA state and a  A, then

TD({s1, …, sn}, a) = l(TN(s1, a)  …  TN(sn, a)).

3. A DFA state is final if one of its elements is an NFA final state.

Example. Given the following NFA.

The algorithm constructs the following DFA transition table TD, where it is also written in

simplified form after a renumbering of the states.

S

0

3

1

b

b

a

L

a

2

b

*

*

Quiz. Use the algorithm to transform the following NFA into a DFA.

Solution: The algorithm constructs the following DFA transition table TD, where it is

also written in simplified form after a renumbering of the states.

S

0

1

a

a

L

b

2

3

a

*

*

Transforming an DFA into a minimum-state DFA

Let S be the set of states that can be reached from the start state of a DFA over A.

For states s, t  S let s ~ t mean that for all strings w  A* either T(s, w) and T(t, w) are

both final or both nonfinal. Observe that ~ is an equivalence relation on S. So it partitions S

into equivalence classes.

Observe also that the number of equivalence classes is the minimum number of states

needed by a DFA to recognize the language of the given DFA.

Algorithm: Transform a DFA to a minimum-state DFA

1. Construct the following sequence of sets of possible equivalent pairs of distinct states:

E0  E1  …  Ek = Ek+1,

where

E0 = {{s, t} | s and t are either both final or both nonfinal}

and

Ei+1 = {{s, t}  Ei | {T(s, a), T(t, a)}  Ei or T(s, a) = T(t, a)} for every a  A}.

Ek represents the distinct pairs of equivalent states from which ~ can be generated.

2. The equivalence classes form the states of the minimum state DFA with transition table Tmin defined by

Tmin([s], a) = [T(s, a)].

3. The start state is the class containing the start state of the given DFA.

4. A final state is any class containing a final state of the given DFA.

*

*

Example. Use the algorithm to transform the following DFA into a minimum-state DFA.

Solution: The set of states is S = {0, 1, 2, 3, 4}. To find the equivalent states calculate:

E0 = {{0, 4}, {1, 2}, {1, 3}, {2, 3}}

E1 = {{1, 2}, {1, 3}, {2, 3}}

E2 = {{1, 2}, {1, 3}, {2, 3}} = E1.

So 1 ~ 2, 1 ~ 3, 2 ~ 3. This tells us that S is partitioned by {0}, {1, 2, 3}, {4}, which we

name [0], [1], [4], respectively. So the minimum-state DFA has three states.

Quiz: What regular expression equality arises from the two DFAs?

Answer: a + aa + (aaa + aab + ab)(a + b)* = a(a + b)*.

S

0

a

b

a

2

a, b

4

1

3

b

a, b

a, b

Min-state Table

Renamed Table

S

0

a

b

a, b

2

1

a, b

Min-state DFA graph

*

*

Quiz. Is the following DFA a minimum-state DFA?

Answer: No. E0 = {{0, 1}, {0, 5}, {1, 5}, {2, 3}, {2, 4}, {3, 4}}

E1 = {{1, 5}, {2, 4}}

E2 = {{1, 5}, {2, 4}} = E1.

So 1 ~ 5 and 2 ~ 4. This gives us {0}, {1, 5}, {2, 4}, {3}, with names

[0], [1], [2], [3], respectively with the following minimum-state DFA.

E0 = {{0, 1}}

E1 = {{0, 1}} = E0.

So 0 ~ 1, which tells us that the partition is the whole set of states {0, 1} = [0]. Therefore,

we obtain the following minimum-state DFA.

Answer. No. Use the minimum-state algorithm.

S

b

0

1

a

a

b

S

a, b

0

Quiz. Is the following DFA a minimum-state DFA?

*

*

Section 11.4 Regular Language Topics

Regular languages are also characterized by special grammars called regular grammars

whose productions take the following form, where w is a string of terminals.

A  wB or A  w.

Example. A regular grammar for the language of a*b* is

S  L | aS | T

T  b | bT.

Quiz. Write a regular grammar for {ab, acb, accb. …, acnb, …}.

Solution: A regular expression for the language is ac*b. A regular grammar is

S  aT

T  b | cT.

Regular grammars as we have defined them are often called right-regular because there are

also left-regular grammars that require productions to have the form

A  Bw or A  w.

Any language with a right-regular grammar also has a left-regular grammar, and

conversely.

Example. For the regular expression a*bc* we have the following grammars.

Right regular: S  aS | bT

T  L | cT.

Left Regular: S  Sc | Tb

T  L | Ta.

*

*

Transforming an NFA to a Regular Grammar

  • State names become the nonterminals. So rename them to be uppercase letters.

2. The start state becomes the start symbol of the grammar.

3. For each state transition from I to J labeled with x construct a production I  xJ.

4. For each final state F construct a production F  L.

Example/Quiz. Transform the following NFA into a regular grammar.

Solution:

S  aI | F

I  aI | bF

F  L

This grammar can be simplified to

S  aI | L

I  aI | b

Notice in the previous example that right-regular grammars derive strings by examining the

leftmost letter first, while left-regular grammars examine the rightmost letter first.

Example/Quiz. Find a right-regular grammar and a left-regular grammar for the language

of the regular expression a(b + c)*de*.

Right regular: S  aT

T  bT | cT | dU

U  L | eU.

Left Regular: S  Se | Td

T  a | Tb | Tc.

Start

S

F

I

L

b

a

a

*

*

Example/Quiz. Transform the regular expression a*(ba)* into a regular grammar.

Solution: Draw an NFA and then use the algorithm.

An NFA:

The resulting grammar:

S  aS | bI | L

I  aF

F  bJ | L

J  aF.

Quiz. Simplify the grammar.

Answer:

S  aS | baF | L

F  baF | L

Quiz. What happens when a DFA has

an error state, like the following DFA?

Answer: The resulting grammar:

S  aF | bE

F  aE | bJ | L

J  aF | bE

E  aE | bE.

But E does not derive a

terminal string. So the

grammar simplifies to

S  aF

F  bJ | L

J  aF.

Quiz: Simplify the grammar

further.

Answer: S  aF

F  baF | L.

Start

S

I

a

b

F

J

a

b

a

Start

S

F

J

a

b

a

E

b

a

b

a, b

*

*

Transforming a Regular Grammar to an NFA

1. Replace any production with multiple terminals by productions with single terminals.

2. The start state is the grammar start symbol.

3. Transform I  aJ into a transition from I to J labeled with a.

4. Transform I  J into a transition from I to J labeled with L.

5. Transform each I  a into a transition from I to new single final state F labeled with a.

6. The final states are F together with each state I with a production I  L.

Example/Quiz. Transform the following regular grammar into a NFA.

S  abS | T | L

T  cT | d

Quiz. What is the regular expression for the language of the grammar?

Answer: (ab)*(L + c*d)

Solution. Transform S  abS into S  aI

and I  bS, so the grammar becomes

S  aI | T | L

I  bS

T  cT | d

Now the NFA can be drawn:

Start

S

T

L

b

a

c

F

I

d

*

*

Properties of Regular Languages

When we know some properties of regular languages they can help us argue, BWOC, that

certain languages are not regular.

The Pumping Lemma

If L is an infinite regular language, then it is recognized by a DFA with, say, m states.

If s in L and | s | ≥ m, then an acceptance path for s must pass through some state twice.

The following graph depicts the situation.

The dotted arrows represent the path to acceptance for s and the letters x, y, and z represent

the concatenation of the letters along the edges of the path. So s = xyz and y ≠ L. Assume

that the middle state is the first repeated state on the path. So | xy | ≤ m. Since the loop can

be traversed any number of times, we have the pumping property: xykz  L for all k  N

Example. The language L = {anbn | n  N} is not regular.

Proof: Assume, BWOC, that L is regular. Since L is infinite, the pumping lemma applies.

Choose s = ambm. Then s = xyz, where y ≠ L, | xy | ≤ m, and xykz  L for all k  N.

Since | xy | ≤ m and s = ambm = xyz, it follows that xy is a string of a’s.

Since y ≠ L, it must be that y = ai for some i > 0.

We’ll try for a contradiction with k = 2. The pumping property implies xy2z  L.

But xy2z = am + ibm, which is not in L because i > 0.

This contradiction implies that L is not regular. QED.

Start

y

x

z

*

*

Quiz. In the previous proof we exhibited a contradiction when k = 2. Find similar

contradictions for k = 0 and k = 3.

Answer: (k = 0) The pumping property implies xy0z  L. In other words, xz  L.

But xz = am – ibm, which is not in L because i > 0. This contradiction implies that L is not

regular. QED.

(k = 3) The pumping property implies xy3z  L. But xy3z = am + 2ibm, which is not in L

because i > 0. This contradiction implies that L is not regular. QED.

Example/Quiz. Prove the language L = {aabnac2n | n  N} is not regular.

Proof: Assume, BWOC, that L is regular. Since L is infinite, the pumping lemma applies.

Choose s = aabmac2m. Then s = xyz, where y ≠ L, | xy | ≤ m and xykz  L for all k  N.

Since | xy | ≤ m, there are three cases for y:

Case 1: y = aabi for some 0 ≤ i ≤ m – 2. (Remember, | xy | ≤ m, so x = L in this case.)

Case 2: y = abi for some 0 ≤ i ≤ m – 2. (In this case, we have x = a.)

Case 3: y = bi for some 0 < i ≤ m – 2 – j. (In this case, x = aabj for some 0 ≤ j ≤ m – 3)

We can obtain a contradiction in each case by considering k = 0, which implies xz  L.

Case 1: xz = bm – iac2m which is not in L because strings of L must begin with aa.

Case 2: xz = abm – iac2m which is not in L because strngs of L must begin with aa.

Case 3: xz = aabm – iac2m which is not in L because strings in L must have twice as many c’s as b’s which can’t be the case since i > 0.

So each of the three cases yields a contradiction. Therefore L is not regular. QED.

*

test

*

Computational Notions

*

Section 12.1 Turing Machines

A Turing machine (TM) is a simple computer

that has an infinite amount of storage in the

form of cells on an infinite tape. There is a

control unit that contains a finite set of state

transition instructions.

(i, a, b, R, j)

An instruction reads the symbol in the current tape cell, writes a symbol to the same cell,

and then moves the tape head one cell left or right or remains at the same cell, after which

the machine enters a new state.

Assumptions:

  • The symbol L denotes a blank cell.
  • The tape head is initially at the left end of a nonempty input string (unless specified

otherwise)

  • There is a designated start state.
  • There is one “halt” state.
  • The moves are denoted by L, S, R for move left, stay, and move right.

Instructions are represented in graphical form or as 5-tuples, as

shown in the example to the right.

This instruction executes if the current state of the TM is i and the

current input symbol is a. The TM writes b into that cell, moves

right one cell and enters state j.

a

Control

Unit

Tape

Tape head

Executes a finite set of instructions

i

j

*

*

Acceptance

An input string on the tape is accepted by the TM if the machine enters the halt state.

The language of a TM is the set of all strings accepted by the machine.

Example/Quiz. Given the following simple TM.

(0, a, a, R, halt).

What is the language of the TM?

Answer: If an input string begins with the letter a, then the TM executes the instruction and

halts. So the string is accepted. Therefore, the language of the TM is the set of all strings that

begin with the letter a.

Example. Construct a TM to accept the language {abn | n  N}.

Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.

If so, move right to scan b’s until  is found.

(0, a, a, R, 1)

(1, , , S, halt)

(1, b, b, R, 1).

Quiz. Construct a TM to accept the language {abna | n  N}.

Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.

If so, move right to scan b’s until a is found. Then make sure there is  to the right.

(0, a, a, R, 1)

(1, a, a, R, 2)

(1, b, b, R, 1)

(2, , , S, halt).

*

*

Quiz. Construct a TM to accept the language of the regular expression a(a + b)*.

Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.

If so, move right to scan any a’s or b’s until  is found.

(0, a, a, R, 1)

(1, a, a, R, 1)

(1, b, b, R, 1)

(1, , , S, halt).

Example/Quiz. Find a TM to accept {anbn | n  N}.

Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.

If so, write X and scan right looking for a b to replace by Y.

(0, , , S, halt) accept 

(0, a, X, R, 1) mark a with X

(0, Y, Y, R, 3) no more a’s

Scan right looking for b to pair with a:

(1, a, a, R, 1)

(1, Y, Y, R, 1)

(1, b, Y, L, 2) mark b with Y

Scan back left looking for X:

(2, a, a, L, 2)

(2, Y, Y, L, 2)

(2, X, X, R, 0)

Scan right looking for  and halt:

(3, Y, Y, R, 3)

(3, , , S, halt)

TMs are very powerful. For example, the preceding example can be generalized to a TM

that accepts the non-context free language {anbncn | n  N}. (See Example 13.2 in the

Text.) So a TM can handle two stacks. In fact, a TM can handle any number of stacks.

*

*

Turing Machines with Output

Specify the form of the output on the tape when the machine halts.

Example/Quiz. Find a TM to add 4 to a natural number represented in binary. Start with the

tape head at the right end of the input string and halt with the tape head at the left end of the

output string.

Solution. Let the start state be 0.

Move two cells left:

(0, 0, 0, L, 1)

(0, 1, 1, L, 1)

(1, 0, 0, L, 2)

(1, 1, 1, L, 2)

(1, , 0, L, 2)

Add 1:

(2, 0, 1, L, 3) Move left

(2, 1, 0, L, 2) Carry

(2, , 1, S, halt) Done

Find left end of the string:

(3, 0, 0, L, 3)

(3, 1, 1, L, 3)

(3, , , R, halt) Done

Quiz. How would you construct a TM to add 5 to a binary number?

One Solution: Add 1, move back to right end, and then use the preceding solution.

For this purpose, let the start state be 4.

Add 1:

(4, 0, 1, R, 5) Move right

(4, 1, 0, L, 4) Carry

(4, , 1, R, 5) Move right

Find right end of the string:

(5, 0, 0, R, 5)

(5, 1, 1, R, 5)

(5, , , L, 0) Go add 4

*

*

Example/Quiz. Find a TM to move any string over {a, b} to the left one cell position.

Assume the tape head ends at the left end of any nonempty output string.

Solution. Let the start state be 0.

Find a or b to move:

(0, a, , L, 1) Go write a

(0, b, , L, 2) Go write b

(0, , , L, 4) Done

Write a or b:

(1, , a, R, 3) Write a

(2, , b, R, 3) Write b

(3, , , R, 0) Skip 

A trace for input aba (tape head is red):

 a b a  (0, a, , L, 1)

  b a  (1, , a, R, 3)

a  b a  (3, , , R, 0)

a  b a  (0, b, , L, 2)

a   a  (2, , b, R, 3)

a b  a  (3, , , R, 0)

a b  a  (0, a, , L, 1)

a b    (1, , a, R, 3)

a b a   (3, , , R, 0)

a b a   (0, , , L, 4)

a b a   (4, , , L, 5)

a b a   (5, a, a, L, 5)

a b a   (5, b, b, L, 5)

a b a   (5, a, a, L, 5)

 a b a   (5, , , R, halt)

 a b a   Output.

Move to left end of output:

(4, , , L, 5)

(5, a, a, L, 5)

(5, b, b, L, 5)

(5, , , R, halt).

Quiz. (Exercise 2). Find a TM to search for

the symbol # on an otherwise empty tape,

where the tape head starts at a random cell.

A Solution: Use a new symbol, say x, to mark

cells that have been searched as the machine

alternately looks left and right.

A Sample Trace:

#    

#  x  

# x x  

# x x  

# x x x 

# x x x 

# x x x .

*

*

Alternative Definitions of Turing Machine

One-way Infinite Tape Multihead Multitape

Quiz. Why are they all equal in power to the original

definition of a Turing machine?

An n-head or n-tape instruction contains n-tuples for the cell contents and move operations.

Example. A typical instruction for a 2-head or a 2-tape TM is

(0, (a, b), (c, d), (L, R), 1).

Example/Quiz. Implement some sample PDA instructions as

TM instructions for a 2-tape TM. Assume one tape holds the

input string and the other tape holds the stack. Assume the

input is scanned left to right and the the stack grows from

right to left.

PDA Instruction:

1. (i, a, X, nop, j)

2. (i, a, X, pop, j)

3. (i, a, X, push(Y), j)

4. (i, L, X, pop, j).

TM Instruction:

1. (i, (a, X), (a, X), (R, S), j)

2. (i, (a, X), (a, L), (R, R), j)

3. (i, (a, X), (a, X), (S, L), k) and (k, (a, L), (a, Y), (R, S), j)

4. For each letter a: (i, (a, X), (a, L), (S, R), j).

a

input

X

stack

*

*

Nondeterministic Turing Machines

Example. Generate an arbitrary string over {a, b} of length n.

Solution: Assume the input is any string over {a, b} of length n. The tape head is at the right

end of the output string.

(0, a, a, R, 0)

(0, a, b, R, 0)

(0, b, a, R, 0)

(0, b, b, R, 0)

(0, L, L, L, halt).

Nondeterministic TMs have the same power as deterministic TMs

The idea: Any nondeterministic TM can be simulated by a deterministic TM that simulates

all 1-step computations, then all 2-step computations, and so on. The process stops if some

computation enters the halt state.

*

*

Section 12.2 The Church-Turing Thesis

The Church-Turing Thesis: Anything that is intuitively computable can be be computed by a

Turing machine.

It is a thesis rather than a theorem because it relates the informal notion of intuitively

computable to the formal notion of a Turing machine.

Computational Models

A computational model is a characterization of a computing process that describes the form a

program and describes how the instructions and are executed.

Example. The Turing machine computational model describes the form of TM instructions

and how to execute them.

Example. If X is a programming language, the X computational model describes the form of a

program and how each instruction is executed.

Equivalence of Computational Models

Two computational models are equivalent in power if they solve the same class of problems.

Any piece of data for a program can be represented by a string of symbols and any string of

symbols can be represented by a natural number.

So even though computational models may process different kinds of data, they can still be

compared with respect to how they process natural numbers.

We’ll make the assumption that there is an unlimited amount of memory available. So we can

represent any natural number or any finite string.

Each of the following models of computation is equal in power to the TM model.

*

*

The Simple Programming Language

This imperative programming model processes natural numbers. The language is defined as

follows:

  • Variables have type N.
  • Assignment statements: X := 0; X := succ(Y); X := pred(Y). (assume pred(0) = 0)
  • Composition of statements: S1; S2.
  • while X ≠ 0 do S od.

This simple language model has the same power as the Turing machine model.

For input and output use the values of the variables before and after execution.

Example/Quiz. To demonstrate the power of this language, define the following macros.

Some Macros Macro Expansion

X := Y

X := 2

Z := Z + X

Z := X + Y

Z := X monus Y

while X < Y do S od

if X ≠ 0 then S1 else S2 fi

X := succ(Y); X := pred(X).

X := 0; X := succ(X); X := succ(X).

C := X; while C ≠ 0 do Z := succ(Z); C := pred(C) od.

Z := X; C := Y; while C ≠ 0 do Z := succ(Z); C := pred(C) od.

Z := X; C := Y; while C ≠ 0 do Z := pred(Z); C := pred(C) od.

T := Y monus X; while T ≠ 0 do S; T := Y monus X od.

U := X; V := 1;

while U ≠ 0 do S1; V := 0; U := 0 od;

while V ≠ 0 do S2; V := 0 od.

*

*

Partial Recursive Functions

This model consists of a set of functions that take natural numbers as arguments and as

values. The functions are defined as follows, where x can represent zero or more arguments.

  • Initial functions: zero(x) = 0, succ(n) = n + 1, and projections (e.g., p2(a, b, c) = b).
  • Composition: e.g., ƒ(x) = h(g1(x), …, gm(x)), where h, g1, …, gm are partial recursive.
  • Primitive recursion:

ƒ(x, 0) = h(x) (h is partial recursive)

ƒ(x, succ(y)) = g(x, y, ƒ(x, y)) (g is partial recursive).

  • Unbounded search (minimalization):

ƒ(x) = min(y, g(x, y) = 0) (g is total partial recursive).

This means that ƒ(x) = y is the minimum y such that g(x, y) = 0, if such a y exists.

This model for constructing functions has the same power as the Turing machine model.

Example. The predecessor and monus functions are partial recursive as follows:

pred(0) = 0

pred(succ(y)) = y, which can be written in the form p1(y, pred(y)).

monus(x, 0) = x

monus(x, succ(y)) = pred(monus(x, y)), which can be written pred(p3(x, y, monus(x, y))).

Quiz. Show that pred(monus(x, y)) = monus(pred(x), y)).

Proof: The equation is true if x = 0 or y = 0. So assume x > 0 and y > 0. Then we have:

pred(monus(x, y)) = if x > y then x – y – 1 else 0

monus(pred(x), y)) = if x – 1 > y then x – 1 – y else 0.

Although x > y and x – 1 > y are different, the if-then-else values are equal. QED.

*

*

Quiz. Let p and q be partial recursive with p(x), q(x)  {0, 1}, for false and true. Show that

the logical operations p(x)  q(x), ¬ p(x), and p(x)  q(x), are partial recursive functions.

Solutions: p(x)  q(x) = p(x)q(x)

¬ p(x) = monus(1, p(x))

p(x)  q(x) = p(x) + monus(1, p(x))q(x).

Examples (Unbounded Search, Minimalization)

ƒ(x) = min(y, xy = 0) defines ƒ(x) = 0.

ƒ(x) = min(y, x + y = 0) defines ƒ(x) = if x = 0 then 0 else undefined.

ƒ(x) = min(y, monus(x, y) = 0) defines ƒ(x) = x.

ƒ(x) = min(y, monus(y, x) = 0) defines ƒ(x) = 0.

ƒ(x, y) = min(z, monus(x + z, y) = 0) defines ƒ(x, y) = if x ≤ y then 0 else undefined

Example/Quiz. For y ≠ 0, let ƒ(x, y) = min(z, monus(x, yz) = 0). What function does ƒ compute?

Answer: ƒ(x, y) =  x / y . To see this, notice that the definition

ƒ(x, y) = min(z, monus(x, yz) = 0)

means that ƒ(x, y) = z is the smallest natural number such that monus(x, yz) = 0.

The definition of monus tells us that

monus(x, yz) = 0 means that x ≤ yz.

So z is the smallest natural number such that x ≤ yz. In other words, we have

y(z – 1) < x ≤ yz.

Divide by y to obtain z – 1 < x/y ≤ z. Therefore z =  x / y .

*

*

Markov Algorithms

This model processes strings. An algorithm consists of a finite, ordered, sequence of

productions of the form x  y, where x, y  A* for some alphabet A.

Any production can be suffixed with (halt) although this is not required.

Execution

Given an input string w  A*, perform the following execution step repeatedly.

Scan the productions x  y sequentially to see whether x occurs as a substring of w. If so,

replace the leftmost occurrence of x in w by y and reset w to this string. Otherwise halt.

If the x  y is labeled with (halt), then halt.

Assumption: w = Lw. So a production of the form L  y would transform w to yw.

The Markov algorithm model has the same power as the Turing machine model.

Example. The Markov algorithm consisting of the single production a  L will delete all a’s

from any string.

Example. A more instructive Markov algorithm to delete all a’s from any string over {a, b}

can be written as the following sequence of productions (# is an extra symbol).

1. #a  #

2. #b  b#

3. #  L (halt)

4. L  #.

An example trace: abab (input)

#abab (by 4)

#bab (by 1)

b#ab (by 2)

b#b (by 1)

bb# (by 2)

bb (by 3, halt).

*

*

Quiz (1 minute). Find a Markov algorithm to replace each a with aa in strings over {a, b}.

Answer. Modify the previous example: 1. #a  aa#

2. #b  b#

3. #  L (halt)

4. L  #.

Example/Quiz. Find a Markov algorithm to delete the rightmost b from strings over {a, b}.

Solution: 1. #a  a#

2. #b  b#

3. #  @

4. a@  @a

5. b@  L (halt)

6. @  L (halt)

7. L  #.

Example/Quiz. Find a Markov algorithm to implement succ(x), where x is a natural number

represented in binary. Assume no leading zeros (except 0 itself).

Solution: 1. #0  0#

2. #1  1#

3. 0#  1 (halt)

4. 1#  @0

5. 1@  @0

6. 0@  1 (halt)

7. @  1 (halt)

8. L  #.

*

*

Post Algorithms

This model processes strings. An algorithm consists of a finite set of productions of the

form s  t where s and t are strings over the union of an input alphabet A with a set of

variables and other symbols. Restriction: If a variable X occurs in t then X occurs in s. A

production can be suffixed with (halt) although this is not required.

Execution

Given an input string w  A*, perform the following execution step repeatedly.

Find a production x  y such that w matches x.

If so, use the match and y to construct a new string w. Otherwise halt.

If the x  y is labeled with (halt), then halt.

Assumption: A variable may match L.

Example. If the input string is 1, then 1 matches 1X. So a production like 1X  1X0 would

transform 1 into 10.

The Post algorithm model has the same power as the Turing machine model.

Example. A Post algorithm with the single production XaY  XY will delete all a’s from

any string. Notice the nondeterminism.

Example. A Post algorithm to replace each a with aa in strings over {a, b}.

Solution: 1. aX  @aa#X

2. bX  @b#X

3. X#aY  Xaa#Y

4. X#bY  Xb#Y

5. @X#  X (halt).

*

*

Example. A Post algorithm to delete the rightmost b from any string over {a, b}.

Solution: 1. Xb  X (halt)

2. Xa  X#a@

3. Xa#Y  X#aY

4. Xb#Y@  XY (halt)

5. #X@  X (halt).

Example/Quiz. Find a Post algorithm to implement succ(x), where x is a natural number

represented in binary. Assume no leading zeros (except 0 itself).

Solution: 1. X0  X1 (halt)

2. X1  X#0#

3. X1#Y#  X#0Y#

4. X0#Y#  X1Y (halt)

5. #Y#  1Y (halt).

Post Systems

This model generates a set of strings from axioms (a given set of strings) and inference

rules (a given set of productions that map strings to strings by matching).

Execution: Match the left side of a production with an axiom string or a string that has

already been constructed. Then use the match and the right side to construct a new string.

Example. A Post system to generate the binary representations of natural numbers:

Axioms: 0, 1

Inference Rules: 1X  1X0

1X  1X1.

The system generates the set {0, 1, 10, 11, 100, 101, 110, 111, … }.

*

*

Quiz. Find a Post system to generate {a}*.

Solution: Axiom: L

Inference rule: X  aX.

Quiz. Find a Post system to generate the set {anbncn | n  N}.

One of Many Solutions: Axioms: L, abc

Inference rule: aXbcY aaXbbccY.

The Post system model has the same power as the Turing machine model in the following

sense: A function ƒ : A*  A* is Post-computable if there is a Post system to compute the

function as a set of ordered pairs in the form {x#ƒ(x) | x  A*}. Post-computable functions

coincide with Turing-computable functions.

Example/Quiz. Generate the function ƒ : {a}*  {a}* where ƒ(an) = a2n.

Solution: Axiom: L#L

Inference rule: X#Y  Xa#Yaa (or the simpler X  aXaa)

This system generates the set {L#L, a#aa, aa#aaaa, …, an#a2n, … }.

Example/Quiz. Generate the function ƒ : N  N defined by ƒ(n) = n2, where n is

represented as a string over {a} of length n.

A Solution: Axiom: L#L

Inference rule: X#Y  Xa#YXXa.

Proof: In terms of natural numbers, from the pair n#n2 we must construct (n + 1)#(n + 1)2.

We can write (n + 1)2 = n2 + 2n + 1 = n2 + n + n + 1.

So from n#n2 we must get (n + 1)#(n2 + n + n + 1).

In terms of strings over {a}, we transform X#Y into Xa#YXXa. QED.

*

*

Section 12.3 Computability

Some problems cannot be solved by any machine/algorithm.

To prove such statements we need to effectively describe all possible algorithms.

Example (Turing machines). Associate a Turing machine with each n  N as follows:

n  b(n) (the binary representation of n)

 a(b(n)) (b(n) split into 7-bit ASCII blocks, with leading zeros if needed)

 if a(b(n)) is the syntax of a TM then a(b(n)) else (0, a, a, S, halt) fi.

So we can effectively describe all possible Turing machines:

T0, T1, T2, …

Of course we could use the same technique to list all possible instances of any computational

model. For example, we can effectively list all possible simple programs and we can

effectively list all possible partial recursive functions.

If we want to use the Church-Turing thesis, then we can effectively list all possible solutions

(e.g., Turing machines) to every intuitively computable problem.

Decision Problems

A decision problem is a problem can be phrased as a yes/no question.

Such a problem is decidable if an algorithm exists to answer yes or no to each

instance of the problem. Otherwise it is called undecidable.

A decision problem is partially decidableif an algorithm exists to halt with the answer

yes to yes-instances of the problem, but may run forever if the answer is no.

*

*

Examples. 1. Is an arbitrary propositional wff a tautology? Decidable.

2. Is an arbitrary first-order wff valid? Undecidable and partially decidable.

3. Does a DFA accept infinitely many strings? Decidable.

4. Does a PDA accept a string s? Decidable.

The Halting Problem

The halting problem asks the following question.

Does an arbitrary program halt on an arbitrary input?

The halting problem is partially decidable: Just execute the program on the input. If the

program halts, output yes.

The halting problem is undecidable.

To prove this, we’ll prove the following form for computable functions.

Is there a computable function that can decide whether an arbitrary computable function

halts on an arbitrary input?

Proof: Assume, BWOC, that the halting problem is decidable. We’ll use the following

effective listing of all computable functions of a single variable.

ƒ0, ƒ1, ƒ2, …

Define the partial function g by

g(n) = if ƒn(n) halts then loop forever else 0 fi.

Observe that g is computable because “ƒn(n) halts” is computable by assumption.

So there is some k such that g = ƒk. Now apply g to k to obtain a contradiction:

g(k) halts iff g(k) does not halt. Therefore the halting problem is undecidable. QED.

*

*

Example/Quiz. Given the following effective listing of all Turing machines.

T0, T1, T2, …

Is it decidable whether Tn halts on some input string of a’s within k steps?

Answer: Yes. Perform the following algorithm.

l := 0; (l represents the length of an input string of a’s. So the tape is initially empty.)

while l ≤ k do

Execute Tn for k steps or until the halt state is reached, whichever comes first;

If the halt state was reached, stop and output the answer YES;

l := l + 1 (Reset the tape with one more a)

od;

Output the answer NO.

Notice: If the while loop terminates without stopping with a YES-answer, then l > k.

In this case Tn will take more than k steps to process l cells with a’s. So the answer is NO.

Some Total Problems

There is no effective listing of the total computable functions.

Proof: To see this for total computable functions of a single variable, assume, BWOC, that

we have the following effective listing of these functions.

ƒ0, ƒ1, ƒ2, …

Define g(n) = ƒn(n) + 1. Since ƒn is total, it follows that g is total too. Therefore g must be

somewhere in the list. So there is some k such that g = ƒk. But then ƒk(k) = g(k) = ƒk(k) + 1,

which is a contradiction. QED.

*

*

The total problem asks whether an arbitrary computable function is total.

The total problem is undecidable.

Proof: Assume, BWOC, that the total problem is decidable. We’ll use the effective listing of

all computable functions of a single variable ƒ0, ƒ1, ƒ2, … . Now define the function

T(n) = if ƒn is total then 1 else 0 fi.

Since “ƒn is total” is computable by assumption, it follows that T is total too. But now we can

effectively list all the total computable functions from the given list as follows:

Let g0 be the smallest k such that T(k) = 1;

Let g1 be the smallest k > g0 such that T(k) = 1;

Let g(n +1) be the smallest k > gn such that T(k) = 1.

Continue in this manner to construct the list ƒg0, ƒg1, …, ƒgn, … of all total computable

functions of a single variable. But this contradicts the fact that it can’t be done. QED.

Example/Quiz. Show that we can’t effectively list the total computable functions that have

finite ranges. For example, ƒ(n) = n mod 4 has range {0, 1, 2, 3}.

Proof: Suppose, BWOC, that ƒ0, ƒ1, ƒ2, … is an effective listing of the single-variable

computable functions with finite range. Now define the function

g(n) = if ƒn(n) ≤ 25 then ƒn(n) + 1 else 25 fi.

Observe that g is total, computable, and has finite range. So there is some k such that g = ƒk.

Quiz: What is the contradiction?

Answer: If ƒk(k) ≤ 25 then ƒk(k) = ƒk(k) + 1. If ƒk(k) > 25 then ƒk(k) = 25. QED.

*

*

Post Correspondence Problem (PCP)

Given an arbitrary finite sequence (s1, t1), …, (sn, tn) of pairs of strings, does there exist a

sequence of indices i1, …, ik, with repetitions allowed, such that si1…sik = ti1…tik?

Example/Quiz. Does the following instance of the PCP have a solution?

(ab, b), (b, a), (a, ab), (ba, b).

Answer: Yes. If the pairs are labeled 1, 2, 3, 4, then the sequence 3, 2, 1 gives the equation

abab = abab.

Quiz. Does the following instance of the PCP have a solution?

(a, aa), (aaaa, a).

Answer: Yes. If the pairs are labeled 1, 2, then the sequence 1, 1, 1, 2 gives the equation

aaaaaaa = aaaaaaa.

The Post correspondence problem is undecidable for alphabets of size 2 or more.

The proof involves reducing the problem to the halting problem.

The PCP is also used in proving that it is undecidable to tell whether a context-free grammar

over an alphabet of size 4 or more is ambiguous.

Details of these two proofs can be found in: Harrison, Introduction to Formal Language

Theory, Addison Wesley, 1981.

*

*

Section 12.4 A Hierarchy of Languages

Context-Sensitive Languages

A context-sensitive grammar has productions of the form xAz  xyz, where A is a

nonterminal and x, y, z are strings of grammar symbols with y ≠ . The production S   is

also allowed if S is the start symbol and it does not appear on the right side of any

production. A context-sensitive language has a context-sensitive grammar.

Example. The following grammar is context-sensitive.

S  aTb | ab

aT  aaTb | ac.

Quiz. What is the language of the grammar?

Answer: {ab}  {an+1cbn+1 | n  N}. This language is context-free. For example, it has the

grammar S  aTb | ab, and T  aTb | c.

Any context-free language is context sensitive.

Example. {anbncn | n ≥ 0} is context-sensitive but not context-free. Here is a csg.

S   | abc | aTBc

T  abC | aTBC

CB  CX BX  BC

bB  bb.

Cc  cc.

Quiz. Derive aaabbbccc.

Answer: S  aTBc  aaTBCBc  aaabCBCBc  aaabBCCBc  aaabBCBCc

 aaabBBCCc  aaabbBCCc  aaabbbCCc  aaabbbCcc  aaabbbccc.

*

*

Linear Bounded Automata (LBA)

A linear bounded automaton (LBA) is a Turing machine that may be nondeterministic and

that restricts the tape to the length of the input with two boundary cells that may not change.

Example. An LBA to check whether a natural number n is divisible by k ≠ 0.

Idea for a Solution: Use a 2-tape (or 2-head single tape) machine. For ease of explanation,

represent k by the nonempty string 1k and represent n by the string an. For example, if k = 3

and n = 9, the input is represented by,

111 a a a a a a a a a

If n = 0, which is represented by L, then halt. Otherwise, move both tape heads to the right k

places while there are a’s to read. Then leave the tape head for a’s in place and move the tape

head for k back to the left end and start the process over. Continue in this manner and enter

the halt state if both tape heads point to L.

Theorem: The context-sensitive languages are exactly the languages that are accepted by

linear bounded automata (LBA).

Example/Quiz. Find an LBA to accept {ap | p is prime}.

Idea for a Solution: Use the the divisibility algorithm in the previous example to implement

the following algorithm, where p ≥ 2.

k := 2;

while k < p do

if k divides p then stop (but don’t enter the halt state) else k := k + 1 fi

od;

Enter the halt state (accept).

*

*

Recursively Enumerable Languages

An unrestricted grammar has productions of the form s  t, where s ≠ L. So any grammar is

Get professional nursing essay writing service and professional nursing term paper writing service