.Open Session 4 -- Review of Automata
. Context
.Table Date
.Item #
.Item Study(2 pts)
.Item Bring(5 pts)
.Item Topic(5 pts)
.Item Notes
.Row Previous
.Item 3
.Item Preface+Web1
.Item URL
.Item History
.Item Exam on math(50 pts)
.Row Today
.Item 4
.Item Chapter 2+Chapter 6 section 6.1
.Item Ex
.Item Automata
.Row Next
.Item 5
.Item Chapter 8 sections 8.1, 8.2
.Item Ex
.Item Turing Machines
.Close.Table

.Open Chapter 2 Finite Automata
. 2.1 Informal Picture
. Ch 2 pp 45 -- What exactly is a Product Automaton?
Is it different from a DFA or is it 
just another way to say DFA?

"Product Automata" is not another way to say DFA!

A product automaton is the result of combining other automata.  Like
the product of 3 and 4 is 12...  Indeed the number of states in the
product automata is equal to the product of the number of states
in the separate automata.  For example the product of states{1,2,3}
with {a,b,c,d} is {(1,a), (2,a), (2,a),(3,a), (1,b),....(3,d)} with
12 states.  These are best diagrammed in a grid:
.Table -	a	b	c	d
.Row 1	1a	1b	1c	1d
.Row 2	2a	2b	2c	2d
.Row 3	3a	3b	3c	3d
.Close.Table

Whenever you see a problem that reads something like this
.As_is 	Accept strings with an even number of 1'a and an odd number of zeroes.
you should think about designing two automata: one for each part of the
problem and then calculating the product.  

Exercise can you find the example later in the book and the exercise
that needs a product automata?

You can't take this kind of product of two automata unless they have
the same input alphabet.

The product of two automata (Q1,Sigma,delta1,q1,F1) and (Q2,Sigma,delta2, q1, F2) is constructed like this:
.Set
	Take the Cartesian product of the state spaces: Q12 = Q1><Q2,
	The typical state is (x,y) where x is in Q1 and y is in Q2.
	The product automata has the same set of input symbols as each automata.
	The transitions of the product combine the separate transitions:
if the first goes from a to b with input c, and the second
from d to e then the product goes from (a,d) +> (b,e).
	((x,y),a) +> (delta1(x,a), delta2(y,a)).
	Initial state is the pair of initial states. (q1,q2)
	The final states are those pairs (x,y) such that both x and y
are accepted in their own machine.  F1><F2.
	OR perhaps the product can accept when any component accepts
(diagram on board...)
.Close.Set

. 2.2 DFAs -- Deterministic Finite Automata
. Request for a lecture
I don't understand  deterministic finite automata especially  processing
strings,and everything else. Dr. Botting it will really help if you lecture
on ch. 2.

I'll prepare a short lecture+activities.
.Set
	We are modeling machines that have a memory of the past.
	The memory is modeled by a set of states.
	The state changes:  when an input appears.
	The change of state depends on the input.
	We can tabulate how each input effects the state.
	We talk of a string of inputs... one after another.
	Automata classify the strings as accepted or rejected.
	(General machines can have outputs other than yes/no).
	The accept/reject is based solely on the state of the memory.
.Close.Set

In this subject it pays to take careful note (on paper, in a file, ...)
of all the formal definitions.  An example is on page 46.

Exercise: With out looking in the book write down the
formal definition of a `deterministic finite automaton`:
	A = (...??...) where
.Net
	...
.Close.Net

Now check your answer with the book.

We made a study of all the binary automata: Q={p,q}, Sigma={0,1},
q0=p.  They differ in the choice of F and delta.  If F={} the
language is {}.  If F={p,q} then the language is Sigma* (all strings).
The interesting automata are when F={p} or F={q}.  We noticed that
changing F from {p} to the {q} and vice versa complements the language.
So just consider F={p} --- so that the empty string epsilon is
accepted.   Then we went to study the effect of choosing delta.
If delta(p,0)=p and delta(p,1)=q then the language is Sigma* (again).
The rest tended to be either parity machines: (accept even strings, strings
with even 0s, strings with even 1s), or `latches`: reject the first 1,
reject the first 1, reject any string with a 1, any string with a zero,
reject all strings with more than 1 symbol.

Here
.See ./auto1.cpp
is the example from section 2.2 coded up as directly as possible
in C++ by abuse(?) of the STL.
.Table State	0	1
.Row q0	q2	q0
.Row q1	q1	q1
.Row q2	q2	q1
.Close.Table

. Ch 2.2.2 pp 46-47 -- DFA
Example 2.1 states:
{w | w is of form x01y for some strings x and y consisting of 0's and 1's
ONLY}
then it states:
strings in the language include 01. Is that true? If true doesn't that mean
x and y are empty strings ? If they are empty strings shouldn't it be noted
in the language ?

