PDA

צפה בגרסה המלאה : [דיון] הוכחה שהפה אינה רגולרית



elixvx
07-11-2011, 19:12
יש לי שאלה, איך אני מוכיח ששפה כלשהי אינה רגולרית?.
על מנת להוכיח שהיא רגולרית אני צריך להוכיח שהיא סופית וניתן לבנות לה אס"ד.
אבל איך אני מוכיח שהשפה אינה רגולרית?.
נגיד השפה:
a^n b^n כשאר n>0
זוהי שפה אינסופית ולא ניתן לבנות לה אס"ד אבל איך אני "בודק" את זה כביכול?.

(כשיהיו לי שפות יותר מורכבות שקשה לקבוע סתם ככה אם הן רגולריות, נגיד עם מספר תנאים וכו')

תודה (: