Instructor: Shai Ben-David

Time: MW 4:00PM - 5:20PM MC4063

.1A * 4⁺ + .2MT + .4FE

+: best 4 of 5

• Week 1. Jan 6
• Week 2. Jan 10
• Week 3. Jan 17
• Week 4. Jan 24
• Week 5. Jan 31
• Week 6. Feb 7
• Week 7. Feb 14
• Week 9. Feb 28
• Week 10. Mar 7
• Week 11. Mar 14
• Week 12. Mar 21
• Week 13. Mar 28
• Week 14. Apr 4

Week 1. Jan 6

countability of sets

notation. set operations

• symmetric difference $A\triangle B:=(A-B)\cup(B-A)=A\cup B-A\cap B$
• complement $A^C:=X-A$ for $A\subseteq X$ for univseral set $X$
• cartesian product: $A\times B:=\{(a,b):a\in A,b\in B\}$
• power set: $\mathcal{P}(A):=2^A:=\{B:B\subseteq A\}$
• power of set: $A^B:=\{f|f:B\rightarrow A\}$
  • think about how subsets and function that maps element to {0,1} are same

notation. multisets: multiplicity matters.

notation. sequence sets: multiplicity and order matter.

defn. relations are subsets of cartesian products.

eg. in a graph $G=(V,E)$, edges $E\subseteq V^2$ are relation.

defn. an order relation is set of pairs in a relation such that the first element is less than or equal to the second. it has

• transitivity: if $(x,y)\in R,(y,z)\in R$, then $(x,z)\in R$
• reflexivity: $(x,x)\in R$
• linearity: $\forall x\forall y:(x,y)\in R\cup(y,x)\in R$

defn. a function relation of $f:A\rightarrow B$ is $R_f\subseteq A\times B=\{(x,f(x)):x\in A,f(x)\in B\}$.

• requirements of $R$ to be a function relation:
  1. $\forall x\in A\,\exist y\in B:(x,y)\in R$
  2. $\forall x\in A\,\forall y_1,y_2\in B$, if $(x,y_1)\in A$ and $(x,y_2)\in A$, then $y_1=y_2$

defn. a function $f:A\rightarrow B$ is one-to-one if for all $x_1,x_2\in A$, $x_1\neq x_2$ imples $f(x_1)\neq f(x_2)$.

defn. a function $f:A\rightarrow B$ is onto $B$ if for every $y\in B$ there exists $x\in A$ such that $f(x)=y$.

defn. an equivalent relation is a relation with

• symmetry: if $(x,y)\in R$ then $(y,x)\in R$
• transitivity
• reflexivity

defn. $|A|\leq|B|$ if there exists a one-to-one function $f:A\rightarrow B$.

defn. $|A|=|B|$ if any of following true

• $|A|\leq|B|$ and $|B|\leq|A|$;
• there exists $f:A\rightarrow B$ that is both one-to-one and onto.

theorem. (Cantor–Bernstein) two definitions above are equivalent.

eg. let $E=\{2m:m\in \mathbb{N}\}$. then $|E|\leq|\mathbb{N}|$ because we have $f(m)=\frac{m}{2}$, and $|\mathbb{N}|\leq|E|$ because we have $f(m)=2m$. so $|E|=|\mathbb{N}|$.

eg. let $A=(0,1)\subseteq \mathbb{R},B=[0,1]\subseteq\mathbb{R}$. then $|A|\subseteq|B|$ because we have $f(x)=x$, and $|B|\leq|A|$ because we have $f(x)=\frac{x}{2}+\frac{1}{4}$ (shrink B to fit in A). so $|A|=|B|$. but it is not obvious to find a both one-to-one and onto function.

eg. show $|\mathbb{Z}|=|\mathbb{N}|$.
define $g:\mathbb{Z}\rightarrow\mathbb{N}$

$$g(x)=\begin{cases} 2x & \text{, } x\geq 0 \\ -2x+1 & \text{, } x<0 \end{cases}$$

it is both one-to-one and onto. $\square$

examples of infinite sets of same cardinality:

• $E\approx\mathbb{N}$
• $(0,1)\approx[0,1]$
• $\mathbb{Z}\approx\mathbb{N}$
• $\mathbb{R}\approx(0,1)$: use $\tan:(-\frac{\pi}{2},\frac{\pi}{2})\rightarrow \mathbb{R}$ function
• any two real intervals are of same cardinality

