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