חישוביות

[carlos22]

חישוביות

Ln = {ww | w is in {a,b}^n} zz בסעיף א' הוכחתי שכל אוטומט לא דטרמיניסטי המקבל את Ln חיב להכיל לפחות 2 בחזקת n מצבים בסעיף ב' צריך לתאר אוטומט עם Ozz מצבים המקבל את המשלים של Ln. אם אני מצליח לצייר את סעיף ב' זה לא יוצר סתירה ? כי אם יש אוטומט עם Ozz מצבים שמקבל את המשלים של השפה אפשר פושט להפוך את המצבים המקבלים ללא מקבלים ולהפך ואז מה שהתקבל קודם לא מתקבל ומה שלא התקבל כן מתקבל.. או שזה רק עבור אוטומטים דטרמיניסטיים ? אני לא ממש מצליח למצוא כיוון כיצד ניתן לצייר אוטומט כנדרש לא אקספוננציאלי ..

 

[עדין ר]

רמז

מילה s1s2...sk היא בשפה המשלימה של Ln אם"ם מתקיים לפחות אחד התנאים הבאים: 1. k שונה מ-2n (כלומר אורך המילה אינו 2n). 2. קיים i<=n כך ש si שונה מ-s(i+n) כלומר החצי הראשון של המילה שונה באות ה-i מהחצי השני. בנה אוטומט שינחש איזה מהתנאים מתקיימים (ואם זה תנאי 2, עבור איזה i). הפיכת המצבים המקבלים ללא מקבלים ולהפך באוטומט לא דטרמיניסטי לא הופכת את השפה שהאוטומט מקבל. אוטומט לא דטרמיניסטי מקבל מילה אם קיימת ריצה מקבלת על המילה, אבל יכול להיות שיש גם ריצות שלא מקבלות. לכן, אם תהפוך את המצבים, עדיין יכולות להיות ריצות מקבלות על אותה מילה (כלומר האוטומט עדיין יקבל את אותה המילה).