**Lecture
4 (NFAs), 9/11/17**

**Concepts, definitions (in italics):**

*Valid*,*accepting*FSA computations (formal definitions)- Accepting vs. valid
vs. invalid computations

·
*Contrapositive* of a statement

- FSA
*transitions*– triples in Q x S x Q - Computations as
*sequences*/lists of transitions - Can write them out as
chains for shorthand
*Deterministic Finite State Automata*(DFAs) – exactly one transition for given (state, character) pair- w is
*accepted*by a DFA M if the computation of M on*w*in accepting *Nondeterministic Finite State Automata*(NFAs) – 0 or more transition for given (state, character) pair

·
Unlike DFAs, NFAs are *non-constructive*
(it is not straightforward to simulate them)

o Also,
cannot use the same table format to represent an NFA

*Epsilon-transitions*- w is
*accepted*by a NFA M if*there exists*an accepting computation of M on w - L(M), the language
*accepted*by FSA M, is the set of strings accepted by it - This works whether FSA
is deterministic or non-deterministic
- Example where nondeterminism helps:
*w*ends in (or contains) a substring*w*'

**Reading and Homework**:

- (NFA) sec 1.2 through example 1.38
- Finish Homework 1 (due next Tuesday)

**Skills:**

- Know new definitions, understand new concepts
- Given an FSA, determine whether or not it is
deterministic
- Figure out if a given string is accepted by a given FSA
- Describe the language accepted by a given FSA
- Using the definition of computation, prove simple
statements about languages of FSAs

(what happens if q_{0}is in F, or if F is empty, or if F = Q) - Construct an DFA or an NFA for a given language

**Notes:**

- A computation of an FSA
*A*on input string*w*is a sequence of transitions (d_{1}, d_{2}, .. d_{k}) in*A* - Each transition d
_{i}is a member of**delta** - Let (d
_{1}, d_{2}, .. d_{k}) be a computation of FSA*A*, where d_{i}= (q_{i}, c_{i}, q’_{i}). It is*valid*if: - q
_{1}is the initial state (i.e., 1st transition starts at initial state) - for all i < k, q’
_{i}= q_{i+1}(i.e., each next transition d_{i+1}starts where previous one d_{i}_{ }ended) - c
_{1}c_{2}… c_{k}= w (i.e. the labels along this sequence of transitions "spell out"*w*) - A valid computation is
*accepting*if - q’
_{k}is in F (i.e. the last transition d_{k}ends at final state). - For any regular language, there may be
*multiple*Finite State Automata that accept it; FSAs with fewer states are preferable.

·
*Note*: just as for DFAs, the book's
definition of NFAs views **delta**
as a mapping; we continue to view **delta**
as a set of triples.