<aside> <img src="/icons/thought-dialogue_yellow.svg" alt="/icons/thought-dialogue_yellow.svg" width="40px" /> Can DFAs compute everything?

</aside>

Intuition, the function MAJORITY might be difficult for DFAs because we “have to” count. And indeed, MAJORITY is not regular.

Other examples that DFA can’t calculate is like “string with same number of 0 and 1”, etc..

Pumping Lemma

A lemma that allows you to check whether if a function is regular.

If f is a regular function, then there exists a number p such that every string x such that f(x)=1 of length ≥ p, can be written as x = abc such that

a) $f(ab^ic) = 1$ for all i ≥ 0

b) length of b > 0

c) length of ab ≤ p

In language, we can represent it as

L is a regular language $\implies$

$\exist$ a number p such that $\forall x\in L$ of length ≥ P

$\exist x = abc$ (b is not empty and length (ab) <+ p) such that

$\forall i, \quad ab^ic \in L$

Intuitive description: If L is regular then every sufficiently long string x in L has a piece that can be repeated while being in L

Example:

$L=\{0^k10^k:k\ge 1\}$

Suppose L is regular

• There exist some number p such that conclusion of PL hold
• Pick a x = $0^p10^p$
• By PL we must be able to split x = abc and length(ab) ≤ p
• ⇒ b is made up only 0s
• Then, abbc will have more 0 before the first 1
• abbc is not in L, but PL says it should be, so there exists the contradiction

⇒ L is not recognizable by a DFA

<aside> 💡 What if L has a finite size? → P could be higher than the largest one in the finite set

</aside>

Another example:

PALINDROME = {x: x= reverse(s)}

Claim: PALINDROME is not regular

Proof:

• Suppose palindrome is regular
• There is some p such that PL holds