PDA

צפה בגרסה המלאה : מודלים חישוביים- שפה רגולרית



roneno
21-11-2010, 20:31
האם השפה {מספר האותיות a בw קטן ממספר האותיות b בw | w} מעל הא"ב {a,b} היא רגולרית?

לפי מה שהתאמצתי להבין, אס"ד לא מסוגל לספור כמה אותיות a או b יש במילה, אז הסבכתי כאן...

netaneld122
21-11-2010, 22:08
היא לא רגולרית.

המשלים של השפה הוא "מספר האותיות a בw גדול-או-שווה למספר האותיות b", וכן ידוע שלא ניתן לדעת מתי a שווה ל b, ובגלל שיש סגירות תחת המשלים אז השפה לא רגולרית.
אבל זה דורש הוכחה (אולי אפשר גם להוכיח בצורה המקורית של התרגיל, אבל לדעתי יותר קל עם המשלים).

roneno
22-11-2010, 07:35
כלומר צורת ההוכחה היא כתיבת הטענה עם המשלים ותכונת הסגירות, ואז להוכיח שהשפה של a שווה לb היא לא רגולרית?

(התשובה לשאלה שלי משתנה אם אני מוסיף לדוג' שההפרש בין a לb הוא פחות מ3?)

netaneld122
22-11-2010, 11:43
אותנו לימדו ממש להוכיח את זה בשלבים, בהתחלה מוכיחים בשלילה שלא קיים מצב סופי של מצבים המקבלים את השפה הנ"ל... ומכך נובע שהשפה לא רגולרית.

אני לא זוכר את הצורה הפורמלית של ההוכחה, אבל בהחלט הייתם אמורים ללמוד את זה בכיתה :)