PDA

צפה בגרסה המלאה : הוכחה ששפה אינה רגולרית...



yairy6
08-11-2011, 11:08
יש לי שאלה שנתנו לי ואני לא מצליח לפתור אותה... אני אשמח לעזרה!



נתונה השפה הבאה Lמעל הא"ב { 0,1 }:

השפה מכילה אך ורק את הרצפים במבנה:
0n1k02n כאשר n זוגי, k אי-זוגי , n,k>=0 . ובין הרצפים מפרידה האות 0.

דוגמא למילה בשפה : 00001000000000001110000
רצף שני רצף ראשון

האם השפה הנתונה רגולרית? הוכח !


תודה לכל העוזרים!