מאוד פשוט
ניתן באמת באמצעות למת הניפוח - אבל אני בספק אם זה רלוונטי לגביך כרגע. אם לא, הנה היוריסטיקה להוכחה שאתה צריך: לשפה רגולרית יש אס"ד שמכריע אותה. תניח שקיים אוטומט כזה. ועכשיו בגלל שהאוטומט סופי ויש לך אין סוף מילים (בעולם המילים), קיימות לפחות שתי תחיליות (שונות!!)A1 != A2 שיביאו אותך לאותו מצב של האוטומט. כעת, עבור סיפא כלשהי V שאותו תשרשר לשתי התחיליות, תגיע לאותו מצב של האוטומט אבל A1V שייכת לשפה ואילו A2V לא בשפה. כל מה שאתה צריך לבחור זה A1, A2 ו V מתאימים לצרכים. בהצלחה.
