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.

         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:


         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