Skip to main content

8. Disproving Regularity

27/02/23

How to show that a language is not regular

The Pumping Lemma​

Given a regular language LL, then there is a number n∈Nn\in\mathbb{N} such that all words w∈Lw\in L that are longer than n(∣w∣≥n)n(|w|\ge n) can be split into three words w=xyzw = xyz s.t.

  1. y≠ϵy \neq \epsilon
  2. ∣xy∣≤n|xy| \le n
  3. ∀k∈N.xykz∈L\forall k \in \mathbb{N} . xy^kz\in L