1 of 27

1

9/9/2024

Sri Raghavendra Educational Institutions Society (R)

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

www.skit.org.in

Department of Computer Science & Engineering

SUBJECT CODE:BCS503

SUBJECT NAME:THEORY OF COMPUTATION

2 of 27

MODULE-1

2

9/9/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

3 of 27

INTRODUCTION TO AUTOMATA THEORY

3

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

4 of 27

What is Automata Theory?

  • Study of abstract computing devices, or “machines”
  • Automaton = an abstract computing device
    • Note: A “device” need not even be a physical hardware!
  • A fundamental question in computer science:
    • Find out what different models of machines can do and cannot do
    • The theory of computation
  • Computability vs. Complexity

4

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

5 of 27

Alan Turing (1912-1954)

  • Father of Modern Computer Science
  • English mathematician
  • Studied abstract machines called Turing machines even before computers existed
  • Heard of the Turing test?

5

(A pioneer of automata theory)

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

6 of 27

Theory of Computation: A Historical Perspective

6

1930s

  • Alan Turing studies Turing machines
  • Decidability
  • Halting problem

1940-1950s

  • “Finite automata” machines studied
  • Noam Chomsky proposes the � “Chomsky Hierarchy” for formal � languages

1969

Cook introduces “intractable” problems� or “NP-Hard” problems

1970-

Modern computer science: compilers, �computational & complexity theory evolve

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

7 of 27

Languages & Grammars

  • Languages: “A language is a collection of sentences of finite length all constructed from a finite alphabet of symbols”
  • Grammars: “A grammar can be regarded as a device that enumerates the sentences of a language” - nothing more, nothing less

​

  • N. Chomsky, Information and Control, Vol 2, 1959

7

Or “words”

Image source: Nowak et al. Nature, vol 417, 2002

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

8 of 27

The Chomsky Hierarchy

8

Regular

(DFA)

Context-�free

(PDA)

Context-�sensitive �(LBA)

Recursively-�enumerable �(TM)

  • A containment hierarchy of classes of formal languages

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

9 of 27

The Central Concepts of Automata Theory

9

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

10 of 27

Alphabet

An alphabet is a finite, non-empty set of symbols

  • We use the symbol ∑ (sigma) to denote an alphabet
  • Examples:
    • Binary: ∑ = {0,1}
    • All lower case letters: ∑ = {a,b,c,..z}
    • Alphanumeric: ∑ = {a-z, A-Z, 0-9}
    • DNA molecule letters: ∑ = {a,c,g,t}
    • …

10

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

11 of 27

Strings

A string or word is a finite sequence of symbols chosen from ∑

  • Empty string is ε (or “epsilon”)

​

  • Length of a string w, denoted by “|w|”, is equal to the number of (non- ε) characters in the string
    • E.g., x = 010100 |x| = 6
    • x = 01 ε 0 ε 1 ε 00 ε |x| = ?

​

    • xy = concatentation of two strings x and y

​

11

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

12 of 27

Powers of an alphabet

Let ∑ be an alphabet.

​

    • ∑k = the set of all strings of length k

​

    • ∑* = ∑0 U ∑1 U ∑2 U …

​

    • ∑+ = ∑1 U ∑2 U ∑3 U …

​

12

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

13 of 27

Languages

L is a said to be a language over alphabet ∑, only if L ⊆ ∑*

🡺 this is because ∑* is the set of all strings (of all possible length including 0) over the given alphabet ∑

Examples:

    • Let L be the language of all strings consisting of n 0’s followed by n 1’s: � L = {ε, 01, 0011, 000111,…}
    • Let L be the language of all strings of with equal number of 0’s and 1’s:

L = {ε, 01, 10, 0011, 1100, 0101, 1010, 1001,…}

​

​

Definition: Ø denotes the Empty language

  • Let L = {ε}; Is L=Ø?

​

13

NO

Canonical ordering of strings in the language

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

14 of 27

The Membership Problem

Given a string w ∈∑*and a language L over ∑, decide whether or not w ∈L.

​

Example:

Let w = 100011

Q) Is w ∈ the language of strings with equal number of 0s and 1s?

​

14

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

15 of 27

