**Lecture 3
(Finite State Automata), 9/6/17**

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

·
*Regular Language - *language
*specified* by some RE

·
The
mapping between the sets of Regular Expressions and Regular Languages (onto,
not one-to-one)

·
When
are two expressions equivalent? Not
equivalent?

o
Two
sets are different if one of them has an element that the other one does not.

- Extending
regular expressions notation
*: R*^{+}, R^{k},**S** - S* - the set of all
strings over alphabet S
- Applications for REs:
- pattern matching
template when searching for substrings, for a utility such as
*grep* - specifying syntax of
programming language tokens, for a compiler or interpreter

·
Are all languages regular? *NO*!
There exist languages that are not regular.

o
*We
will prove it in several different ways, but not yet*

·
*Finite
state automata*
(FSAs) - states, input characters, transitions

·
*3
FSA representations: diagram, table, formal (set-based)*

o
To make the table-based description complete, list
the initial state first, and circle the final states.

·
Computations
are *sequences* of transitions, with
one input character per transitions

o
The
number of transitions equals the length of the input string

·
A
string w is *accepted* by an FSA M if the computation of M on w ends in a
final state

·
L(M),
the language *accepted* by FSA M, is the set of strings accepted by it

**Reading and homework**:

- (FSAs) Sipser sec. 1.1 through
fig. 1.22
- Note: Definition 1.16
is an alternate definition of a regular language; we will prove that the
two definitions are equivalent.
- Note: the book defines
transitions differently than we did in class, use our definition
- Start Homework 1 (due next
Wednesday)

**Skills**:

·
Know
new definitions, understand new concepts

·
Write
a formal (set-based) FSA description from an FSA diagram and vice versa

·
Write
FSA table from an FSA diagram and vice versa

·
Determine
whether a given string is accepted by a given FSA

·
Describe
the language accepted by a given FSA

**Notes**:

- For any regular language, there may be
*multiple*regular expressions that specify it; simpler ones are*preferable*. - The formal description of an FSA is a quintuple (
**Q,****S****,****d****, q**)_{0}, F