Final Review

A question on finite state machine with output and/or on finite state automaton

Create a finite state machine

Given a finite state automaton check to see if the language can recognize a given string

Nothing on non-deterministic automata

Recurrence relations: A problem similar to the one on assignment. Mostly from the exercises at the end of section 5.2

Go through review for the second test and do those which were not covered in the second test

The review for test - 1 is somewhat sketchy so the detail follow:

Definition of the relations

What is an equivalence relation what is a partial order

Operations on relations

Theorem 1 (6.1)

Expect a simple proof.

Given one representation draw another one

Given a partial order draw a Hasse diagram and figure out if it is a lattice. Other questions similar to the assignment.

Given a Hasse diagram right down the relation.

Definitions from section 7.1 and 7.2: questions that test your understanding of the definition.

Given two graphs tell whether they are isomorphic.