Part 1: Automata and Languages

Chapter 1: Regular Languages

Section 1.1a: Finite Automata and Regular Languages



Part One Goals



Part One Goals - Ways to Define a Language

  1. List the strings. Examples: ...

  2. English:

  3. Build a machine that tests whether a string is or is not in the language

  4. Regular Expressions (Section 1.3)

  5. Grammars (Chapter 2)


Chapter 1 Goals - Language Goals

  1. Given a language, define a machine that defines that language

  2. Given a machine, determine the language that it defines


Chapter 1 Tasks



Section Goals



Finite State Machines




Example Finite Automata: Door Controller



Computations Using Strings



Examples Revisited



Finite Automata: More Examples



States Provide Limited Memory



Designing Finite Automata



Designing Finite Automata: Examples



Precisely Defining a Finite Automata - What to Specify?



Finite Automata: Formal Definition



Formal Definition and Empty Sets A



Machine M Recognizes/Accepts a String



Machine M Recognizes a Language

Machine M Accepts a Language

L(M) = A



Computation: Formal Definition of Accepts



Regular Language: Definition



Questions on Regular Languages





ITEC 420 Course Page,
Last modified on