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