אם Lרגולרית אז L' רגולרית

אם L ח"ה אז L' ח"ה

אם אז

אם L לא רגולרית אז L' לא רגולרית

2.יהיו (מספרים טבעיים). נגדיר ו- .יהיו M אס"ד עבור עם מספר מצבים מינימלי.אזי מספר המצבים ב-M הוא :

3.יהיו ו- השפות מהשאלה הקודמת (כאשר n לא מחלק את m ולהפך). יהי M אס"ד עבור עם מספר מצבים מינימלי. אזי מספר המצבים ב-M הוא :

4. דקדוק בצורת "טאואר-אייר" הוא דקדוק שכל הפקה בו היא מהצורה : או כאשר ו- .

G בצורת "טאואר-אייר" גורר רגולרית

L רגולרית גורר קיים דקדוק G בצורת "טאואר-אייר" כך ש-

לשפה קיים דקדוק "טאואר-אייר" היוצר אותה

G בצורת "טאואר-אייר" גורר קיים דקדוק G' בצורה נורמלית של חומסקי כך ש-

5.נגדר:

f-היא האות הראשונה ב-x

l-היא האות האחרונה ב-x

תהי מספר המצבים באס"ד המינימלי עבור L הוא:

6.ניתן להוכיח ששפה אינסופית נתונה היא ח"ה על ידי שימוש ב-:

7.תהי

8.תהי L שפה אינסופית ויהי M אס"ד בעל 5 מצבים כך ש-

בהכרח קיימות לפחות 6 מילים באורך 50

בהכרח קיימות לפחות 10 מילים באורך 50

הקבוצה הפורשת המינימלית של L מכילה לפחות 5 מילים

הקבוצה הפורשת המינימלית של L מכילה לכל היותר 5 מילים

9. יהיו (מספרים טבעיים), .

נגדיר

10.יהי G דקדוק בצורה נורמלית של חומסקי. תהי , ויהי T עץ גזירה של w. מספר הקדקודים הפנימיים (כולל השורש, לא כולל העלים) ב-T הוא: