בוקר טוב לכולם

יש לי כמה שאלות בנושא אוטומטים :
1. למת הניפוח , אני מעוניין לדעת איך מוצאים את הקובע המינימלי ביותר -
לדוגמא עבור המילה *00001 הקבוע זה 5 , כי 4 האפסים הראשונים חייבים להיות בשפה , והחל מהספרה ה-1 הראשונה אני יכול להתחיל לנפח , עבור כל מילה פשוטה יחסית קל למצוא את הקבוע המינימלי ,
אבל אני לא מצליח להבין כשמתחילים להיות ביטוים טיפה יותר "מורכבים" כגון
(*(00) + 11) או *(00+111) , קצת קשה להבין בדיוק איך פועלת ה * משפיעה על קביעת הקבוע ,

אני הרי יכול להסתכל שפועלת ה* אומרת שאני חייב להוסיף לקבוע הניפוח 1 לפחות (עבור אפיסון כי הוא כן בשפה) ועבור כל שאר האיברים הנותרים אני אקצה את Y , אשמח אם משהו יכול לחדד את הנקודה.

2. בשאלות של בניית אוטמטי מכפלה , לדוגמא אם נתונה השפה

קוד:

 L={abc,cde,fpg)  

אז אומרים לי לבנות אוטמט חדש שיקבל את השפה הבאה :

קוד:

L~ = {aabbcc,ccddee,ffppgg}  

ואני צריך לבנות אותה בצורה הפורמלית שלה, כלומר להגדיר מהו הq0 , Q,F וכו'

אשמח לדעת אם למשהו יש תרגילים בנושא,

בתודה רבה יגאל!

_

אני הלוחם של היום והלויס ליין של המחר

לא הבנתי כל כך את השאלה הראשונה.
למת הניפוח היא כלי המשמש להוכחה ששפה נתונה כלשהי אינה רגולרית, למה אתה מתכוון כשאתה אומר למצוא את הקבוע?

לגבי השאלה השניה: כל אות שהופיעה פעם אחת בשפה הראשונה צריכה להופיע פעמיים בשפה השניה, לכן כל מצב q באוטומט שמגיעים אליו עם תו בשפה(ולא עם אפסילון) אתה צריך לפצל לשני מצבים חדשים q1,q2 כך שכל מה שנכנס ל-q יכנס ל-q1 וכל מה שיוצא מ-q יצא מ-q2, ולחבר את q2 עם q1 בחץ עם כל התווים שנכנסים ל-q.
ככה יצרת אוטומט שבו כל תו שהופיע באוטומט הראשון פעם אחת חייב להופיע בשני פעמים.

תודה על התגובה


לגבי השאלה הראשונה , אני מחפש תרגילים שבהם לדוגמא נתונה שפה רגולרית (ביטוי רגולרי או פירוט של שפה) ואז אני צריך למצוא את הקבוע המינימלי N שאיתו אפשר להתחיל לנפח.
כמו שעבור השפה *00001 הקבוע המינימלי הוא 5 , מכיוון שמאחר "יש חובה" ל 4 אפסים ראשונים ואסור ש Y יהיה שווה לאפסילון , Y חייב להיות ל - '1' אחד לפחות.
לכן לי הפירוק :
x = 0000
y = 1
z = כל שאר ה-1 שיכולים להגיע (במידה והם קיימים )

דוגמא נוספת השפה 0*1*0 - כאן קבוע הניפוח הוא 2 , מכיוון שיש חובה על ה0 הימני ביותר להופיע ונקח אותו בתור ה Z , בתור ה -Y נקח את אחד המופעים של *0 או *1 ו את X אפשר לקחת כ אפסילון.


מה ששאלתי אם למישהו יש מאגר שאלות בנושא הזה, של מציאת קבוע ניפוח מינמלי,
וכנ"ל גם לגבי שאלה 2 , החומר יחסית מובן , אבל חסרים שאלות לתרגול.


בתודה!

_

אני הלוחם של היום והלויס ליין של המחר

אין איזו שיטה אונברסלית..
הכל עניין של תרגול.

בכדי להשתמש בלמת הניפוח לא צריך לדעת את הN המנימלי! צריך להניח בשלילה שהוא קיים! ואז להגיע לסתירה.

הנה יש פה כמה תרגלים+פתרונות
http://www.cs.bgu.ac.il/~auto111/As...ts/Assignment_3

הבהרה:
בלמת הניפוח משתמשים(כמו שאמר הבחור מעלי) רק כדי לסתור רגולריות של שפה, שכן המשפט הוא לא אם"ם, כלומר יש שפות שעומדות בתנאי למת הניפוח, אבל אינם רגולריות.
בניגוד לכך כל שפה רגולרית בהכרח מקיימת את למת הניפוח.

אם אתה משום מה מתעקש ממש למצוא את הN המובטח מלמת הניפוח, הדרך לעשות זאת הוא למצוא את מחלקות השקלות של השפה, מספר מחלקות השקלות שווה לN הנ"ל=למספר מצבים באוטומט דטרמניסטי מינימלי המכיר שפה זו.

ציטוט:

כמו שעבור השפה *00001 הקבוע המינימלי הוא 5 , מכיוון שמאחר "יש חובה" ל 4 אפסים ראשונים ואסור ש Y יהיה שווה לאפסילון , Y חייב להיות ל - '1' אחד לפחות. לכן לי הפירוק : x = 0000 y = 1 z = כל שאר ה-1 שיכולים להגיע (במידה והם קיימים ) דוגמא נוספת השפה 0*1*0 - כאן קבוע הניפוח הוא 2 , מכיוון שיש חובה על ה0 הימני ביותר להופיע ונקח אותו בתור ה Z , בתור ה -Y נקח את אחד המופעים של *0 או *1 ו את X אפשר לקחת כ אפסילון.

בשני הדוגמאות שנתת, יש טעות בידך!(הN שנסית לחשב לא נכון בעליל)! איך אני רואה זאת מיידית? N=למספר מצבים באוטומט דטרמניסטי מינימלי המכיר את השפה, נסה לחשוב על אוטומט דטרמניסטי בעל 5 מצבים המכיר בשפה א, ובאוטומט 2 מצבים המכיר את שפה ב..

אני חושב שיש לך בעיות הבנה בכל הקשור ללמת הניפוח, קרא את ההסבר שלי אודות הלמה, קראה סיכומים באינטרנט.
http://he.wikipedia.org/wiki/%D7%9C...%99%D7%95%D7%AA

ואז נסה לתרגל.

למצוא את הקבוע המנימלי===>שקול למציאת מספר מחלקות השקלות(שזהו כמובן מספר סופי, אם השפה רגולירית)