Context Free Pumping

Sat 11:30 AM

Prof. Calvin

CSCI 5100

Sketch

• CF Pumping Lemma
  • Statement
  • Examples

Preface

Avoid this trap

• Suppose we wish to prove a language is not a context free language
• We must prove there is no CFG/PDA that recognizes the language.
• It may be tempting to conclude:
  • I thought about it really hard.
  • I could find no PDA/CFG
  • Therefore the language is not a context free language.

Example

• Take \(\Sigma = \{0,1,2\}\)
• Take \(B = \{0^k1^k2^k| k \in \mathbb{N}\}\)
• This language is not a context free language.
  • If you had a stack, match 0s with 1s
  • How to deal with 2s?
  • Not a proof, but an intuition.

Pumping Lemma

Regular Pumping Lemma

\[ \begin{aligned} &\forall A:\exists p \in \mathbb{N} : \\ &\exists xyz \in A : |xyz| \geq p \implies \\ &\forall i \in \mathbb{N} : xy^iz \in A \land \\ &|y| > 0 \land \\ &|xy| \leq p \end{aligned} \]

• That is, \(\{xz, xyz, xyyz\} \in A\)
• We “pump up” the number of occurances of y

Context Free Pumping Lemma

\[ \begin{aligned} &\forall \text{ CFL } A :\exists p \in \mathbb{N} : \\ &\exists s = uvxyz \in A : |uvxyz| \geq p \implies \\ &\forall i \in \mathbb{N} : uv^ixy^iz \in A \land \\ &|vy| > 0 \land \\ &|vxy| \leq p \end{aligned} \]

• That is, \(\{uxz, uvxyz, uvvxyyz\} \in A\)
• We “pump up” occurances of v and y

Sketch of Proof

• We imagine an arbitrarily long string.
  • We’ll be precise latter.
• The parse tree of a long string is very high.
  • Recall parse trees:

Checkin

• Can a string of length 1 million be made my a parse tree of height 1?
  • How about all factors of 1 million?
• We’ll quantify this shortly.

\[ \begin{aligned} &S \rightarrow 0^{10^6} \\ \end{aligned} \]

Given a tall tree

• Let’s assume the tall tree
• Each step in the tree involves variable substitution
• So as soon as height is greater than the size of set of variables, we necessarily repeat some variable.

Tikz

• I’m going to use a new tool to show the next bit: Tikz!
  • Part of LaTeX
  • Seems to run well inside of R
• Credit LaTeX Graphics using TikZ
• Credit JBGruber

Example

\begin{tikzpicture}
 \draw (0,0) circle (1cm);
\end{tikzpicture}

Proof by Picture

\(s\) is long

Parse Tree

Begin with \(E\)

Tree is tall

Take a Derivation

Necessary Repetition

\(R\) to \(s\)

\(s\) to \(uvxyz\)

Displace the lowest \(R\)…

With the higher \(R\)…

Side by side

• On the left we have \(s = uvxyz\)
• On the right we have \(s = uvvxyz = uv^2xy^2z\)
• Process is repeatable.

Deskew

Code Reveal

\begin{tikzpicture}
\fill[darkgray!40!black] (0,0) rectangle (10,7);
\draw[white] (2,2) -- node[below,cyan] {u} ++(1,0)  -- node[below,cyan] {v} ++(1,0) ;
\draw[white] (4,2) -- node[below,cyan] {x} ++(2,0);
\draw[white] (6,2) -- node[below,cyan] {y} ++(1,0) -- node[below,cyan] {z} ++(1,0);

\draw[white] (5,5.5) -- node[below,cyan] {E} ++(0,0) ;

\draw[white] (5,4.5) -- node[below,cyan] {R} ++(0,0) ;
\draw[white] (5,3.5) -- node[below,cyan] {R} ++(0,0) ;

\draw[white] (2,2) -- (5,5) ;
\draw[white] (5,5) -- (8,2) ;

\draw[white] (3,2) -- (5,4) ;
\draw[white] (5,4) -- (7,2) ;

\draw[white] (4,2) -- (5,3) ;
\draw[white] (5,3) -- (6,2) ;

\end{tikzpicture}

\begin{tikzpicture}
\fill[darkgray!40!black] (0,0) rectangle (10,7);
\draw[white] (2,2) -- node[below,cyan] {u} ++(1,0)  -- node[below,cyan] {v} ++(1,0) ;
\draw[white] (6,2) -- node[below,cyan] {y} ++(1,0) -- node[below,cyan] {z} ++(1,0);

\draw[white] (5,5.5) -- node[below,cyan] {E} ++(0,0) ;

\draw[white] (5,4.5) -- node[below,cyan] {R} ++(0,0) ;
\draw[white] (5,3.5) -- node[below,cyan] {R} ++(0,0) ;
\draw[white] (5,2.5) -- node[below,cyan] {R} ++(0,0) ;

\draw[white] (2,2) -- (5,5) ;
\draw[white] (5,5) -- (8,2) ;

\draw[white] (3,2) -- (5,4) ;
\draw[white] (5,4) -- (7,2) ;

\draw[white] (3,1) -- (5,3) ;
\draw[white] (5,3) -- (7,1) ;

\draw[white] (4,1) -- (5,2) ;
\draw[white] (5,2) -- (6,1) ;

\draw[white] (3,1) -- node[below,cyan] {v} ++(1,0) -- node[below,cyan] {x} ++(2,0) -- node[below,cyan] {y} ++(1,0) ;

\end{tikzpicture}

\(uxz\)

Context Free Pumping Lemma

\[ \begin{aligned} &\forall \text{ CFL } A :\exists p \in \mathbb{N} : \\ &\exists s = uvxyz \in A : \\ & |uvxyz| \geq p \implies \\ &\forall i \in \mathbb{N} : uv^ixy^iz \in A \land \\ &|vy| > 0 \land \\ &|vxy| \leq p \end{aligned} \]

Proof

Details

• Take \(b\) maximum branch size
• Take \(h\) height parse tree
• Need \(|s| < b^h\)
• Let \(p = b^{|V|}\)
  • \(V\) is the set of variables.

All conditions

• \(uv^ixy^iz \in A \forall i \in \mathbb{N}\)
  • Cut and paste
• \(vy \neq \varepsilon\)
  • Take smallest possible tree.
• \(|vxy| \leq p\)
  • Pick lowest \(R\)

Example

• Take \(B = \{0^k1^k2^k|k\in\mathbb{N}\}\)
  • Need 0, 1, and 2 in \(vxy\)
    • \(|vxy| \leq p\)
  • Pumping anything leads to unequal.
  • Not in CFL by condition 3.

Stretch Break

• Home