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:

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

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

• Two special languages:

  • empty language {} or Ø   => size $|\{\}|=0$
  • empty string language $\{ϵ\}$   => size $|\{ϵ\}|=1$, string length $|ϵ|=0$

Operations

• union: $L_1\cup L_2$, intersection: $L_1\cap L_2$, difference $L_1-L_2$
• complement: $\overline{L}={\mathrm{\Sigma }}^{\ast }-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^n{b}^n:n\ge 0\}$ then $L^2=\{a^n{b}^n{a}^m{b}^m:n,m\ge 0\}$
  • special case: $L^0=\{ϵ\}$
• Star closure / Kleene *: $L^{\ast }=L^0\cup L^1\cup L^2\cup ...$

$$\{a,bb{\}}^{\ast }=\{\begin{array}{ll}ϵ,& (L_0)\\ a,bb,& (L_1)\\ aa,abb,bba,bbbb,& (L_2)\\ aaa,aabb,abba,abbbb,...& (L_3)\end{array}$$

• Positive closure: $L^{+}=L^1\cup L^2\cup ...$
  • note: $L^{\ast }=L^0\cup L^{+}$

$$\{a,bb{\}}^{+}=\{\begin{array}{ll}a,bb,& (L_1)\\ aa,abb,bba,bbbb,& (L_2)\\ aaa,aabb,abba,abbbb,...& (L_3)\end{array}$$