Skip to content

1. Languages

Jan 11/13, 2022

Automata

  • distinguished by temporal memory
    • finite automata: no temporary memory
    • pushdown automata: stack
    • Turing machines: random access
  • more flexible memory → able to solve more computational problems:
1
2
Finite automata  <     Pushdown automata    <    Turing machine
simple problems  <   more complex problems  <   hardest problems
  • Turing machine is the most powerful known computational model, though cannot solve all computational problems

Languages

  • language is a set of strings
    • string is a sequence of symbols from the alphabet
    • alphabet \(\Sigma\) is a set of symbols e.g. \(\Sigma = \{a,b\}\) (non-empty)
  • operations: concatenation (\(wv\)), reverse (\(w^R\)), exponent (\(w^n\))
  • length: \(|w|\) → length of concat: \(|uv| = |u| + |v|\)
  • empty string: \(\epsilon\) or \(\lambda\)
    • note: \(|\epsilon| = 0\),   \(\epsilon w = w \epsilon = w\),   \(w^0 = \epsilon\)
  • star \(\Sigma^*\) operation: all possible strings from the alphabet (including \(\epsilon\))
    • e.g. \(\Sigma = \{a,b\}\) => \(\Sigma^* = \{\epsilon, a,b,aa,ab,ba,bb,aaa,aab,...\}\)
    • language over alphabet \(\Sigma\) is any subset of \(\Sigma^*\)
    • \(\Sigma^+ = \Sigma^* - \{\epsilon\}\)

  • language problems are membership problems => does string belong to language

  • Two special languages:

    • empty language {} or Ø   => size \(|\{\}| = 0\)
    • empty string language \(\{\epsilon \}\)   => size \(|\{\epsilon \}| = 1\), string length \(|\epsilon| = 0\)

Operations

  • union: \(L_1 \cup L_2\), intersection: \(L_1 \cap L_2\), difference \(L_1 - L_2\)
  • complement: \(\bar{L} = \Sigma^* - L\)
  • reverse: \(L^R = \{ w^R : w \in L \}\)
  • concatenation: \(L_1 L_2 = \{xy: x \in L_1, y \in L_2\}\)
  • \(L^n\) (or "L n times")
    • e.g. \(\{a,b\}^3 = \{a,b\}\{a,b\}\{a,b\} = \{aaa, aab, aba, abb, baa, bab, bba...\}\)
    • e.g. \(L = \{a^nb^n: n \geq 0\}\) then \(L^2 = \{a^nb^na^mb^m: n,m \geq 0\}\)
    • special case: \(L^0 = \{ \epsilon \}\)
  • Star closure / Kleene *: \(L^* = L^0 \cup L^1 \cup L^2 \cup ...\)
\[\begin{equation} \{a, bb\}^* = \begin{cases} \epsilon, & (L_0)\\ a, bb, & (L_1)\\ aa, abb, bba, bbbb, & (L_2) \\ aaa, aabb, abba, abbbb, ... & (L_3) \end{cases} \end{equation}\]
  • Positive closure: \(L^+ = L^1 \cup L^2 \cup ...\)
    • note: \(L^* = L^0 \cup L^+\)
\[\begin{equation} \{a, bb\}^+ = \begin{cases} a, bb, & (L_1)\\ aa, abb, bba, bbbb, & (L_2) \\ aaa, aabb, abba, abbbb, ... & (L_3) \end{cases} \end{equation}\]