theorem. (Cantor) $\mathbb{N}\approx\mathbb{Z}\approx E\not\approx (0,1)\approx[0,1]\approx\mathbb{R}$.
proof. show there does not exist an onto function from $\mathbb{N}$ to $(0,1)$ (or equivalently $(0,1)$ to $\mathbb{N}$). let $f: \mathbb{N}\rightarrow(0,1)$ be any function, write

$$f(0)=0.x_0^0x_1^0x_2^0...x_n^0...\\ f(1)=0.x_0^1x_1^1x_2^1...x_n^1...\\ ...\\ f(m)=0.x_0^mx_1^mx_2^m...x_n^m...\\ ...\\$$

choose the diagonal $d=0.x_0^0x_1^1...x_n^n...$, and let $r_f=0.y_0y_1...y_n$ where for all $i$ we have $y_i\neq x_i^i$. we claim $r_f$ is not in the range of $f$. so $f$ is not onto. $\square$

theorem. (generalized Cantor) for every set $A$, $A\not\approx 2^A$.
pf. let $f:A\rightarrow2^A$ and we want to show it cannot be onto. define $Z_f=\{x\in A:x\notin f(x)\}\subseteq A$, we have $Z_f\in2^A,$ we want to show for no $x\in A$ we get $f(x)=Z_f$ ($f$ must miss this subset in $2^A$). assume for contradiction that we have $x_0$ such that $f(x_0)=Z_f$, if $x_0\in Z_f$ then $x_0\notin Z_f$, and vice versa... $\square$

Week 2. Jan 10

eg. show for all $A$ we have $A\leq \mathcal{P}(A)$.
define one-to-one mapping $f(a)=\{a\}\forall a\in A$. further by generalized Cantor we have $A<\mathcal{P}(A)$. $\square$

eg. show $\mathbb{R}\approx\mathcal{P}(\mathbb{N})$.
start by $\mathbb{R}\approx(0,1)$. note we can use binary expansion to represent numbers in (0,1), eg 0.10110100... but for each number, this series of 0 and 1's will represent a subset of natural numbers if 1 represents chosen and 0 otherwise for $i\in\mathbb{N}$-th digit. eg f(0.10101) = {0,2,4}. $\square$

corollary. $|\mathbb{N}|<|\mathbb{R}|$.

puzzle. suppose we have $A<\mathcal{P}(A)<\mathcal{P}(\mathcal{P}(A))<...$ what is the size of these sets altogether? the 'number' of sizes is larger than the 'size' of any set.

puzzle. is there any set $A$ such that $|\mathbb{N}|<|A|<|\mathbb{R}|$, ie size between that of $\mathbb{N}$ and $\mathbb{R}$? there is no way to answer this question.

notation.

• $\alef_0=|\mathbb{N}|$
• $\alef_1=$ next infinite set of size larger than $\alef_0$
• $\alef_2=$...

defn. set of size $\alef_0$ are called countable sets.

• every infinite subset $A\subseteq\mathbb{N}$ is countable.

defn. set of size greater than that of $\mathbb{N}$ is uncountable.

theorem. (closure properties of family of countable sets)

1. if $A,B$ are both countable, so is $A\cup B$.
   • proof. we know $A\approx2\mathbb{Z},B\approx2\mathbb{Z}+1$. then we naturally have one-to-one function that maps even+odd numbers to integers, then to naturals. $\square$
2. if there are finite countable sets $A_1,A_2,...$ that are countable, then so is $\bigcup_{i\in\mathbb{N}}A_i$.

corollary. $\mathbb{Q}$ is countable.
because you can use a pairs of naturals to represent rationals, then union them.

theorem. some further notes about sizes of infinite sets:

1. every infinite set $A$ has a proper subset $B$ such that $|A|=|B|$.
2. for pairs of infinite sets $A,B$, then $|A\cup B|=\max\{|A|,|B|\}$
3. for every infinite set $A$ and natural number $n$, $|A^n|=|A|$
   1. it is not the case if $n$ is infinite, eg $|\mathbb{N}^\mathbb{N}|>|\mathbb{N}|$

regular languages

defn.

