Automata Theory and Computability

CS310 : Automata Theory 2020

Lecture 1: Automata Theory and Computability

Instructor: S. Akshay

IIT Bombay, India

13-01-2020

Automata Theory and Computability

What is this course about?

I Things that compute: Abacus, calculators

I Well, and Computers. How do we model them? I Mathematical models for computation and computers I Why mathematical? why theory?

I Limits of computers and computation I Can a computer do ANYTHING? I Are there things that cannot be solved?

Automata Theory and Computability

What is this course about?

I Things that compute: Abacus, calculators I Well, and Computers.

How do we model them? I Mathematical models for computation and computers I Why mathematical? why theory?

I Limits of computers and computation I Can a computer do ANYTHING? I Are there things that cannot be solved?

Automata Theory and Computability

What is this course about?

I Things that compute: Abacus, calculators I Well, and Computers. How do we model them?

I Mathematical models for computation and computers I Why mathematical? why theory?

I Limits of computers and computation I Can a computer do ANYTHING? I Are there things that cannot be solved?

Automata Theory and Computability

What is this course about?

I Things that compute: Abacus, calculators I Well, and Computers. How do we model them?

I Mathematical models for computation and computers

I Why mathematical? why theory? I Limits of computers and computation

I Can a computer do ANYTHING? I Are there things that cannot be solved?

Automata Theory and Computability

What is this course about?

I Things that compute: Abacus, calculators I Well, and Computers. How do we model them?

I Mathematical models for computation and computers I Why mathematical? why theory?

I Limits of computers and computation I Can a computer do ANYTHING? I Are there things that cannot be solved?

Automata Theory and Computability

What is this course about?

I Things that compute: Abacus, calculators I Well, and Computers. How do we model them?

I Mathematical models for computation and computers I Why mathematical? why theory?

I Limits of computers and computation

I Can a computer do ANYTHING? I Are there things that cannot be solved?

Automata Theory and Computability

What is this course about?

I Things that compute: Abacus, calculators I Well, and Computers. How do we model them?

I Mathematical models for computation and computers I Why mathematical? why theory?

I Limits of computers and computation I Can a computer do ANYTHING?

I Are there things that cannot be solved?

Course Outline

What we plan to cover

1. Finite automata and regular languages/expressions and more...

2. Pushdown automata, context-free grammars and other models of computation

3. Turing machines and computability: the extents and limits of computation

4. Efficient computation: basic complexity classes...

Logistics

Evaluation I Quizzes 30%

I Midsem 25%

I Endsem 40%

I Attendance/Pop quizzes 5%

Recommended text

I Intro to Automata Theory, Languages and Computation: Hopcroft, Motwani, Ullman

I Intro to Theory of Computation: Michael Sipser

Logistics

Evaluation I Quizzes 30%

I Midsem 25%

I Endsem 40%

I Attendance/Pop quizzes 5%

Recommended text

I Intro to Automata Theory, Languages and Computation: Hopcroft, Motwani, Ullman

I Intro to Theory of Computation: Michael Sipser

Logistics (Contd.)

Course material

See https://www.cse.iitb.ac.in/∼akshayss/teaching/cs310-2020

Discussions

I For online discussions: Piazza (To be set up).

I Weekly problem solving session: 1 hour per week (To be fixed by TAs).

I Office hours: by email appointment/weekly hour (TBA).

Module 1: Finite Automata and regular languages

Modeling a computing device :an automaton I Input

I Processing I Output

Example

I Consider a bulb with a switch. I Its input are: on/off

I Behavior during the day is: “on off on off” I When light is off, I can turn it on and vice versa.

Module 1: Finite Automata and regular languages

Modeling a computing device :an automaton I Input

I Processing I Output

Example

I Consider a bulb with a switch.

I Its input are: on/off

I Behavior during the day is: “on off on off” I When light is off, I can turn it on and vice versa.

Module 1: Finite Automata and regular languages

Modeling a computing device :an automaton I Input

I Processing I Output

Example

I Consider a bulb with a switch.

I Its input are: on/off

I Behavior during the day is: “on off on off”

I When light is off, I can turn it on and vice versa.