Finite Automata

  • Some Applications
    • Software for designing and checking the behavior of digital circuits
    • Lexical analyzer of a typical compiler
    • Software for scanning large bodies of text (e.g., web pages) for pattern finding
    • Software for verifying systems of all types that have a finite number of states (e.g., stock market transaction, communication/network protocol)

​

15

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

16 of 27

Finite Automata : Examples

  • On/Off switch

​

​

  • Modeling recognition of the word “then”

​

16

Start state

Final state

Transition

Intermediate �state

action

state

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

17 of 27

Structural expressions

  • Grammars
  • Regular expressions
    • E.g., unix style to capture city names such as “Palo Alto CA”:
      • [A-Z][a-z]*([ ][A-Z][a-z]*)*[ ][A-Z][A-Z]

​

17

Start with a letter

A string of other �letters (possibly�empty)

Other space delimited words�(part of city name)

Should end w/ 2-letter state code

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

18 of 27

Formal Proofs

18

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

19 of 27

Deductive Proofs

From the given statement(s) to a conclusion statement (what we want to prove)

  • Logical progression by direct implications

​

Example for parsing a statement:

  • “If y≥4, then 2y≥y2.”

​

​

(there are other ways of writing this).

19

given

conclusion

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

20 of 27

Example: Deductive proof

Let Claim 1: If y≥4, then 2y≥y2.

​

Let x be any number which is obtained by adding the squares of 4 positive integers.

Claim 2:

Given x and assuming that Claim 1 is true, prove that 2x≥x2

  • Proof:
    1. Given: x = a2 + b2 + c2 + d2
    2. Given: a≥1, b≥1, c≥1, d≥1
    3. 🡺 a2≥1, b2≥1, c2≥1, d2≥1 (by 2)
    4. 🡺 x ≥ 4 (by 1 & 3)
    5. 🡺 2x ≥ x2 (by 4 and Claim 1)

20

“implies” or “follows”

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

21 of 27

On Theorems, Lemmas and Corollaries

We typically refer to:

  • A major result as a “theorem”
  • An intermediate result that we show to prove a larger result as a “lemma”
  • A result that follows from an already proven result as a “corollary”

21

An example:

Theorem: The height of an n-node binary tree is at least floor(lg n)

Lemma: Level i of a perfect binary tree has 2i nodes.

Corollary: A perfect binary tree of height h has 2h+1-1 nodes.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

22 of 27

Quantifiers

“For all” or “For every”

    • Universal proofs
    • Notation=

“There exists”

    • Used in existential proofs
    • Notation=

Implication is denoted by =>

      • E.g., “IF A THEN B” can also be written as “A=>B”

22

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

23 of 27

Proving techniques

  • By contradiction
    • Start with the statement contradictory to the given statement
    • E.g., To prove (A => B), we start with:
      • (A and ~B)
      • … and then show that could never happen��What if you want to prove that “(A and B => C or D)”?

​

  • By induction
    • (3 steps) Basis, inductive hypothesis, inductive step
  • By contrapositive statement
    • If A then B ≡ If ~B then ~A

23

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

24 of 27

Proving techniques…

  • By counter-example
    • Show an example that disproves the claim

​

  • Note: There is no such thing called a �“proof by example”!
    • So when asked to prove a claim, an example that satisfied that claim is not a proof

24

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

25 of 27

Different ways of saying the same thing

  • “If H then C”:
    1. H implies C
    2. H => C
    3. C if H
    4. H only if C
    5. Whenever H holds, C follows

​

​

25

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

26 of 27

“If-and-Only-If” statements

  • “A if and only if B” (A <==> B)
    • (if part) if B then A ( <= )
    • (only if part) A only if B ( => )� (same as “if A then B”)
  • “If and only if” is abbreviated as “iff”
    • i.e., “A iff B”
  • Example:
    • Theorem: Let x be a real number. Then floor of x = ceiling of x if and only if x is an integer.
  • Proofs for iff have two parts
    • One for the “if part” & another for the “only if part”

26

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

27 of 27

Summary

  • Automata theory & a historical perspective
  • Chomsky hierarchy
  • Finite automata
  • Alphabets, strings/words/sentences, languages
  • Membership problem
  • Proofs:
    • Deductive, induction, contrapositive, contradiction, counterexample
    • If and only if

​

  • Read chapter 1 for more examples and exercises

​

27

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in