Investigates what can be computed with an algorithm in principle.
Mostly resolved by the 1950s.
Second Half: Complexity Theory
Focuses on what is computable in practice, considering time and space constraints.
Will cover topics like the P vs NP problem.
Pre-requisites: Moderate to advanced math experience, familiarity with mathematical theorems and proofs.
Role of Theory in Computer Science
Theoretical computer science helps us understand computation at a fundamental level.
Although some computational problems like the brain's functioning remain unsolved, theory provides elegant frameworks useful in practical applications.
The course will cover theoretical models like finite automata and Turing machines.
Models of Computation
Abstract Models: Simplified representations to study computers mathematically.
Finite Automaton (FA):
Consists of states, transitions, starting state, and accepting states.
Example: A finite automaton can recognize strings containing consecutive '1's.
Language of an automaton: Set of all strings it accepts.
Finite Automaton Details
Formal Definition:
A five-tuple (Q, Σ, δ, q0, F)
Q: Finite set of states
Σ: Input alphabet
δ: Transition function
q0: Starting state
F: Accepting states
Computation:
Process input strings to determine acceptance or rejection.
Languages and Regular Languages
String and Language: A string is a finite sequence of symbols. A language is a set of strings.
Regular Language: Recognizable by some finite automaton.
Operations on Languages:
Union, Concatenation, and Star operations.
Regular expressions use these operations to describe languages.
Closure Properties of Regular Languages
Closed Under Union:
If A1 and A2 are regular, A1 ∪ A2 is also regular.
Proven by constructing a new FA that simulates both automata in parallel.
Closure Under Concatenation (in progress):
Preliminary steps indicate the difficulty in determining where to split strings.
Next Steps
Begin analyzing closure under concatenation and complete proofs for closure properties.
Continue exploring the equivalence of finite automata and regular expressions.
Important Notes
Regular languages are a foundational concept for understanding computational limitations and capabilities.
The course will require a strong understanding of proofs and mathematical reasoning.