Intro

First of all, we need to know the points of TC:

Understanding
- limits of computers
- how machine solve problems
Practical — Conceptual frameworks that can be put into practice
- grammars of programming language
- regular expressions in pattern matching
- NP-Completeness tells which problems aren’t tractable
Timeless
- Frameworks are resilient to changes in technology
Simple – Theory strips away complicated aspects of computing!
Foundational – Theory is interesting on its own! Tons of open
questions, lots of work to be done

What is machine ?

Everyday, we work with machine in a wide range from the vending machines to Game AIs…
It processes input and deliver some output
Machines greatly differ in their capabilities

Finite Automata

It refers to the simplest computational models, also called Finite State Machine.

Example 1 - Automatic doors

States:

Open
Closed

Inputs:

Person
No Person

Inputs
States		Person	Not Person
Open	Open	Closed
Not Open	Open	Closed

The memory only needs to store current state

Finite Automata Definition: 5-tuple(Q, Σ, δ, q0, F)

Q - finite, set of states
Σ - alphabet, finite; set of valid inputs
δ - transition function that maps (Q × Σ) -> Q, state-input pair -> state
q0 - start state (element of Q)
F - set of accept states(a subset of Q)

Input: finite string of chars from Σ

Output: accept or reject

Process begin at start state, read input 1 char at one time, follow transitions, accept or reject bases on final state

Review topics

• Sets, set operations, power set
• Sequences, tuples
• Functions, equivalence relations
• Graphs
• Boolean logic
• Proofs (direct, contradiction, induction)