Just because "01" is accepted doesn't mean that "00000001000000" is
rejected.

Further,  the empty string is just another string (when a theorist is 
talking).

By the way: when you program -- make sure your code handles the null
cases gracefully!


. Ch 2 pp 53-53 -- Exercise 2.2.1 - Transition Table
I'm confused about the answer to Exercise 2.2.1a and how the transition 
table is derived. Part a is a starred exercise (*) and the answer is on the
following link:
.See http://www-db.stanford.edu/~ullman/ialcsols/sol2.html
Why are some of the rows repeated where the only difference between them is
an 'accepted' or 'rejected' symbol? Rows 1 to 2, and 4 to 5, are some 
of the rows that I am confused about.

The DFA in this book have no real output.  Just some states are
labeled "accept" and the rest "reject".  So to show where a marble
comes out of the machine you have to code this by attaching it to a state
-- not to a transition.   Now, the position of the levers is not
enough to predict where the marble emerges because it also depends on
where the marble went in.... so you include in the state both
the position of the levers and what happened!  This leads to
both r and a states.

.Set
	It gave me pause for thought when I was trying the exercise before
going to the
site.
	I also miscalculated 6 or 7 transitions.... :-(
.Close.Set
. 2.3 NFA -- Nondeterministic Finite Automata
. Ch 2 pp 58-59 -- The Extended Transition Function
Page 58 has an equation using a large "U" with i=1..k. Is this "U" the 
union symbol used on the next page?

Yes.  The Big U is for Union. It is actually a big "CUP".
In the same way that Sigma does a
whole series of plusses, the big U does a whole series of set unions.

. Ch 2 pp 49-58 -- extended transition function
Would you please explain a little bit more the difference between the DFA 
and NFA's "extended transition function"?

The DFA extende delta-hat function represents a single path thru the
states.  The NFA version tracks all the possible paths.

. Ch 2.3 pp 66 -- Pigeonhole Principle
Can we prove the pigeonhole principle by mathematical induction?

I don't know and it is not important for this class.
. 2.4 Application - grep
. Ch 2 pp 69-70 -- Finite Automata
Which is a more effective when it comes to doing a text search  for 
keywords, using an NFA or a DFA?

We always end up coding a DFA because our hardware is deterministic.
But we use NFA as a high-level design.  In the past I taught
a programming methodology that design all programs as nondeterministic
(just leave out the conditions!) and resolve the "recognition difficulties"
by back-tracking and/or reading-ahead.

. 2.5 epsilon-transitions
. Ch 2 pp -- Epsilon Transitions
I have heard epsilon transitions called "lambda" transitions. Is there a
difference or was it just the preference of the instructor?

It is the choice of the writer whether they us \lambda or \epsilon to
represent the empty string.   Computer scientists and logicians
use \lambda for a totally different purpose and so \epsilon for empty is
what they use.  Grammar and language theorists tend to use \lambda.
. Ch 2 pp 72-79 -- Epsilon Transitions
Could you please go over Epsilon Transitions in general?  Epsilon Closures
are confusing and I don't really understand their purpose.  (Actually I 
haven't taken CSCI 500 so about the last half of chapter 2 is new material
to me.)

I think we can skip them for now.  Essentially they allow the finite
machine to do an internal computation without reading any data.  Useful
is designing solutions to some problems.... but not essential since
we can always get rid of them. We will omit the proof via \epsilon
closures.

.Close
.Open Chapter 6 Section 6.1 Push Down Automata
. Ch 6 pp 221-222 -- PDA
When giving the formal definition of a push-down automata, the book 
doesn't mention anything about what happens if lambda = epsilon but the 
stack X is empty.  Would that be considered an error, or would the 
push-down automata continue happily along?

I'm not sure what lambda is here.... but normally if a PDA attempts
to pop an empty stack it stops and fails.  In other words,
a nondeterministic PDA, the branches that lead to popping an
empty stack die.

Sometimes PDAs are defined without a set of accepting states.  They
accept a string by emptying their stack (and stopping!).

In other words.... this may not be a bug, but a feature:-)

. Ch 6 pp 219-222  What is the function of a pushdown automata?
(1) the missing link between finite automata and Turing Machines.

(2) They model several important algorithms in compilers and interpreters.

(3) Providing employment to theorists in the 1950's and practitioners
in the 1960's onward.

(4) #include <stack>


. Ch 2+6 -- deadline for automata questions
Fewer points after this is received.
. Ch 2 pp 55 -- Nondeterministic Finite Automata
The author says that NFA are usually more succint and easier to design then
DFA's.  Why is that?

A NFA can try out many options at once and keeps track of which options
are open at any time.  This can be done with a DFA but it has to explicitly
do the book-keeping that is implicit in a NFA




.Close
.Close Session 4 -- Review of Automata
. Next -- Turing Machines
.See ./05.html