THEOCS Lecture A/1: Introduction to Theoretical Computer Science and Languages

This is an old revision of the document!

Alan Turing ❤️ 🏳️‍🌈
- Proven that computational power does not determine the problems it can run. All classical computers regardless of powers can compute the same problems.
In late 1950s. N. Chomsky begain to study of formal “grammars” - they have a close relationship to abstract automata.
S. Cook seperated problems that can be solved efficiently from (CONT)

Set of symbols - alphabet - which are combined into acceptable strings
- A finite, nonempty set of symbols is called an alphabet
  - $\Sigma = \{a,b,c\}$ is an example of a alphabet
Rules which tell us how to combine strings in sensible ways are called the grammar
- A sting is a finite sequence of symbols from the alphabet
  - $abc, aaa, bb$ are examples of strings on $\Sigma$
  - A string with no symbols is called an empty string and is denoted $\Lambda$
Using alphabet, strings, grammar makes a language
- If $\Sigma$ is an alphabet, then a language over $\Sigma$ is a set of strings (including empty string $\Lambda$) whose symbols comre from $\Sigma$.
  - If $\Sigma = \{a,b\}$, then $L = \{ab,aaaab,abbb,a\}$ is an example of a language over $\Sigma$
  - If $\Sigma$ is an alphabet, then $\Sigma^{\ast}$ denoted the infinite set of all strings made up from $\Sigma$ (including an empty string $\Lambda$
  - Looking at $\Sigma^{\ast}$, a lanuage over $\Sigma$ is any subset of $\Sigma^{\ast}$

Four simple examples of languages over an alphabet $\Sigma$ are the sets:
- $\emptyset, \{\Lambda\}, \Sigma, \Sigma^{\ast}$
If $L = \{aa,bb,ab\} \text{and} \ M = \{ab,aabb\} \text{then} \$