theocs:lecture1

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
theocs:lecture1 [2024/10/03 13:17] – tamitheocs: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 ==
 +
 +{{ :theocs:lecture01_a_slides_1_.pdf | Lecture 1 Slides}}
  
   * **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 to study of formal "grammars" - they have a close relationship to abstract automata.+  * In late 1950s. N. Chomsky begain the study of formal "grammars" - they have a close relationship to abstract automata.
   * 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 comre from $\Sigma$.+    * If $\Sigma$ is an alphabet, then a **language over $\Sigma$** is a set of strings (including empty string $\Lambda$) whose symbols come from $\Sigma$.
       * If $\Sigma = \{a,b\}$, then $L = \{ab,aaaab,abbb,a\}$ is an example of a language over $\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$       * 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 38: Line 40:
 ====== Lecture A/2: Grammars ====== ====== Lecture A/2: Grammars ======
  
 +{{ :theocs:lecture02_a_1_.pdf |Lecture 2 Slides}}
  • theocs/lecture1.1727961443.txt.gz
  • Last modified: 2024/10/03 13:17
  • by tami