5 - Non-Regularity

ucla | CS 181 | 2024-04-22 14:25

---

Table of Contents

• First Non. Reg. Lang.
• Pumping Lemma
  • Contrapositive
  • Examples
• Proving non-regularity using closure properties
• Common Pitfalls

First Non. Reg. Lang.

• $L=0^n{1}^n:n\ge 1$
• Consider an automaton $M$ with $P$ states. Suppose we have a binary string $w=0^P{1}^P\in L$
• By the P.P., this string must have a loop in the automaton.
• Suppose the loop is on 0 (although there should be a loop on both).
  • Let $x$ be the substring prior to the loop ($0\dots 0_k$)
  • Let $y$ be the substring in the loop ($0{k+1}…0{p-1}$)
  • Let $z$ be the substring after the loop ($0_{p}1\dots 1_p$)
• If $M$ accepts $xyz$, it accepts $xyyz$ BUT $xyyz\notin L$.

Pumping Lemma

• Let $L$ be a reg. lang., then $\mathrm{\exists }p\in \mathbb{N}$ s.t. every $w\in L$ of length $\ge p$ can be written as $w=xyz$ where
  • $x,y,z$ are strings
  • $y\ne \epsilon$

  • $

    xy

    \le p$

  • $x{y}^{i}z\in L,\mathrm{\forall }i\in \mathbb{N}$
• i.e., all sufficiently long strings in the language can be pumped
• a pumping length $p$ is at least the number of states in the DFA(?), thus for strings valid to the lemma, they must visit at least 1 state more than once -> a loop

  Contrapositive

• $\forall p\space:\space \exists w\in L,\space

  w

  \ge p$

• $\mathrm{\forall }x,y,z$:
  • $w=xyz$
  • $y\ne \epsilon$

  • $

    xy

    \le p$

  • $\mathrm{\exists }i:x{y}^{i}z\notin L$
• then, this implies $L$ is nonregular
• this is NOT bidirectional i.e. some nonregular langs satisfy pumping langs

  Examples

• $L={10}^n{1}^n$
  • consider the string ${10}^p{1}^p$, then there are 2 cases:
  • case 1: $y$ is the first 1 $⟹$ pumping down makes thee\ string no longer in the lang, thus lang is nonreg
  • case 2: $y$ is in the $0^p$ string, then pumping down makes the number of 0s $\ne$ number of 1s, thus $xz$ (we pumped out $y$) not in the lang $⟹L$ is nonreg
• $L=1^{n^2}$
  • consider $w=1^{p^2}$

  • $p^2\lt

    xy^2z

    =

    xyz

    +

    y

    =p^2+

    y

    $

    • note that adding a single symbol should make the number of 1s to be $(p+1{)}^2=p^2+2p+1$ chars long

  • and since $

    y

    \le p$wecansayintheedge(“best”)case$

    y

    =p$

  • s.t. $p^2\le

    xyz

    +

    y

    \le p^2 +p\lt p^2+2p+1=(p+1)^2$

  • thus $x{y}^{2}z\notin L⟹L$ is nonregular
• $L=w:w=w^R$
  • consider $w=0^p{10}^p$
  • then $y\in 0^p$ is fragile s.t. pumping up or down will make the number of 0s on the left be more or less than the number of 0s after the 1, which is not in the language, thus $L$ is nonregular
• $L=ww:w\in {0,1}^{\ast }$
  • consider $w=0^p{10}^{p}1$ s.t. $y\in 0^p$ (the first part)
  • then pumping $y$ up or down will lead to the first half of the string != the second half, thus not in the lang => L is nonreg

• $L={w:

  w

  \in \mathbb{P}}$($\mathbb{P}=$primes)

  • consider $w=0^q$ s.t. $q\in \mathbb{P}:q\ge p$

  • then consider $w=xy{y}^{q}z$ s.t. $

    xyy^qz

    =

    xyz

    +q

    y

    =q+q

    y

    =q(

    y

    +1)$

  • thus the size of this string is a composite number which can never be a prime number, thus the string $xy{y}^{q}z\notin L⟹L$ is nonreg
• $\mathrm{\Sigma }=0,1,\dots ,9$; $L=w\in {\mathrm{\Sigma }}^{\ast }:\text{ fractional part of PI starts with }w$
  • e.g. $L=\epsilon ,1,14,141,1415,14159,\dots$

  • consider $w=14159265358979\dots$ s.t. $

    w

    =p$

  • sps. $x{y}^{i}z$ is pumpable $\mathrm{\forall }i$ , then it means that as we take $i$ to the limit $3.x{y}^{i}z\to 3.xyyyy\dots$ which is a rational number while $\pi$ is not
  • thus $\mathrm{\exists }i$ s.t. $x{y}^{i}z$ is not in the language => L is nonreg

    Proving non-regularity using closure properties

• Instead of applying the contrapositive of the pumping lemma (P.L.), we can show with closure under regular operations that a language is regular or non-regular
• e.g., $L=0^n{1}^m:n\ne m$
  • we can show ${0^1^}\setminus L={0^n1^n\space:\space n\in \mathbb Z^+}$isnonregular,andbcsetminusisaregularoperationundertheclosurepropertyofsetminus,$L$ must be non-regular
  • proving this using P.L. is a little more complex, consider the string $0^p{1}^{p+a}$ where we don’t yet know the value of $a$ such that the string is in thee language but can be pumped to prove nonregularity

  • consider $w=xyy^{\frac{a}{

    y

    }}z$ s.t. the number of 0s should equal thee number of 1s to prove nonregularity

  • then we can say that there are $p+a$ ones and $p+\frac a{

    y

    }

    y

    $0s,thusforthenumberofystobeintegervalues,wemutensure$a$isalwaysdiivisibleby$y$whichmeansweshouldchoose$a=p!$thenweget$p+p!$ones=$p+\frac{p!}{

    y

    }

    y

    $ 0s

  • thus the number of 0s = num 1s is not in the lang, thus the lang is nonreg

    Common Pitfalls

• reg langs closed under infinite union
  • false
• subsets of reg langs are reg
  • False: $L_{nonreg}\subseteq {\mathrm{\Sigma }}^{\ast }$
• subsets of nonreg langs are nonreg
  • False: $\mathrm{\varnothing }\subseteq 0^n{1}^n$
• nonreg langs are closed under complement
  • True: bc if not true $⟹$ the complement off a reg lang could be non reg which is not. possible bc $L_{reg}⟺\overline{L_{reg}}$
• nonreg langs closed under intersection
  • False: consider intersection of 2 nonreg langs that resultss in the set of the empty string e.g. $0^n{1}^n\cap 1^n{0}^n=\epsilon$