רשימת משפטים

טענה 1.1

השפה לא רגולרית

משפט 1.2

השפה L היא רגולרית, אם ורק אם קיים אסל"ד M כך השפה L היא רגולרית , אם ורק אם היא מתקבלת ע"י אוטומט דטרמיניסטי, ולכן מספיק להראות דטרמיניסטי, אם ורק אם לא דטרמיניסטי.

משפט 1.4

תהיינה L₁ ו-L₂ שפות רגולריות. אזי, השפה רגולרית.

משפט 1.5

תהי L שפה רגולרית. אזי, L^c היא שפה רגולרית.

משפט 1.6

תהיינה L₁ ו-L₂ שפות רגולריות. אזי, השפה היא רגולרית.

משפט 1.7

השפה הריקה היא רגולרית.

משפט 1.8

תהי . אזי, השפה היא רגולרית.

משפט 1.9

תהי L שפה סופית. אזי, השפה L היא רגולרית.

משפט 1.10

תהיינה L₁ ו-L₂ שפות רגולריות. אזי, השפה היא שפה רגולרית.

משפט 1.11

תהי L שפה רגולרית. אזי, השפה היא רגולרית.

משפט 1.12 (Kleene)

השפה L היא רגולרית אם ורק אם ניתן לבנות אותה מה-א"ב ע"י .

משפט 1.13 (למת הניפוח)

יהי M אוטומט סופי דטרמיניסטי בעל n מצבים, ותהי כך ש- . אזי, קיים ל-x פירוק כך שמתקיים:
א. .
ב. .
ג. לכל .

משפט 1.14

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

משפט 1.15

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

משפט 1.16

יהיו . אם , אז .

משפט 1.17 (Myheel-Nerode)

השפה L היא רגולרית אם ורק אם קיימת קבוצה פורשת ל-L.

משפט 2.1

השפה L היא רגולרית אם ורק אם קיים דקדוק רגולרי כך ש-

משפט 3.1

לכל דקדוק חסר הקשר קיים דקדוק חסר הקשר מסתעף ,כך ש-

משפט 3.2

לכל דקדוק חסר הקשר קיים דקדוק בצורת חומסקי כך ש-

משפט 3.3

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

משפט 3.4 (משפט בר-הילל)

יהי דקדוק בצורת חומסקי בעל בדיוק n משתנים
תהי x מילה ב- כך ש-

אזי ניתן לפרק את x ל- כך ש-

(1) כאשר לפחות אחד מהם לא מילה ריקה
(2)
(3) לכל

משפט 3.5

יהי דקדוק חומסקי בעל n משתנים. אזי, אינה ריקה אם ורק אם קיימת כך ש-.

משפט 3.6

יהי דקדוק חומסקי בעל n משתנים. אזי, אינסופית אם ורק אם קיימת כך ש-.

משפט 3.7

תהיינה L₁ ו-L₂ שפות חסרות הקשר. אזי, השפה היא שפה חסרת הקשר.

טענה 3.8

קיימות שפות חסרות הקשר L₁ ו-L₂ כך ש- אינה חסרת הקשר.

משפט 3.9

קיימת שפה חסרת הקשר L כך ש- L^c אינה חסרת הקשר.

משפט 3.10

תהי L שפה חסרת הקשר, ותהי R שפה רגולרית. אזי, השפה היא חסרת הקשר.

משפט 3.11

שפה מעל א"ב של אות אחת שאינה רגולרית אינה ח"ה.

משפט עזר 1

תהי שפה חסרת הקשר, ותהי . אזי, היא שפה חסרת הקשר.

משפט עזר 2

לכל A ולכל n השפה היא חסרת הקשר.

משפט עזר 3

.

משפט 3.12 (חומסקי-שורצנברגר)

יהי דקדוק בצורת חומסקי בעל n הפקות מהצורה . אזי, קיימת שפה רגולרית R כך ש-.

משפט 3.13

השפה L היא חסרת הקשר אם ורק אם קיימת שפה רגולרית R כך ש-.

משפט 3.14

יהי דקדוק בצורת חומסקי, ויהי המבחין של . אזי, קיים אוטומט מחסנית דטרמיניסטי M כך ש-.

משפט 3.15

יהי דקדוק בצורת חומסקי. אזי, קיים אוטומט מחסנית לא דטרמיניסטי *M כך ש-.

משפט 3.16

לכל אוטומט מחסנית M קיים אוטמט מחסנית אטומי M' כך ש-.

משפט 4.1 (משפט Landweber-Kuroda )

השפה L היא תלוית קשר אם ורק אם קיים אוטומט חסום לינארית לא דטרמיניסטי M כך ש-

.איתן 2002. כל הזכויות שמורות למערכת המידע איתן©