רעיון ההוכחה:

עבור מילים מספיק ארוכות ($|w|>|Q|$) יתקיים בהכרח שחוזרים על מצב $q$ בריצה על $w$. קטע המילה שבין החזרות יכול לשמש לניפוח המילה ($y$ בציור).

כן והיא ניתנת לניפוח עם $n=\max|w|+1$ ואז השפה ניתנת לניפוח באופן ריק שכן אין שום מילה שכזו.

הוכחה:
נוכיח כי $L$ לא ניתנת לניפוח ⇐ לפי שלילת למת הניפוח, נסיק כי $L$ אינה רגולרית.
יהי $n \in \mathbb{N}^+$. נבחר $w=a^nca^n$ אזי מתקיים $|w|=2n+1\geq n$ וגם $(a^n)^R=a^n$ ולכן $w \in L$.
יהי פירוק $w=xyz$ כך ש-$|xy|\leq n$ וגם $|y|>0$. אזי מתקיים כי $x=a^m$ ו-$y=a^k$ ו-$z=a^{n-m-k}ca^n$ כאשר $m,k \in \mathbb{N}$ וגם $m+k \leq n$ ו-$k>0$. לכן, הפירוק שלנו הוא בעצם $w=a^ma^ka^{n-m-k}ca^n$.
נבחר $i=0 \in \mathbb{N}$ ואז יתקיים

מתקיים $k>0$ ולכן $n-k<n$ ולכן $(a^{n-k})^R\neq a^n$ ונובע $xy^iz \not\in L$. לכן, $L$ לא ניתנת לניפוח ולא רגולרית כנדרש.
∎

הוכחה: (1)
נבחר $n=1$ תהא מילה $w \in L$ כך ש-$|w|\geq n$. נשים לב שלכל פירוק $w=xyz$ שיקיים $|xy|\leq n=1$ וגם $|y|>0$ יתקיים $|xy|=1$ וגם $x=\epsilon$ וגם $|y|=1$.
נחלק למקרים לפי הגדרת $L$:
כאשר $w \in \left\{ b \right\}^+\circ L_{1}$: מהגדרת השפה, קיים $m \in \mathbb{N}^+$ כך ש-$w=b^ma^p$ עבור $p$ ראשוני כך ש-$m+p\geq n$. נבחר את הפירוק $\begin{cases}x=\epsilon\\y=b\\z=b^{m-1}a^p\end{cases}$ שעונה על $|xy|\leq n$ וגם $|y|>0$ כפי שהסברנו קודם.
יהי $i \in \mathbb{N}$. צ"ל: $xy^iz \in L$.
מתקיים: $xy^iz=b^ib^{m-1}a^p=b^{m-1+i}a^p$. אם $m-1+i>0$ אזי $xy^iz \in \left\{ b \right\}^+\circ L_{1}$ ולכן $xy^iz \in L$ מהגדרת האיחוד.
אחרת, $m-1+i=0$ ואז $xy^iz=a^p$ השייך ל-$\left\{ a \right\}^*$ ולכן שייך ל-$L$ מהגדרת האיחוד. בכל מקרה, $xy^iz \in L$.
כעת נעבור למקרה השני, כאשר $w \in \left\{ a \right\}^*$. מהגדרת השפה, קיים $m \in \mathbb{N}$ טבעי כך ש-$w=a^m$ ו-$m\geq n$. נבחר $\begin{cases}x=\epsilon\\y=a\\z=a^{m-1}\end{cases}$ שעונה על הדרישות $|xy|\leq n$ וגם $|y|>0$ כפי שהסברנו.
יהי $i \in \mathbb{N}$. צ"ל: $xy^iz \in L$.
מתקיים $xy^iz=a^ia^{m-1}=a^{m-1+i}$. בגלל ש-$i \in \mathbb{N}$ ו-$m\geq n=1$ מתקיים $m-1+i\geq 0$ ולכן $xy^iz \in \left\{ a \right\}^*$ ומהגדרת האיחוד $xy^iz \in L$.
לסיכום, ראינו כי $L$ ניתנת לניפוח לפי הגדרה.
∎

הוכחה: (2)
נניח בשלילה כי $L$ רגולרית. על פי הוכחה מההרצאה, מתקיים כי לכל א"ב $\Sigma$ מתקיים כי $\Sigma^*$ היא רגולרית ולכן $\left\{ a \right\}^*$.
מסגירות שפות רגולריות למשלים, מתקיים כי $\overline{\left\{ a \right\}^*}$ רגולרית. מסגירות שפות רגולריות לחיתוך, נובע כי $L \cap \overline{\left\{ a \right\}^*}=\left\{ b \right\}^+\circ L_{1}:=L_{2}$ היא שפה רגולרית. נראה ש-$L_{2}$ לא ניתנת לניפוח, לכן משלילת למת הניפוח $L_{2}$ לא תהא רגולרי בסתירה. ואז נסיק ש-$L$ אינה רגולרית כנדרש.
נראה ש-$L_{2}$ לא ניתנת לניפוח:
יהא $n \in \mathbb{N}^+$. נבחר $w=ba^p$ כך ש-$p\geq n$ ראשוני. אז מתקיים $w \in L_{2}$ וגם $|w|\geq n+1\geq n$.
יהי פירוק $w=xyz$ כך ש-$|xy|\leq n$ וגם $|y|>0$. נחלק למקרים:
אם $x=\epsilon$ אזי $y=ba^m$ עבור $m \in \mathbb{N}$ ואז $z=a^{p-m}$ כך ש-$m+1\leq n$. נבחר $i=0$ ויתקיים $xy^iz=a^{p-m}\not\in L_{2}$ כי מילים ב-$L_{2}$ מתחילות ב-$b$.
אם $x\neq \epsilon$ אזי $\begin{cases}x=ba^m\\y=a^k\\z=a^{p-m-k}\end{cases}$ כך ש-$m,k \in \mathbb{N}$ ו-$k>0$ וגם $1+n+k \leq n$ (כי $|xy|\leq n$). נבחר $i=p+1$ ויתקיים $xy^iz=ba^m(a^k)^ia^{p-m-k}=ba^{p+(i-1)k}=ba^{p(k+1)}$. מתקיים ש-$p$ ראשוני ולכן $p>1$ ו-$k+1>1$ כי $k>0$ ולכן $p(k+1)$ אינו מספר ראשוני. לכן $xy^iz \not\in L_{2}$.
הראנו כי $L_{2}$ לא ניתנת לניפוח, כנדרש.
∎

דרכים להראות כי שפה אינה רגולרית

1. מראים שהשפה לא ניתנת לניפוח ומשלילת למת הניפוח מסיקים שהיא אינה רגולרית.
2. מניחים בשלילה שהשפה רגולרית. מבצעים פעולות סגור עם שפות רגולריות ידועות ומקבלים שפה לא רגולרית, בסתירה להנחת השלילה.