>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 04 [Text Version]

[About] [Contact] [Grades] [Projects] [Submit] [Schedule] [Syllabus] [Search

Session: [01] [02] [03]

Thu Jun 8 13:02:49 PDT 2006

- Session 4 -- Review of Automata
- : Context
- : Chapter 2 Finite Automata
- : : 2.1 Informal Picture
- : : Ch 2 pp 45 -- What exactly is a Product Automaton?
- : : 2.2 DFAs -- Deterministic Finite Automata
- : : Request for a lecture
- : : Ch 2.2.2 pp 46-47 -- DFA
- : : Ch 2 pp 53-53 -- Exercise 2.2.1 - Transition Table
- : : 2.3 NFA -- Nondeterministic Finite Automata
- : : Ch 2 pp 58-59 -- The Extended Transition Function
- : : Ch 2 pp 49-58 -- extended transition function
- : : Ch 2.3 pp 66 -- Pigeonhole Principle
- : : 2.4 Application - grep
- : : Ch 2 pp 69-70 -- Finite Automata
- : : 2.5 epsilon-transitions
- : : Ch 2 pp -- Epsilon Transitions
- : : Ch 2 pp 72-79 -- Epsilon Transitions
- : Chapter 6 Section 6.1 Push Down Automata
- : : Ch 6 pp 221-222 -- PDA
- : : Ch 6 pp 219-222 What is the function of a pushdown automata?
- : : Ch 2+6 -- deadline for automata questions
- : : Ch 2 pp 55 -- Nondeterministic Finite Automata
- Next -- Turing Machines
- Standard Definitions
- From Logic

- 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...)
- 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.
- A = (...??...) where

Net- ...

(End of 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 [ auto1.cpp ] is the example from section 2.2 coded up as directly as possible in C++ by abuse(?) of the STL.

State 0 1 q0 q2 q0 q1 q1 q1 q2 q2 q1 ### 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: [ 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.

- It gave me pause for thought when I was trying the exercise before going to the site.
- I also miscalculated 6 or 7 transitions.... :-(

### 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.

- FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
- ND::="Non-deterministic", a machine that can try out many possibilities
and always guesses the right choice. Note: For a given problem
a
*ND*solution is simpler and easier to understand than a deterministic one. We study*ND*machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun. - PDA::="Push down Automata", a machine with a finite control and a
single stack for remembering intermediate data. Kind of like half a
*TM*. - RJB::=
*The author of this document*, [ ../index.html ] - |-
*RJB*="Richard J Botting, Comp Sci Dept, CSUSB". - Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
- Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
- Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
- TBA::="To Be Announced".
- TM::="Turing Machine".
- NTM::="Nondeterministic Turing Machine".
- nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
- DTM::="Deterministic Turing Machine".
- runtime::=
*run_time*, - run_time::="The number of steps a TM takes before it halts when start on a given input".
- complexity::="The largest
*run_time*for any word with a given length" , usually expressed as an assymptotic (Big-O) formula. - P::@problem=
*class of problems that a*.*DTM*can compute in*polynomial_time* - NP::@problem=
*class of problems that a*.*NTM*can compute in*polynomial_time* - polynomial_time::=
*An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c*.# From Logic

- LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html
- (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can
substitute a new variable for it.
- (LOGIC)|- (eg): existential generalization -- if P is true of this thing then
it is true of something!
- (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument.
Typically
*if A and B and C then D*starts with assuming A,B, and C are*given*. They are called the hypotheses. - (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after
the
*then*in an*if...then...*result. This is called the conclusion. - (LOGIC)|- (def): By definition of a term defined above.
- (LOGIC)|- (algebra): Either by using well known algebraic results, or by
use a series of algebraic steps.
- (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.

Date | # | Study(2 pts) | Bring(5 pts) | Topic(5 pts) | Notes |
---|---|---|---|---|---|

Previous | 3 | Preface+Web1 | URL | History | Exam on math(50 pts) |

Today | 4 | Chapter 2+Chapter 6 section 6.1 | Ex | Automata | |

Next | 5 | Chapter 8 sections 8.1, 8.2 | Ex | Turing Machines |

"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:

- | a | b | c | d |
---|---|---|---|---|

1 | 1a | 1b | 1c | 1d |

2 | 2a | 2b | 2c | 2d |

3 | 3a | 3b | 3c | 3d |

Whenever you see a problem that reads something like this

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:

I'll prepare a short lecture+activities.

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*:

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:-)

(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>

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

*. . . . . . . . . ( end of section Session 4 -- Review of Automata) *<<Contents | End>>