נתונה השפה הבאה:
L=\left\{ w\in\{a,b,c\}^{*}\,:\,\#_{b}(w)=\#_{c}(w)\vee\#_{b}(w)\geq\#_{a}(w)\right\}
האם השפות הבאה מקיימת את למת הניפוח?
האם היא שפה רגולרית?
כיצד עלי לבדוק אם השפה L מקיימת את למת הניפוח?
תודה רבה על העזרה.
נוכיח כי השפה L אינה מקיימת את למת הניפוח. נניח בשלילה כי השפה L רגולרית. יהי n\geq1 כלשהו. נתבונן במילה z=b^{n}a^{n}c^{n}. מספר ה-b-ים במילה z שווה למספר ה-c-ים ולכן z\in L. כמו כן, מתקיים |z|=3n\geq n. לכן ע"פ למת הניפוח קיים פירוק z=uvw כלשהו של z כך שמתקיים |uv|\leq n וגם |v|\geq1. נשים לב כי n האותיות הראשונות במילה z הן כולן b. לכן קיימים t,s\leq n כך שמתקיים u=b^{s}, v=b^{t} ו-t\geq1. כלומר uv=b^{s}b^{t} ולכן w=b^{n-s-t}a^{n}c^{t}. ע"פ תנאי שלוש של למת הניפוח נובע כי המילה uv^{i}w שייכת לשפה L לכל 0\leq i. בפרט זה נכון עובר i=0, כלומר מתקיים uvw\in L. נשים לב כי מתקיים:
uv^{0}w=uw=b^{s}b^{n-s-t}a^{n}c^{t}=b^{n-t}a^{n}c^{t}
כמו כן, נשים לב כי במילה b^{n-t}a^{n}c^{t}, מספר ה-b-ים הוא n-t ומספר ה-c-ים הוא t. מאחר ומתקיים t\geq1 נובע n-t\neq t ולכן התנאי \#_{b}(uv^{0}w)=\#_{c}(uv^{0}w) לא מתקיים. בנוסף לכך, מספר ה-a-ים הוא n ומספר ה-b-ים הוא n-t. מאחר ומתקיים t\geq1 נובע n-t<n ולכן התנאי \#_{b}(uv^{0}w)\geq\#_{a}(uv^{0}w) לא מתקיים. לפיכך נובע כי uv^{0}w\not\in L, סתירה. לכן השפה L אינה רגולרית והיא אינה מקיימת את למת הניפוח.