אתה צודק במאה אחוז: ההגדרה לרקורסיה שנתתי לא מבחינה בין שפות רגולריות לשפות חסרות הקשר. האמת היא שרוב המאמרים שמתקשרים בצורה זו או אחרת לנושא הזרזירים (ומחקרים שקדמו לכך) לא נותנים הגדרה ברורה, ואיכשהו מניחים שכולנו יודעים מה סוג הרקורסיה שבאמת מעניין אותנו. לפעמים יש בהקשר הזה התייחסות לרקורסיה מסוג center embedding, כלומר למבנים מהסוג:
X -> α X β
כש-α ו-β הם מחרוזות לא ריקות.
מה שמשעשע בהקשר הזה היא העובדה הידועה שלמרות ששפות טבעיות מאפשרות, מבחינת הדקדוק שלהן, center embedding, זה מוביל די מהר לקשיי עיבוד. למשל:
1. הילד בכה.
2. הילד שהכלב נשך בכה.
3. הילד שהכלב שהאיש ליטף נשך בכה.
המשפט האחרון הוא אולי דקדוקי, אבל קשה מאד לעיבוד. ודווקא על center embedding מתנהל כל הדיון. (ומצד שני, הדוגמאות האלה הן אולי לא בדיוק סוג הרקורסיה שניסחתי למעלה- אבל אני כבר מתחיל לסטות מהנושא קצת יותר מדי).

גבי, לגבי הטענה ששפה שכוללת בתוכה אפשרות לרקורסיה היא לא רגולרית, מה בדבר:
S –> A | epsilon
A –> aA | epsilon

זוהי שפה הכוללת אפשרות לרקורסיה אבל היא עדיין רגולרית (מיוצגת על ידי הביטוי הרגולרי a*‎).

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