06.1 Pumping lemma

Last updated Nov 9, 2022

(Česky “věta o pumpování”)

• Vlastnost regulárního jazyka

• Platí pro každý regulární jazyk

  • (ale ne obráceně - tedy pokud platí PL, jazyk může a nemusí být regulární)

• Lze využít k důkazu, že nějaký jazyk není regulární

• Pro automat, který obsahuje nějakou smyčku (ze stavu do sebe samého), tedy lze opakovat/pumpovat symboly nekonečněkrát

• Předpokládejme jazyk $L = {0^{n}1^{n}: n \ge 1 }$ by regulární
• V takovém případě by $L$ byl přijímán konečným automatem $\mathcal{A}$ s $m$ stavy
• Nechť čte posloupnost $0^{m}$, jednou dojde přes $i$ stavů do posledního stavu automatu - označme ho $q.$ (Princip holubníku)
  • tj. $\exists i \lt j: p_{i} = p_{j}$
  • (i) Neformálně - $\mathcal{A}$ nemůže mít nekonečno stavů, takže po $i$ stavech zavedeme další poslední se smyčkou, kde se budou znaky hromadit
  • tedy nelze poté určit jejich počet
• Mohl by nám vzniknout automat, který přijímá jiný počet $0$ než $1$, ale to už nesplňuje zadání $L$
• $\Rightarrow$ jazyk $L$ není regulární

• Nechť $L$ je regulární jazyk, pak pro něj existuje konstanta $p \ge 1$ taková, že pro každou větu $w \in L$ platí:

• Jestliže $|w| \ge p$, pak $w$ lze zapsat ve tvaru $w = xyz$ tak, že: ^podminky-pl

  1. $y \neq \varepsilon$ (tj. $|y| \ge 1$) (smyčka nemůže být $\varepsilon$, musí mít alespoň 1 znak)
  2. $|xy| \le p$ (určitě se v první části věty ($xy$) projde smyčkou)
  3. $\forall k \ge 0: xy^{k}z \in L$ (smyčka se opakuje $k$-krát)

• (i) Pro všechny věty $w \in L$, které jsou delší jak $p$, platí, že při přijímání věty $w$ pomocí automatu $M$ se alespoň jednou projde cyklem

• Minimální $p = 6$
• Jakékoliv věty délky 6 a více musí nutně procházet smyčkou, aby byly přijaty

Pozn. pro konečný jazyk

• U konečného jazyka je minimální $p$ rovno nejdelší přijímající větě + 1
• Protože PL musí platit u všech regulárních jazyků, určením $p$ větší než nejdelší přijímanou větu ho tedy stále budeme splňovat