# Course Introduction

## Why Study Theory?

• Finite Automata and Regular Expressions are helpful in searching, replacing and matching tasks.
• Grammars are useful in describing, understanding and implementing programming languages.
• Computability theory will prevent you from working on impossible problems.
• Complexity theory will teach you which problems are computationally intractable.
• Complexity theory is also fundamental to security.
• It never becomes out-dated.
• It's fun.

## Regular Expressions

Regular expressions are a computational language for matching text. They are extremely useful as computer scientists, giving rise to scanning and matching algorithms, as well as forming the basis for powerful search and replace features in many programming tools.

## Grammars

Context-Free Grammars are a language for describing other languages. They are used to define programming languages - you can read the grammars for popular languages online.

They are also used to build programming languages including compilers, and interpreters. This also includes tools that parse code such as documentation generators, IDEs etc.

This is also useful if you need to parse complex data formats such as XML or JSON.

## Computability

Computability theory has to deal with what problems can and cannot be solved by computer systems.

Some problems are simply not solvable no matter how powerful a computer we have.

## Complexity

Complexity theory is the study of the efficiency of algorithms as the size of the input grows. We will look at different complexity classes of problems, those that can be solved in linear time, polynomial time, exponential time etc.

You will learn which problems have fast, practical solutions and which do not.

Complexity theory is also important for computer security where we don't want solutions that are easily computable.

## Mathematical Background

This class builds on discrete math, and we will use all of the following concepts heavily:

• Sets (subsets, intersection, complement, union)
• Functions (domain, range, relations)
• Graphs, trees
• Boolean logic
• Proofs (by construction, contradiction, induction).

You can refer to Stephen's Discrete Math course if you need a refresher on these topics!