**Lecture
4 (DFAs vs. NFAs), 1/25/18**

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

- The formal description of an FSA is a quintuple (
**Q,****S****,****d****, q**)_{0}, F - Note: the book defines
**d**differently than we do, use our definition *3 FSA representations: diagram, table, formal (set-based)**Valid*,*accepting*FSA computations (formal definitions)- Invalid vs. valid vs.
accepting computations
- FSA
*transitions*-- triples (q1, c, q2) for q1 in**Q**, q2 in**Q**, c in**S** - Computations are
*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- The computation of M of any w is
*unique* - w is
*accepted*by a DFA M if the computation of M on*w*in accepting - L(M), the language accepted by M is {w in
**S**: M accepts w}^{*} *Nondeterministic Finite State Automata*(NFAs) -- 0 or more transition for given (state, character) pair

o DFAs are special cases of
NFAs, but not vice versa

·
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
- Unlike DFAs, NFAs are
*non-constructive*(it is not straightforward to simulate them) - Example where nondeterminism helps:
*w*ends in (or contains) a substring*w*' - DFAs are special cases of
NFAs, but not vice versa

**Reading and Homework**:

- (NFA) sec 1.2 up to "equivalence of NFAs and
DFAs" section
- Finish Homework 1 (due next Tuesday 1/30)

**Skills:**

- Know new definitions, understand new concepts
- Write a formal (set-based) FSA description from an FSA
diagram and vice versa
- Given an FSA, determine whether or not it is
deterministic
- Figure out if a given string is accepted by a given FSA
(NFA or DFA)
- Describe the language accepted by a given FSA (NFA or
DFA)

**Notes:**

- A computation of an FSA
*M*on input string*w*is a sequence of transitions (d_{1}, d_{2}, .. d_{k}) - Each transition d
_{i}is a member of**d** - Let (d
_{1}, d_{2}, .. d_{k}) be a computation of FSA*M*, 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 > 1, q
_{i}= q'_{i-1}(i.e., each next transition d_{i+1}starts where previous one d_{i}_{ }ended) - for all i, c
_{i}= w[i] (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*: the book's definition views**delta**as a mapping; we view**delta**as a set of triples.