Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
| theocs:lecture1 [2024/10/03 12:49] – tami | theocs:lecture1 [2024/10/07 23:05] (current) – tami | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== THEOCS Lecture A/1: Introduction to Theoretical Computer Science and Languages ====== | ====== THEOCS Lecture A/1: Introduction to Theoretical Computer Science and Languages ====== | ||
| == 03/10/2024 == | == 03/10/2024 == | ||
| + | |||
| + | {{ : | ||
| * **Alan Turing ❤️ 🏳️🌈** | * **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. | * 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 | + | * In late 1950s. N. Chomsky begain |
| * S. Cook seperated problems that **can be solved efficiently** from (CONT) | * S. Cook seperated problems that **can be solved efficiently** from (CONT) | ||
| Line 17: | Line 19: | ||
| * A string with no symbols is called an **empty string** and is denoted $\Lambda$ | * A string with no symbols is called an **empty string** and is denoted $\Lambda$ | ||
| * Using alphabet, strings, grammar makes a language | * 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 | + | * If $\Sigma$ is an alphabet, then a **language over $\Sigma$** is a set of strings (including empty string $\Lambda$) whose symbols |
| * If $\Sigma = \{a,b\}$, then $L = \{ab, | * If $\Sigma = \{a,b\}$, then $L = \{ab, | ||
| * If $\Sigma$ is an alphabet, then $\Sigma^{\ast}$ denoted the infinite set of all strings made up from $\Sigma$ (including an empty string $\Lambda$ | * If $\Sigma$ is an alphabet, then $\Sigma^{\ast}$ denoted the infinite set of all strings made up from $\Sigma$ (including an empty string $\Lambda$ | ||
| Line 35: | Line 37: | ||
| * If L is a language of $\Sigma$ (i.e. $L \subset \Sigma^\ast$) then the **closure of L** is the language denoted by $L^\ast$ | * If L is a language of $\Sigma$ (i.e. $L \subset \Sigma^\ast$) then the **closure of L** is the language denoted by $L^\ast$ | ||
| * **TODO: Positive closure** | * **TODO: Positive closure** | ||
| - | * | + | |
| + | ====== Lecture A/2: Grammars ====== | ||
| + | |||
| + | {{ : | ||