Differences

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

--- theocs:lecture1 [2024/10/03 12:26] – 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 ======
 == 03/10/2024 ==
+{{ :theocs:lecture01_a_slides_1_.pdf | Lecture 1 Slides}}
   * **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.
+  * 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)
@@ Line 17: / Line 19: @@
       * 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$ 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$ 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\} and M = \{ab,aabb\} then$
+  * $L \cdot \{\Lambda\} = \{\Lambda\} \cdot L = L$
+  * $L \cdot \emptyset = \emptyset \cdot L = \emptyset$
+  * $L \cdot M \neq M \cdot L$
+    * **TODO: Insert examples**
+  * $L \cdot (M \cdot N) = (L \cdot M ) \cdot N$
+  * $L^0 = \{\Lambda\},\ L^n = L \cdot L^{n-1},\ if\ n > 0$
+    * **TODO: Insert examples**
+  * 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**
+====== Lecture A/2: Grammars ======
+{{ :theocs:lecture02_a_1_.pdf |Lecture 2 Slides}}