8 - Non-context-free Grammar

ucla | CS 181 | 2024-05-13 14:09

---

Table of Contents

• Pumping Lemma for CFL
  • Proof with CFG
• Examples

Pumping Lemma for CFL

• similar to one for reg languages but: $w=uvxyz$
• where $|vxy|\le p$ $|v|+|y|\ne 0$ $u{v}^{i}x{y}^{i}z\in L\mathrm{\forall }i\in \mathbb{N}$

  Proof with CFG

• given a CFG, we define the branching factor $b$ as the max length of the RHS in $R$ (considering vars + terminals)

• sps. $p=b^{

  V

  +1}$

• $s$ is a string in $L$ s.t. $

  s

  \ge p$

• so we an create a parse tree for the minimal parse tree of the longest path, here we can now visually represent pumping up and down

  Examples

•