Automata Theory �and�Compiler Design�(17CI15)

B.Tech. CSE – V Sem, A.Y:2020-21

Why Theory of Computation?

• The Theory of Computation is the branch that deals with how efficiently problems can be solved on a model of computation using an algorithm.
• It divides into three major areas Automata theory and formal languages, computability theory, and computational complexity theory.

• Automata theory deals with

computational models

• Formal languages are used to represent computational

problems

• Computability theory deals about the what problems can be solvable using computer?

• It deals with how efficiently

the problems can be solved

based on the resources time

and space complexity?

• Classifies problems into P and NP classes

Automata Theory and Compiler Design

Unit-1

• Finite Automata
• Regular Languages

Unit-2

• Context-free languages
• Pushdown Automata

Unit-3

• Design of Lexical analyzer
• Design of Parser (Top down

and Bottom up parsing)

Unit-4

• Syntax-directed Translation
• Run-time Environment

​

Unit-5

• Basics of Code optimization
• Code generation

Text books:

1. John E. Hopcraft and J.D.Ullman – Introduction to Automata Theory and Formal Languages and Computation, Narosa publications , 1999 ( unit-1 and 2)
2. Alfred V. Aho ,Jeffrey Ullman , Ravi sethi – Compilers Prinicples, Techniques and Tools , Pearson Education 2^nd edition ,2008( for 3,4,5 units)

​

Pre-requisite: Set theory and Graph theory, programming language and data structures

Course Outcomes

At the end of the course, the student shall be able to

CO 1: Design Finite Automata and Regular expressions for regular languages

​

CO 2: Design Context-free grammar and push-down automata for CFL

​

CO 3: Design and Implement Lexical and Syntax Analyzer

​

CO 4: Create framework for syntax directed translation schemes and

understand the run-time organization of the program.

​

CO 5: Analyze various code optimization techniques and understand the

design issues of code generation

Introduction to Automata Theory

• The study of computational models (known as Abstract machines) and its characteristics is known as Automata theory
• Automata (Known as Abstract machines) is used to model the problems.

( or)

A Mathematical model to provide a proof for the computational problems that are solvable by the computer

• Automata is a self-acting machines i.e., consumes input and provide transition from one state to another state
• Based on the computational capability and complexity the Automata are classified as
• Finite Automata
• Pushdown Automata
• Linear Bounded Automata
• Turing Machines

Components of Automata

The components of Automata are

• Input tape
• Read/write head
• Finite Control( set of states)

Q₁, Q₂,…..Q_n

Input tape

Read/Write Head

Finite Control

Introduction to Finite Automata

• It is used to model the problems .
• Model the switch(on/off)
• A switch can be one of the two possible states (ON/OFF). If the switch is in ‘ON’ state on input ‘off(0)’ it goes to OFF state. Similarly, if the switch is in ‘OFF’ state on input ‘on(1)’it goes to ON state.

OFF

ON

on(1)

off(0)

Example 2 – Modelling the Binary Adder

Without carry

With carry

00 | 0

10 | 0

11 | 0

00 | 1

01 | 1

10 | 1

11 | 1

01 | 0

Note : So, problem will be represented as a language and problem-solving means constructing an equivalent automaton.

Mathematical Notations

• Alphabet
• An alphabet is an finite non-empty set of symbols.
• It is represented by ∑.

Example s

∑ = {0,1} or {a,b} or { a-zA-Z0-9,+,-,*…}

​

• String
• A string is a finite sequence of one or more symbols of an alphabet.
• Examples

“ababb” is a string over the alphabet {a,b}

“a+b*c” is a string over the alphabet {a-zA-Z0-9,+,*}

​

• Language
• A language is a set of strings.

Example

L1 = {0,1,00,11,01,10,….} over the alphabet ∑ ={ 0,1 }

L2= {ab, aab,aaab,aaaab,…..} over the alphabet ∑ ={ a,b }

​

​

Finite Automaton (FA)

• Informally, a state diagram that comprehensively captures all possible states and transitions that a machine can take while responding to a stream or sequence of input symbols

​

• Recognizer for “Regular Languages”.

​

• Deterministic Finite Automata (DFA)
• The machine can exist in only one state at any given time

​

• Non-deterministic Finite Automata (NFA)
• The machine can exist in multiple states at the same time

Deterministic Finite Automata

Formally ,a DFA is defined by the 5-tuple M= {Q, ∑ , δ ,q₀, F}

