theocs:lecture1

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

03/10/2024

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 the 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 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/lecture1.txt
  • Last modified: 2024/10/07 23:05
  • by tami