1. an alphabet $\Sigma$ is any finite set of symbols
2. for all $n\in\mathbb{N}$, $\Sigma^n:=\Sigma\times...\times\Sigma$ (n times) is the set of all sequences $a_1...a_n$ such that for all $i\leq n$ we have $a_i\in\Sigma$
3. $\Sigma^*:=\bigcup_{n\in\mathbb{N}}\Sigma^n$, ie the set of all finite sequence of members of $\Sigma$
4. a language is a subset of $\Sigma^*$.

every alphabet $\Sigma$ that we discuss will be finite.

theorem. $|\Sigma^n|=|\Sigma|^n$.

theorem. $\Sigma^*\approx\mathbb{N}$, ie it is countable.

theorem. the set of all languages over $\Sigma^*$ is not countable.
proof. $\mathcal{P}(\Sigma^*)\approx\mathcal{P}(\mathbb{N})\approx\mathbb{R}$. $\square$

defn. a deterministic automaton (DFA) is a 5-tuple:

• $\Sigma$ the alphabet of inputs to A
• $Q$: finite set of states of A
• $q_0\in A$: the initial state
• $\delta:Q\times\Sigma\rightarrow Q$: a transition function
• $F\subseteq Q$: accepting states

defn. the language $L$ is accepted by $A$, ie $w=\sigma_1...\sigma_n\in L(A)$ iff $\exists x_1,...,x_n\in Q$ such that $x_0=q_0$ and $\forall i\, x_{i+1}=\delta(x_i,\Sigma_{i+1})$ and $x_n\in F$.

eg. construct a DFA that accepts a string $w\in\{0,1\}^*$ iff the number of 1's in $w$ is even.

accepting state is q0.

eg. describe a DFA $A$ such that $L(A)=\{w=w_1...w_n:n\in\mathbb{N},w_n=1\}$ (it it ends with 1).

eg. find a DFA such that $L(A)=$ all strings that starts and ends with the same symbol.
start from q0, if the first symbol is 1, then go to the same DFA above; if first symbol is 0, ...

