אוטומטים ושפות פורמליות/תכונות של שפות רגולריות
כל אוטומט סופי מקבל שפה מסויימת. אם נביט בכל האוטומטים הסופיים שקיימים, כל אחד מהם מגדיר שפה (אולי זהה לשפה שאוטומט אחר מקבל). שפה שמתקבלת על-ידי אוטומט סופי נקראת שפה רגולרית, ובהתאמה אוסף כל השפות המתקבלות על-ידי אוטמט סופי כלשהו נקראת מחלקת השפות הרגולריות או קבוצת השפות הרגולריות. כפי שראינו, אוטומט לא-דטרמיניסטי שקול לאוטומט סופי דטרמיניסטי, לכן, אוסף כל השפות המתקבלות על ידי אוטומט סופי לא-דטרמיניסטי כלשהו הינה בדיוק קבוצת השפות הרגולריות. בהמשך נראה אפיון נוסף לשפות אלו בעזרת ביטויים רגולריים.
עתה כשאנחנו יודעים מהי שפה רגולרית (שפה שקיים עבורה אוטומט סופי, שמקבל אותה), נרצה לחקור את התכונות שלה.
תכונה ראשונה מעניינת, היא תכונת הסגירות. כלומר, אם אנחנו לוקחים שפות מהמשפחה הרגולרים ומפעילים עליהן פעולות שונות, האם התוצאה עדיין רגולרית? נראה כי תכונת הסגירות מתקיימת עבור פעולות רבות כגון חיתוך, איחוד, כוכב והיפוך לאחור.
תכונה שניה של שפות רגולריות (אינסופיות) נוגעת למבנה המילים בשפה. נוכיח למה המראה כי כלל המילים בשפה רגולרית אינסופית בעלות מבנה משותף - בכל מילה ארוכה דיה, קיימת תת-מחרוזת שחוזרת על עצמה שוב ושוב. למה זו ידועה בשם למת הניפוח של שפות רגולריות.
בפרק זה נוכיח תכונות אלו.
| הפרק הקודם: אוטומט סופי לא דטרמיניסטי |
תכונות של שפות רגולריות | הפרק הבא: סגירות תחת פעולות שונות |