Module 1: Finite Automata and regular languages

Modeling a computing device :an automaton I Input

I Processing I Output

Example

I Consider a bulb with a switch.

I Its input are: on/off

I Behavior during the day is: “on off on off”

I When light is off, I can turn it on and vice versa.

Inputs

I Domain of inputs/actions: Σ ={on,off} I This is called theAlphabet.

I Elements areLetters.

I Inputs or behaviors are strings or sequences of letters, calledwords. I Example: “on off on off on off” is a word in Σ^∗.

Set of words over Σ

I Σ^∗ =∪_n≥0Σⁿ , i.e., all finite words over alphabet Σ. I What is Σ⁰?

I What is the difference between Σ⁺ and Σ^∗?

Inputs

I Domain of inputs/actions: Σ ={on,off} I This is called theAlphabet.

I Elements areLetters.

I Inputs or behaviors are strings or sequences of letters, calledwords.

I Example: “on off on off on off” is a word in Σ^∗.

Set of words over Σ

I Σ^∗ =∪_n≥0Σⁿ , i.e., all finite words over alphabet Σ. I What is Σ⁰?

I What is the difference between Σ⁺ and Σ^∗?

Inputs

I Domain of inputs/actions: Σ ={on,off} I This is called theAlphabet.

I Elements areLetters.

I Inputs or behaviors are strings or sequences of letters, calledwords.

I Example: “on off on off on off” is a word in Σ^∗.

Set of words over Σ

I Σ^∗ =∪_n≥0Σⁿ , i.e., all finite words over alphabet Σ.

I What is Σ⁰?

I What is the difference between Σ⁺ and Σ^∗?

Inputs

I Domain of inputs/actions: Σ ={on,off} I This is called theAlphabet.

I Elements areLetters.

I Inputs or behaviors are strings or sequences of letters, calledwords.

I Example: “on off on off on off” is a word in Σ^∗.

Set of words over Σ

I Σ^∗ =∪_n≥0Σⁿ , i.e., all finite words over alphabet Σ.

I What is Σ⁰?

I What is the difference between Σ⁺ and Σ^∗?

Inputs

I Domain of inputs/actions: Σ ={on,off} I This is called theAlphabet.

I Elements areLetters.

I Inputs or behaviors are strings or sequences of letters, calledwords.

I Example: “on off on off on off” is a word in Σ^∗.

Set of words over Σ

I Σ^∗ =∪_n≥0Σⁿ , i.e., all finite words over alphabet Σ.

I What is Σ⁰?

I What is the difference between Σ⁺ and Σ^∗?

Processing

Processing

I States: current information which allows to process the next letter/input.

start dark light

Processing

Processing

I States: current information which allows to process the next letter/input.

I Transitions: read an input and movefrom a state to another

start dark light

on

off

Where is the automaton?

start dark light

on

off

Whichstate is reachedafter reading the following words?

1. “on off on”

Where is the automaton?

start dark light

on

off

Whichstate is reachedafter reading the following words?

1. “on off on”

2. “off off”

Where is the automaton?

start dark light

off

on

off

on

Whichstate is reachedafter reading the following words?

1. “on off on”

2. “off off”

Where is the automaton?

start dark light

off

on

off

on

Whichstate is reachedafter reading the following words?

1. “on off on”

2. “off off”

3. “on (off on)^∗”

Outputs: accepting states

start dark light

off

on

off

on

1. Some states are designated “accept” or “final”

2. If an input word moves to accept state, then its accepted, else rejected.

3. What are the words accepted by above automaton?

Language of an automaton

I All words accepted by an automaton form itslanguage.

start dark light

off

on

off

on

Languages

Let Σ be a finite alphabet.

A language over Σ is a subset of Σ^∗. Examples:

1. L₁: words that end with 1

2. L2: words that haven 0s followed byn 1s, for each non-negative integer n.

3. L₃: words of length a prime number.

I Give an example of a finite and infinite language.

I Give an example of a language that contains any language over Σ.

Languages

Let Σ be a finite alphabet.

A language over Σ is a subset of Σ^∗. Examples:

1. L₁: words that end with 1