• Q - a finite set of states
• ∑ - a finite set of input symbols (alphabet)
• δ - a transition function, which is a mapping between

Q x ∑ --> Q

• q₀ - a start state/ initial state
• F - set of accepting states/ final states

​

​

Example

What is the language accepted by the following Finite Automaton?

M1 :

M2 :

L(M1) or L1= {ϵ, 0, 1, 00, 01,…}

L2 = {, 0, 1, 000,001,010…}

M3 :

L3 = {ϵ, aa, ba,ab,bb,…}

M4 :

L5 = Φ ( empty set)

M5:

L5 = {0, 00,10,000,010,100…..}

Strings ending with zero

M6:

L6 = {ba,bab,babb,abab,aaaba,…….}

Strings ending with either one a (or) zero or more b

What is the language accepted by the following Finite Automaton?

States required to construct FA

“a” (or) “0”

1

2

“01”

2

3

where w = a or b or 0 or 1

“abba”

4

5

“01001…..”

n

n+1

Example 1:

Step 1 : The minimum possible string having “ba” as a substring is “ba”. so, minimum number of states to represent “ba” is 3

Step 2: Place the missing transitions of each state with out changing the original property of the language(i.e., having “ba” as a substring).

q₀

q₁

q₂

b

a

For q₀ transition a is missing, the possibilities are (q₀ , a)= q₀ , (q₀ , a)= q₁, (q₀ , a)= q₂

a

a

a

x

x

q₀

q₁

b

a

Problem: Construct a Deterministic Finite Automata for the Language L over the alphabet {a,b} and whose strings have “ba” as a substring

Among the possibilities (q₀ , a)= q₀ is valid and (q₀ , a)= q₁, (q₀ , a)= q₂ are invalid

q₀

q₁

b

a

a

For q₁ transition b is missing, the possibilities are (q₁ , b)= q₀ , (q₁ , b)= q₁, (q₁ , b)= q₂

q₀

q₁

b

a

a

Among the possibilities (q₁ , b)= q₁ is valid and (q₁, b)= q₀, (q₁, b)= q₂ are invalid

b

b

b

x

x

For q₂ transitions a, and b are missing, the possibilities are

(q₂ , a)= q₀ , (q₂ , a)= q₁, (q₂ , a)= q₂ and (q₂ , b)= q₀ , (q₂ , b)= q₁, (q₂ , b)= q₂

q₀

q₁

b

a

a

b

q₀

q₁

b

a

a

b

Among the possibilities (q₂ , a)= q₂ and (q₂ , b)= q₂ are valid and remaining are invalid

a,b

Equivalent representation of FA

δ (q₀ , a ) = q₀

δ (q₀ , b ) = q₁

δ (q₁ , a ) = q₂

δ (q₁ , b ) = q₁

δ (q₂ , a ) = q₂

δ (q₂ , b ) = q₂

Transition diagram

Transition table

Transitions

A finite Automata M= {Q, ∑ , δ ,q₀, F} where

Q= { q0,q1,q2} , ∑ = {a,b} , initial state= q0 , F={ q2}

where transition function δ is represented as

Language accepted by DFA(M)

= δ( δ(q₀, abb), a)

​

= δ(δ(δ(q₀, ab), b)a)

​

= δ(δ(δ(δ(q₀, a),b), b)a)

​

= δ(δ(δ(δ(δ(q₀, ϵ),a),b), b)a)

​

= δ(δ(δ(δ(q₀,a),b), b)a)

​

= δ(δ(δ(q₀,b), b)a)

​

= δ(δ(q₁,b)a)

​

= δ(q₁,a) =q₂ ( Accept state)

^

^

^

^

q₂

Informally, transition path is represented as

Language accepted by FA

The language of a DFA M = (Q, Σ, δ, q₀ , F), denoted L(M) is defined by

​

​

The language of M is the set of strings w that take the start state q₀ to one of the accepting states.

If L is a L(M) from some DFA, then L is a regular language

Deterministic Finite Automata

Construct DFA for the Language L over the alphabet {0,1} and whose strings

contains 01 as a substring

Example

Construct DFA for the language over the alphabet {0,1} and whose string have

• Even length
• Odd length
• Even number of ones
• Odd number of ones
• Even number of zeros
• Odd number of zeros
• Even number of zeros and ones - EE
• Even number of zeros and odd number of ones - EO
• Odd number of zeros and even number of ones - OE
• Odd number of zeros and odd number of ones - OO
• Even number of zeros or ones - { EE,EO,OE } - OO
• Even number of zeros or odd number of ones -except OE
• Odd number of zeros or even number of ones -Except EO
• Odd number of zeros or odd number of ones -except EE

Example

Construct DFA for the language L over the alphabet {a,b} and

whose string length is divisible by 3 (or) multiple of 3

Construct DFA for the following language L

L ={ w ϵ { a,b}* | |w| mod 3 = 0 }

(or)

Construct DFA for the following language L

• L ={ w ϵ { a,b}* | |w| mod 3 = 1 }
• L ={ w ϵ { a,b}* | |w| mod 3 = 2 }
• L ={ w ϵ { a,b}* | |n_a (w)| mod 3 = 0 }
• L ={ w ϵ { a,b}* | |n_b (w)| mod 3 = 0 }
• L ={ w ϵ { a,b}* | |n_a (w)| mod 3 = 1 }
• L ={ w ϵ { a,b}* | |n_b (w)| mod 3 = 1}
• L ={ w ϵ { a,b}* | |n_a (w)| mod 3 = 2}
• L ={ w ϵ { a,b}* | |n_b (w)| mod 3 = 2}

Example

Construct DFA for the language L over the alphabet {a,b} and whose strings having

• Substring abba
• No substring abba

Construct DFA for the language L over the alphabet {a,b} and whose strings having

• Substring abba
• No substring abba

Non-deterministic Finite Automata(NFA)

Mathematically a NFA is defined by the 5-tuple M= {Q, ∑ , δ ,q₀, F}

• Q - a finite set of states
• ∑ - a finite set of input symbols (alphabet)
• δ - a transition function, which is a mapping between

Q x ∑ --> 2^Q

• q₀ - a start state/ initial state
• F - set of accepting states/ final states

​

​

Non-deterministic Finite Automata (NFA)

• A Non-deterministic Finite Automaton (NFA)
• “non-deterministic”
• Implying that the machine can exist in more than one state at the same time
• Transitions could be non-deterministic

​

q_i

1

1

q_j

q_k

…

• Each transition function therefore �maps to a set of states

How to use an NFA?

• Input: a string w in ∑*
• Question: Is w acceptable by the NFA?
• Steps:
• Start at the “start state” q₀
• For every input symbol in the sequence w do
• Determine all possible next states from all current states for the given the current input symbol in w and the transition function
• If after all symbols in w are consumed and if at least one of the current states is a final state then accept w;
• Otherwise, reject w.

NFA for strings containing substring 01

What will happen if at state q₁ �an input of 0 is received?

NFA will halt and says, w is not accepted

More Natural way of constructing the automata.

3 possible cases strings may contain 01

1. At the Begin i.e., 01 followed by any no. of 0’s and 1’s
2. At the End i.e., any no of 0’s and 1’s followed by 01.
3. At some position . any no of 0’s and 1’s (01) any no. of 0’s and 1’s

δ ( q₀, 000)

δ ( q₀, 00)

δ ( q₁, 00)

δ ( q₀, 0)

δ ( q₁, 0)

q₀

0

0

0

0

0

Among the leaves { q₀ } , there is no

final state . So, the string 1000 is

not accepted

δ ( q₀, 010)

δ ( q₀, 10)

δ ( q₁, 10)

δ ( q₀, 0)

δ ( q₂, 0)

q₀

q₂

0

0

1

1

0

0

δ ( q₀, 1000)

1

Halt, No

transition

for q1 on 0

X

X

0

Among the leaves { q_{0 ,} q_1,q₂ } , there is a

final state . So, the string 010 is accepted

0

Halt, No transition for q1 on 0

Acceptance of strings by NFA

q₁

0

NFA to DFA construction: Example

• L = {w | w ends in 01}

q₀

q₁

0

0,1

q₂

1

NFA:

DFA:

2. Determine transitions

To avoid enumerating all of power set, do �“lazy creation of states”

3. Retain only those states � reachable from {q₀}

1. Enumerate all possible subsets

NFA to DFA: Repeating the example using �LAZY CREATION

• L = {w | w ends in 01}

q₀

q₁

0

0,1

q₂

1

NFA:

DFA:

Idea: Introduce states as you go

(on a need basis)

Summary

• Construction of DFA/NFA is equivalent to writing the program for the given problem.

​

• Depending up on the given problem( i.e., language) , we decide the number of states Q

,initial state and set of final states.

​

• There can be infinitely many DFAs exists for the given problem, but the minimal DFA is

unique.

​

​

​

Properties of DFAs and NFAs

• The machine never really terminates.
• It is always waiting for the next input symbol or making transitions.

​

• The machine decides when to consume the next symbol from the input and when to ignore it.
• (but the machine can never skip a symbol)

​

• A transition can happen even without really consuming an input symbol (think of consuming ε as a free token) – if this happens, then it becomes an ε-NFA .

​

• A single transition cannot consume more than one (non-ε) symbol.

Finite Automata(NFA) with ε-Transitions

• We can allow explicit ε-transitions in finite automata
• i.e., a transition from one state to another state without consuming any additional input symbol
• Explicit ε-transitions between different states introduce non-determinism.
• Makes it easier sometimes to construct NFAs

​

Definition: ε -NFAs are those NFAs with at least one explicit ε-transition defined.

• ε -NFAs have one more column in their transition table

^

Example of an ε-NFA

• ε-closure of a state q, is the set of all states (including itself) that can be reached from q by repeatedly making an arbitrary number of ε-transitions.

L = {w | w is empty, or if non-empty will end in 01}

Example of an ε-NFA

For the string aac, we can view as a, a ,ϵ, ϵ, c

Identity

a. ϵ = ϵ . a = a

a. Φ = a. Φ = Φ

q₀

a

Example of an ε-NFA

• ε-closure of a state q, is the set of all states (including itself) that can be reached from q by repeatedly making an arbitrary number of ε-transitions.

L = {w | w is empty, or if non-empty will end in 01}

Simulation of ε-NFA

Simulate for w=101

L = {w | w is empty, or if non-empty will end in 01}

q₀

q₁

1

Ø

1

x

To simulate any transition:� Step 1) Go to all immediate destination states.

Step 2) From there go to all their ε-closure states as well.

Example of another ε-NFA

Simulate for w=101:

?

​

q₀

q₁

0

0,1

1

q₂

q’₀

ε

ε

q₃

1

To simulate any transition:� Step 1) Go to all immediate destination states.

Step 2) From there go to all their ε-closure states as well.

Conversion of ε-NFA to DFA

40

L = {w | w is empty, or if non-empty will end in 01}

q₀

q₁

0

0,1

1

q₂

Conversion of ε-NFA to DFA

41

L = {w | w is empty, or if non-empty will end in 01}

q₁

q₂

0

0,1

1

q₃

Equivalency of DFA, NFA, ε-NFA

• Theorem: A language L is accepted by some ε-NFA if and only if L is accepted by some DFA

​

​

• Implication:
• DFA ≡ NFA ≡ ε-NFA
• (all accept Regular Languages)

Applications of Interest

• Comparing two DFAs:
• L(DFA₁) == L(DFA₂)?

​

​

• How to minimize a DFA?
1. Remove unreachable states
2. Identify & condense equivalent states into one

​

43

When to call two states in a DFA “equivalent”?

Two states p and q are said to be equivalent iff:

• Any string w accepted by starting at p is also accepted by starting at q;

​

​

​

• Any string w rejected by starting at p is also rejected by starting at q.

p

q

AND

w

p

q

w

🡺 p≡ q

Computing equivalent states in a DFA

45

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

Table Filling Algorithm

Pass #0

• Mark accepting states ≠ non-accepting states

Pass #1

• Compare every pair of states
• Distinguish by one symbol transition
• Mark = or ≠ or blank(tbd)

Pass #2

• Compare every pair of states
• Distinguish by up to two symbol transitions (until different or same or tbd)

….

(keep repeating until table complete)

Table Filling Algorithm - step by step

46

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

Table Filling Algorithm - step by step

47

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1. Mark X between accepting vs. non-accepting state

​

​

Table Filling Algorithm - step by step

48

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1. Mark X between accepting vs. non-accepting state
2. Look 1- hop away for distinguishing states or strings

Table Filling Algorithm - step by step

49

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1. Mark X between accepting vs. non-accepting state
2. Look 1- hop away for distinguishing states or strings

Table Filling Algorithm - step by step

50

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1. Mark X between accepting vs. non-accepting state
2. Look 1- hop away for distinguishing states or strings

Table Filling Algorithm - step by step

51

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1. Mark X between accepting vs. non-accepting state
2. Look 1- hop away for distinguishing states or strings

Table Filling Algorithm - step by step

52

A

C

E

G

B

D

F

H

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1