\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Answer
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
Math and science::Theory of Computation

Pumping lemma for regular languages

The pumping lemma is useful for showing that a language cannot be represented by a finite state machine.

Can a language be accepted by an automaton?

There are two cases.

  1. If a language contains only finite strings, we can create a finite automaton that handles each case.
  2. If a language contains infinite strings, we look to the pumping lemma to answer this question.

The gist of the lemma

The gist of the pumping lemma is: if a finite set of states is able to represent an infinite string, then during the state transitions between start and accept states, there must be a [...] at some point. This property can be used to show, by contradiction, that some languages cannot be represented by finite state automata.

Pumping lemma

If \( A \) is a regular language, then there is a number \( p \) (the pumping length) where if \( s \) is any string in \( A \) of length at least \( p \), then \( s \) may be divided into three pieces, \( s = xyz \), satisfying the following three conditions:

  1. for each \( i \ge 0, xy^iz \in A \)
  2. \( |y| \ge 0 \)
  3. [...]