2. L₂: words that haven 0s followed byn 1s, for each non-negative integer n.

3. L₃: words of length a prime number.

I Give an example of a finite and infinite language.

I Give an example of a language that contains any language over Σ.

Languages

Let Σ be a finite alphabet.

A language over Σ is a subset of Σ^∗. Examples:

1. L₁: words that end with 1

2. L₂: words that haven 0s followed byn 1s, for each non-negative integer n.

3. L₃: words of length a prime number.

I Give an example of a finite and infinite language.

I Give an example of a language that contains any language over Σ.

Languages

Let Σ be a finite alphabet.

A language over Σ is a subset of Σ^∗. Examples:

1. L₁: words that end with 1

2. L₂: words that haven 0s followed byn 1s, for each non-negative integer n.

3. L₃: words of length a prime number.

I Give an example of a finite and infinite language.

I Give an example of a language that contains any language over Σ.

Languages

Let Σ be a finite alphabet.

A language over Σ is a subset of Σ^∗. Examples:

1. L₁: words that end with 1

2. L₂: words that haven 0s followed byn 1s, for each non-negative integer n.

3. L₃: words of length a prime number.

I Give an example of a finite and infinite language.

I Give an example of a language that contains any language over Σ.

Languages as problems

Computing problems can be seen as languages!

Consider

I is n∈Na prime?

I with Σ ={a}, ask ifaⁿ∈L₃.

I That is, all theyesinstances of the problem are in the language and only these are!

I Can there be an automaton for this?

We will go back-and-forth between languages and problems!

Languages as problems

Computing problems can be seen as languages!

Consider

I is n∈Na prime?

I with Σ ={a}, ask ifaⁿ∈L3.

I That is, all theyesinstances of the problem are in the language and only these are!

I Can there be an automaton for this?

We will go back-and-forth between languages and problems!

Languages as problems

Computing problems can be seen as languages!

Consider

I is n∈Na prime?

I with Σ ={a}, ask ifaⁿ∈L3.

I That is, all theyesinstances of the problem are in the language and only these are!

I Can there be an automaton for this?

We will go back-and-forth between languages and problems!

Languages as problems

Computing problems can be seen as languages!

Consider

I is n∈Na prime?

I with Σ ={a}, ask ifaⁿ∈L3.

I That is, all theyesinstances of the problem are in the language and only these are!

I Can there be an automaton for this?

We will go back-and-forth between languages and problems!

Languages as problems

Computing problems can be seen as languages!

Consider

I is n∈Na prime?

I with Σ ={a}, ask ifaⁿ∈L3.

I That is, all theyesinstances of the problem are in the language and only these are!

I Can there be an automaton for this?

We will go back-and-forth between languages and problems!

Languages and regular languages

I So, given a language, the question is:

I Can we define an automaton that accepts exactly that language!

Example

I Fix Σ ={a,b}

I Let Lbe all words over Σ that have odd number ofa’s.

I What automaton would acceptL?

start

b

a

a

b

Languages and regular languages

I So, given a language, the question is:

I Can we define an automaton that accepts exactly that language!

Example

I Fix Σ ={a,b}

I Let Lbe all words over Σ that have odd number ofa’s.

I What automaton would acceptL?

start

b

a

a

b

Languages and regular languages

I So, given a language, the question is:

I Can we define an automaton that accepts exactly that language!

Example

I Fix Σ ={a,b}

I Let Lbe all words over Σ that have odd number ofa’s.

I What automaton would acceptL?

start

b

a

a

b

Some more examples

Let Lbe set of all words over Σ ={a,b} which end withbb.

1. WriteL in set notation.

2. Give an automaton that accepts L.

LetL⁰ be set of all words over Σ ={0,1}which are binary representations of multiple of 3.

1. WriteL⁰ in set notation.

2. Give an automaton that accepts L⁰.

Some more examples

Let Lbe set of all words over Σ ={a,b} which end withbb.

1. WriteL in set notation.

2. Give an automaton that accepts L.

Let L⁰ be set of all words over Σ ={0,1}which are binary representations of multiple of 3.

1. WriteL⁰ in set notation.

2. Give an automaton that accepts L⁰.