שפות חסרות הקשר – תכונות סגור

הפוסט הקודם שלי על שפות חסרות הקשר היה כבד יחסית, אז בואו נישאר הפעם במסגרת הדברים הקלילים. אני ממשיך עם ההקבלה שלנו לשפות רגולריות, והגענו לשלב שבו אנחנו מוכיחים כל מני תכונות סגור שונות ומשונות – פעולות שאפשר להפעיל על … להמשיך לקרוא

שקילות אוטומט מחסנית ודקדוק חסר הקשר

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

אוטומט מחסנית

בפוסטים הקודמים על שפות פורמליות הגדרתי את המושג של שפה חסרת הקשר. שפה היא חסרת הקשר אם יוצר אותה דקדוק חסר הקשר. זה מייצג גישה שונה לשפות פורמליות ביחס לזו שבה נקטתי עבור שפות רגולריות – שם הגדרתי את המחלקה … להמשיך לקרוא

אז מה הקשר בין דקדוקים חסרי הקשר ופונקציות יוצרות?

תכירו – מסלולי מוצקין. מסלול מוצקין מאורך $latex n$ הוא מסלול ב-$latex \mathbb{Z}^{2}$ שמתחיל ב-$latex \left(0,0\right)$ ומסתיים ב-$latex \left(n,0\right)$ ומורכב משלושה סוגים אפשריים של צעדים: ימינה, למעלה-ימינה ולמטה-ימינה. כלומר, אנחנו כרגע ב-$latex \left(x,y\right)$ אז אנחנו יכולים לעבור אל $latex \left(x+1,y+\delta\right)$ … להמשיך לקרוא

מבוא לדקדוקים חסרי הקשר

הפוסט על משפט נרוד מהווה לטעמי סיום הולם לנושא של שפות רגולריות, אבל מהנושא הזה יש קפיצה טבעית מאוד אל נושא קרוב ברוחו – שפות חסרות הקשר. בזמן שהכלי העיקרי שבו השתמשנו כדי לתאר שפות רגולריות היה אוטומטים, עבור שפות … להמשיך לקרוא