eg. find $A$ such that $L(A)=\{w:\#_0(w)\equiv1\mod k\}$ where $\#_0=$ number of symbols 0 in $w$.
we need to store how many 0's we have seen so far.

eg. describe a DFA such that $L(A)=\{w=w_11111w_2:w_1,w_2\in\{0,1\}^*\}$, ie it has four 1's.

how can we prove that the language is accepted by A? one way of providing such statement is, for every state $q_i\in Q$, let $L(q_i)=\{w:\text{upon reading }w\text{ we end in state }q_i\}$. describe each language $L(q_i)$ and prove by induction on the length of $w$ that $w\in L(q_i)$ iff it satisfies properties.

theorem. there are languages $L\subseteq\Sigma^*$ such that no DFA accepts it.
proof. for every nonempty alphabet $\Sigma$ we have $\Sigma^*=|\mathbb{N}|=\alef_0$, then $\{L:L\subseteq\Sigma^*\}=|\mathcal{P}(\mathbb{N})|>\alef_0$, so the number of languages uncountable. we claim the number of DFAs over a given $\Sigma$ is countable. let $W_n=\{A:A\text{ is DFA with at most }n\text{ states}\}$, then we have at most $n^{n|\Sigma|}$ possible transition tables. recall that $A=(q_0,\{q_0,...,q_{n-1}\},\delta,F)$, the number of possible $F$ is $2^n$, so $|W_n|\leq nn^{n|\Sigma|}2^n$ is finite. hence the set DFAs is countable, but the number of languages are not. we cannot cover all the languages. $\square$

definition. a regular language is a language that is accepted by a DFA.

corollary. the number of regular languages based on $\Sigma$ is countable.

theorem. (closure properties of the set of regular languages)

1. closure under complement: if $L$ is a regular language then so is $\overline{L}=\{w:w\notin L\}$

   • proof. flip the accepting states. $\square$

2. if both $L_1,L_2$ are regular, then so is $L_1\cup L_2$

   • proof. let $A_1=(\Sigma,Q_1,\delta_1,F_1,q_0^1),A_2=(\Sigma,Q_2,\delta_2,F_2,q_0^1)$ be such that $L(A_1)=L_1,L(A_2)=L_2$. let the new DFA be $A_u=(\Sigma,Q_u,\delta_u,F_u,q_0^u)$ where
     • $Q_u=Q_1\times Q_2$
     • $q_0^u=(q_0^1,q_0^2)$
     • $\delta_u((q_i,q_j),\sigma)=(\delta_1(q_1,\sigma),\delta_2(q_j,\sigma))$
     • $F_u=F_1\times Q_2\cup Q_1\times F_2=\{(q_i,q_j):\text{either }q_1\in F_1\text{ or }q_2\in F_2\}$.

   use induction to show it satisfies. $\square$

3. if both $L_1,L_2$ are regular, then so is $L_1\cap L_2$.

   • pf. same but $F^\cap=F_1\times F_2$. $\square$

Week 3. Jan 17

defn. a non-deterministic automaton (NFA) is a tuple $N=(\Sigma,Q,\delta,F,q_0)$ where

1. $\delta:Q\times(\Sigma\cup\{\epsilon\})\rightarrow\mathcal{P}(Q)$

or informally, NFA is a DFA plus following relaxations:

1. allowing multiple same-label transition out of state
2. allowing $\epsilon$-transition (switching between states without reading an input symbol)

defn. the language $L$ is accepted by $N$, ie $w\in L(N)$ iff $\exists\overline{w}$ obtained from $w$ by inserting the symbol $\epsilon$ in as many places and $\exists x_1,...,x_m$ such that $x_1=q_0$ $\forall i\,x_{i+1}\in\delta(x_i,y_i)$ where $y_i$ is ith symbol in $\overline{w}$ and $y_m\in F$.

eg. given DFA's $A_1,A_2$ construct $A_3$ accepting $L(A_1)\cup L(A_2)$

eg. let $L=\{w\in\{0,1\}^*:\text{third-last symbol in }w\text{ is }1\}$ = {111, 000100, 00101, ...}.

we can choose many paths. if any path leads us to an accepting state then w is accepted.

using DFA, we would remember the last 3 letters and each correspond to a state.

theorem. (closure properties of the set of languages accepted by NFAs)

1. closure under concatenation: if $L_1,L_2$ are accepted by $N_1,N_2$, respectively, then $L_1\circ L_2=\{w_1w_2:w_1\in L_1,w_2\in L_2\}$ is accepted by an NFA.
   • proof. we chain $N_1$ and $N_2$: let the accepting states of $N_1$ transit to the starting state of $N_2$ using $\epsilon$, and let the accepting states of $N_1$ be no longer accepted. $\square$
2. closure under * operation: given language $L$ accepted by $N$, let $L_0=\varnothing,L_1=L,L_{n+1}=L_nL$, then $L^*=\bigcup_{n\in\mathbb{N}}L_n=\{w_1...w_n:w_i\in\Sigma,n\in\mathbb{N}\}$ is accepted by an NFA.
   • proof. construct $N^*$ with a new starting state $q_*$ which is also accepted, and transits to starting state of $N$, $q_0$, using $\epsilon$. let all the accepting states of $N$ transit to $q_0$ via $\epsilon$. $\square$

remark. if we do not add this new $q_*$ but reuse $q_0$ we would have error: a word finishes scanning and land on non-accepting state which can transit to $q_0$, then this word is suddenly accepted.

theorem. a language $L$ is accepted by an DFA iff is accepted by a NFA.
proof.

• (forward) every DFA is also an NFA.
• (backward) given some NFA $N=(Q,q_0,\delta,\Sigma,F)$, construct $A=(Q',q_0',\delta',\Sigma,F')$ where
  • $Q'=\mathcal{P}(Q)$
  • $q'=\{q_0\}$
  • $\delta'(R,a)=\bigcup_{q\in R}\delta(E(q),a)$ where $E(q)$ is the set of states reachable from $q$ via ϵ-transitions only
  • $F'=\{w\subseteq Q:w\cap F\neq\varnothing\}$ $\square$

corollary. converting an NFA into a DFA, the DFA may have $2^n$ states.

corollary. a language is regular is regular iff it is accepted by an NFA.

corollary. the set of all regular languages is closed by union, intersection, concatenation and star.

theorem. every finite language is regular.
proof. let $L=\{w_1,...,w_n\}$. we know for every word $w_i=a_{i1}...a_{ik_i}$, the individual letters $\{a_{i1}\},...\{a_{ik_i}\}$ are regular, by closure of concatenation, we know for every word $w_i$, $L_{w_i}=\{w_i\}=\{a_{i1}...a_{ik_i}\}$ is regular. by closure of union we know $L=L_{w_1}\cup...\cup L_{w_n}$ is regular. $\square$

theorem. every regular language can be derived from these basic languages by a finite sequence of closure operations.

inductive definition of regular languages

we can define sets in 3 ways:

• listing all elements
• describing common properties
• inductive definition: define domain (universe) $X$, core set $A$, and operations $O$, then $I(X,A,O)$ is minimal set $W$ containing $A$ and is closed under operations in $O$.
  1. we will require both $X$ and $A$ are defined and
  2. $A\subseteq X$
  3. O is a set of functions from $X^n$ to $X$

Week 4. Jan 24

eg. X = all human beings, A = {me}, O = {parent of, child of, spouse of}. my blood relatives are I(X,A,O).

theorem. if $W_1,W_2$ are two sets that contain $A$ and is closed under $O$, then $W_1\cap W_2$ also contains $A$ and is closed under $O$.

theorem. (minimality) define $W=\bigcap_iW_i$ where $W_i$'s are all sets that contain $A$ and is closed under $O$, then not only $W$ contain $A$ and is closed under $O$, but also is minimal in this respect.
proof. because if any set $\overline{W}$ satisfies the properties, then it is among the sets intersected in the definition of $W$, so $W\subseteq\overline{W}$. $\square$

theorem. such $W=\bigcap_i W_i$ is unique.

eg. assume we know real numbers, define natural numbers: $I(\mathbb{R},\{0\},\{x\mapsto x+1\})=\mathbb{N}$.

eg. define set of all polynomials with integer coefficients.

• $X=$ all finite strings over $\Sigma=\mathbb{N}\cup\{+,\land,*\}$
• $A=\{+1,-1,x\}$
• $O=\{(p,q)\mapsto p+q,(p,q)\mapsto p* q\}$

eg. set of all propositional formulas.

• $X=$ all finite strings over $\Sigma=$ lower case English letters with/without indices $\cup\{(,),\land,\lor,\rightarrow,\lnot\}$
• $A=$ all lower letters with/without indices
• $O=\{\frac{\alpha,\beta}{\alpha\lor\beta}\},\{\frac{\alpha,\beta}{\alpha\land\beta},\{\frac{\alpha,\beta}{\alpha\rightarrow\beta}\},\{\frac{\alpha}{\lnot\alpha}\}\}$

inductive sets have the ability to prove properties by structural induction.

• formally: let $R\subseteq X$ be some property, if $A\subseteq R$ and whenever $[x_1,...,x_n]\in R^n$ so is $f(x_1,...,x_n)$ for every $f\in O$, then $I(X,A,O)\subseteq R$.

eg. have 3 cups initially positioned as ∪∩∪, one can flip two cups each time. can i finally flip all of them upright?

• base set: {∪∩∪}
• operations: {flip left two, flip right two, flip two ends}
• property: number of upright cups is even.
  1. for base set: we know ∪∩∪ satisfies property.
  2. if we have a configuration $c$ satisfying this property, if we flip two, then either i flipped two in same position => number changed by 2 => no effect on oddity; or i flipped one up and one down => number does not change. so we still have even number.
  3. we can never have all cups upright (∪∪∪ is outside R). $\square$

we can use inductive sets to revisit regular expressions.

defn. set of regular expressions is $I=(\text{alphabet}^*,A,O)$ where:

1. alphabet: $\Sigma\cup\{\epsilon,\varnothing,(,),\circ,*,\cup\}$
2. core: $A=\Sigma\cup\{\epsilon,\varnothing\}$
3. operations: $O=\{\frac{R_1,R_2}{R_1\cup R_2},\frac{R_1,R_2}{R_1\circ R_2},\frac{R_1}{R_1^*}\}$

we can generate $\epsilon,a,b,a\circ b,a^*,(a\cup b)^*$, etc.

for simplicity we omit "$\circ$", and delete brackets according to priorities: $* >\circ>\cup$. it is also common to use $+$ instead of $\cup$.

theorem. for alphabet $\Sigma$, we define a function $L$ that maps regular expressions to languages for every regular expression $r$ such that $L(r)$ is subset of $\Sigma^*$

1. $L(\varnothing)=\varnothing$ (empty expression -> empty language)
2. $L(\epsilon)=\{\epsilon\}$
3. $L(a)=\{a\}$ for every $a\in\Sigma$
4. $L(R_1\cup R_2)=L(R_1)\cup L(R_2)$
5. $L(R_1R_2)=L(R_1)L(R_2)$
6. $L(R^*)=(L(R))^*$

such $L$ is well-defined.
idea. this is well defined whenever I(X,A,O) has a unique readability property, ie for every $r\in I(X,A,O)$, either $r\in A$ or there are uniquely defined $f\in O$ and $r_1,r_2\in I(X,A,O)$ such that $f(r_1,r_2)=r$.

remark. why do we need $\varnothing$ in definition of regular languages? because there are languages that do not accept anything, and we need a mapping from regular languages to it.

eg. assume $\Sigma=\{a,b\}$, let $L_1=$ all strings containing $a$, $r=(a\cup b)^*a(a\cup b)^*$, then $L(r)=L_1$.

eg. let $r=(a+b)\varnothing$, what is $L(r)$? it is $\varnothing$ because it is followed by empty set => cannot generate.

eg. find $r$ such that $L(r)=$ all strings where every $a$ is immediately followed by a $b$. $r=((\epsilon\cup a)b)^*$.

defn. a generalized non deterministic automaton (GNFA) is a tuple $(\Sigma,Q,q_0,q_F,\delta)$

1. $\Sigma$: finite alphabet
2. $Q$: finite states
3. starting state: $q_0$
4. accepting states: $q_F$
5. transitions $\delta:(Q-\{q_0\})\times(Q-\{q_F\})\rightarrow (Q-\{q_0\})$: $\delta$ defines the labeling of edges in the GNFA, where edges are regular expressions

or informally an NFA where,

1. there is a unique start state $q_0$ and no arrows go into it
2. there is a unique end state $q_F$ and no arrows go out of it
3. every arrow is labeled by a regular expression

defn. a string $w$ is accepted by GNFA $D$, ie $w\in L(D)$, iff there exists a path $q_0...q_kq_F$ such that $w=w_0w_1...w_k$ and for every $i\leq k$ we have $w_i\in L(\delta(q_i,q_{i+1}))$ and $w_k\in L(\delta(q_k,q_F))$. ie we are matching the input word by regexes part by part.

aaabb:

      a*        b*
q0 ------> q1 ------> qF

theorem. for every DFA $D$, there exists a NGFA $G$ accepting same language, ie $L(D)=L(G)$.
proof. we need to remove labels entering $q_0$: add a new nonaccepting starting state $\overline{q}_0$ that goes to the original $q_0$ by ϵ. then need to remove labels leaving accepting states: add a new accepting state $\overline{q}_F$ and any previous accepting states go to it by ϵ. make the previous accepting states non-accepting.

if we have self-loops $q_1\rightarrow q_2$ by $a$, we can star it: $a^*$.

then we relabel using regexes and eliminate useless states. given any GNFA $G=(\Sigma,Q,q_0,q_F,\delta),Q=\{q_0,...,q_k,q_F\}$, we will construct GNFA's $G_1,...,G_k$ such that $Q(G_{i+1})=Q(G_i)-\{q_i\}$ and $L(G_{i+1})=L(G_i)$, $Q(G_k)=\{q_0,q_F\}$ (?). connect any $q$ with an edge leading into $q_i$ to any node with an arrow from $q_i$ to that state

(if state $q_1$ goes to $q_2$ by two arrows $r_1,r_2$, then replace two arrows by a single one $r_1+r_2$)

we shrink edges until we only have two states from $q_0$ to $q_F$. $\square$

we now have the third type of automaton aside from DFA and NFA, we we can show the following theorem.

theorem. for every $\Sigma$, $\{L(r):r\text{ is regular expression over }\Sigma\}=\{L(A):A\text{ is a DFA over }\Sigma\}=$ all regular languages over $\Sigma^*$.
proof. we want to show for a regular expression $r$, there exists some DFA $A_r$ such that $L(A_r)=L(r)$. we know regular expressions = I(X=strings, A={∅,ϵ}∪Σ, O={...}), we want to show it has equivalent automaton. by induction, base: we just show each member $A$ has a DFA:

• ∅ (rejects everything): just a single starting state $q_0$ non-accepting, and transits everything to itself
• ϵ (accepts only empty string): one starting state $q_0$ accepting, and it transits to $q_1$ via ϵ non-accepting. $q_1$ transits to itself via ϵ.
• Σ: one starting state $q_0$ non accepting, transits to an accepting state by letters in Σ

induction: let $r_1,r_2$ be regular expressions, assume there are DFAs $D_1,D_2$ s.t. $L(D_1)=L(r_1),L(D_2)=L(r_2)$ (IH), we want to show after operations IH still holds:

• show there exists $D_3$ s.t. $L(D_3)=L(r_1\cup r_2)=L(r_1)\cup L(r_2)$: recall the family of regular languages is closed under union and result is still regex, by IH it has an $D_3$.
• show there exists $D_3$ s.t. $L(D_3)=L(r_1r_2)=L(r_1)L(r_2)$: recall the family of regular languages is closed under union...
• show there exists $D_3$ s.t. $L(D_3)=L(r^*)=L(r)^*$: recall the closure of regular languages under *...

so for every regular expression $r$ there exists some DFA $D$ s.t. $L(D)=L(r)$, and left ⊆ right.

the remaining direction is for every DFA, there is a same regular language. we just convert it into a GNFA with only two states. the regex on the edge is the regular expression we want. $\square$

Week 5. Jan 31

the pumping lemma

corollary. for every $\Sigma$ there exists $L\subseteq\Sigma^*$ that is not regular.
proof. we know the set of languages is uncountable and set of DFAs over $\Sigma^*$ is countable (so set of regular expressions over $\Sigma^*$ is countable). $\square$

can we point to a non-regular language?

theorem. (the pumping lemma) for every regular language $L$ there exist some number $n_L$ such that for every $w\in L$ such that $|w|>n_L$ there is a partition of $w$ into sections $w=xyz$ satisfying:

1. $|xy|\leq n_L$,
2. $y\neq\epsilon$,
3. $\forall i\in\N\in xy^iz\in L$.

proof. let $A$ be a DFA accepting $L$ and let $n_L$ denote number of states in $A$. let $w\in L$ with $|w|>n_L$, consider the sequence of states $q_0,\delta(q_0\sigma_1),,\delta(q_0\sigma_1\sigma_2),...,\delta(q_0\sigma_1...\sigma_m)$ where $w=\sigma_1...\sigma_m$, then there exists $\sigma_r,\sigma_s$ such that $\delta(q_0\sigma_1...\sigma_n)=\delta(q_0\sigma_1...\sigma_n\sigma_r...\sigma_s)$ (we are repeating some states).

now define $x=\sigma_1...\sigma_n,y=\sigma_{r+1}...\sigma_s,z=\sigma=\delta_{s+1}...\sigma_m$ by picking $r$ such that $\delta(q_0\sigma_1...\sigma_r)$ is different than any $\delta(q_0...q_i)$ for any $i<n$ and that $\delta(q_0\sigma_1...\sigma_{r+1}),\sigma(q_0\sigma_1...\sigma_{r+2}),...,\delta(q_0\sigma_1...\sigma_s)$ are all different, we are guaranteed that $|xy|\leq n_L$. then $\delta(q_0\sigma_1...\sigma_r(\sigma_{r+1}...\sigma_s)^i\sigma_{s+1}...\sigma_m)=\delta(q_0\sigma_1...\sigma_r(\sigma_{r+1}...\sigma_s)^j\sigma_{s+1}...\sigma_m)$ for all $i,j\in\N$. $\square$

• converse is not true

eg. given $L=\{a^nb^n:n\in\N\}$, show it is not regular.
pick any $n_L$, given a word $w=a^{n_L+1}b^{n_L+1}\in L$, since we want to have $|xy|\leq n_L$ we pick partition $xy$ to be a sequence of $a$'s. then $xy^2z$ will have $n_L+1+|y|$ $a$'s and $n_L+1$ $b$'s, which is not in $L$, failing the pumping lemma (3). $\square$

eg. show palindromes $L=\{ww^R:w\in\{a,b\}^*\}$ is not regular.
consider $w=a^{n_L+1}bba^{n_L+1}$.

eg. (languages over an alphabet with just one symbol) let $L\subseteq\{a\}^*,L_n=\{w\in L:|w|=n\}$, show every infinite language $K$ where for arbitrarily large numbers $k$ there exists $n_k$ such that for all $n_k\leq i\leq n_k+k$ such that $L_i=\varnothing$ is not regular.

given any number there is a hole of that length
a aa ... a^5 a^6 a^7 ... a^15 a^16 

pick any $n_L$, and pick any $k>n_L$ such that $w:=a^k\in K$ and for all $i\leq n_L+1$ we have $a^{k+i}\notin K$. then let $xyz$ be any partition of this word such that $|xy|\leq n_L$, then $|xy^2z|=|w|+|y|\leq k+n_L<k+n_L+1$ and it is not in $K$. $\square$

the machine will lose track of states and 'sleep' after rejecting too many.

eg. $\{a^{n^2}:n\in\N\}$ is not regular.
because the gap between $n^2$ and $(n+1)^2$ can be arbitrarily large.

eg. $\{a^p:p\text{ is prime}\}$ is not regular.
it is an infinite language but for every $k$ there exists a prime number $p$ such that $p+1,...,p+k$ is not in the language.

eg. show $L=\{w\in\{a,b\}^*:\#_a(w)\neq\#_b(w)\}$ is not regular.
use closure property. consider $\{ab\}^*-L=a^nb^n$, we know it not is regular either by last example, but it should if $L$ were regular. $\square$

combinatorial definition of regular languages

the pumping lemma is not a characteristic of regular languages, but MN theorem is.

defn. given a language $L\subseteq\Sigma^*$, we say $w,w'\in\Sigma^*$ are distinguishable with respect to $L$ if there exists some $z\in\Sigma^*$ such that one of $wz,w'z$ is in $L$ and the other is not.

claim. given $L$ we define an equivalence relation over $\Sigma^*$ by $w\equiv_Lw'$ if $w,w'$ are not distinguishable via $L$.
proof.

• reflexivity: clear
• transitivity: let $w_1\equiv_L w_2,w_2\equiv_L w_3$, then for all $z$, $w_1z\in L\iff w_2z\in L\iff w_3z\in L$ so $w_1\equiv_L w_3$.
• commutativity: clear $\square$

using this relation we can partition $\Sigma^*$ into equivalence classes.

eg. let $L_e=\{w:|w|\in2\N\}$. then $ab$ and $abb$ are distinguishable (a simplest empty string as $z$ will work). we can also partition $\Sigma^*$ into two equivalence classes (even length and odd).

eg. let $L=\{a^nb^k:n,k\in\N\}$. then there are infinitely many equivalent classes $\{w:\#_a(w)-\#_b(w)=i\}$ for all $i$...

eg. let $L_k=\{w\in\Sigma^*:\#_a(w)\leq k\}$. depending on how many $a$'s there are $k+2$ equivalent classes.

• $W_{i}=\{w:\#_a(w)= i\}$ for $0\leq i\leq k$
• $W_{>k}=\{w:\#_a(w)> k\}$

theorem. (Myhill Nerode) a language $L$ is regular iff the number of equivalence classes of $\equiv_L$ is finite. furthermore, the number of equivalence classes is the number the minimal number of states in any DFA for $L$.

• equivalently: L is regular iff number of subsets $W\subseteq\Sigma^*$ such that every two of its elements are distinguishable by $L$, is finite.

proof.

• assume $L$ is regular. then there are a DFA $D=(\Sigma,Q,q_0,\delta,F)$ that accepts $L$. note for every $q\in Q$, $\{w\in\Sigma^*:\delta(q_0,w)=q\}$ (final state) is an $\equiv_L$ equivalence class, by that for every $z\in\Sigma^*$, any words concatenated with $z$, $w,w'$ will re-start at the same previous final state (q), so $wz,w'z$ must be (un)distinguishable at the same time.
  • corollary. the number of $\equiv_L$ equivalence classes is less than $|Q|$ and therefore finite.
• assume the number of $\equiv_L$ equivalence classes is finite. for a word $w$, let $[w]_L$ denote its belonging $\equiv_L$ class. construct a DFA $D=(\Sigma,Q,q_0,\delta,F)$ by letting
  • $Q=\{w\subseteq\Sigma^*:W\text{ is equivalence class to }\equiv_L\}$
  • $q_0=[\epsilon]_L$
  • $\delta([w]_L,\sigma)=[w\sigma]_L$
  • $F=\{[w]_L:w\in L\}$.
  • for all $w\in\Sigma^*$, we have $\delta(q_0,w)=[w]_L$, so $L(D)=\{w\in\Sigma^*:\delta(q_0,w)\in F\}=\{w\in\Sigma^*:[w]_L\in F\}=\{w\in\Sigma^*:w\in L\}$.
• we have $|Q|\leq$ number of equivalence classes. the equivalence classes of $\equiv_L$ are merges of the difference kinds of inputs so number of equivalence classes $\leq|Q|$. $\square$