אוטומטים ושפות פורמליות 1 – אוניברסיטת אריאל

ספטמבר 23, 2025

שם שיעור: אוטומטים ושפות פורמליות 1

מספר שיעור: 7029010

סמסטר: א

שעות שבועיות: 1.5

נקודות זיכוי: 2.5

דרישות קדם

מבנים דיסקרטיים למדעי המחשב בציון 60

וגם

תורת המספרים האלגוריתמית בציון 60

וגם

לוגיקה ותורת הקבוצות בציון 60

שם הקורס: אוטומטים ושפות פורמליות 1

שם הפקולטה: הפקולטה למדעי הטבע

שם המחלקה: המחלקה למדעי המחשב

מספר הקורס: 7029010

מתכונת הקורס: הרצאה + תרגיל

שנת לימודים: ב סמסטר: א היקף שעות: 3 נקודות זכות: 2.5

מטרות הקורס (מטרות על / מטרות ספציפיות):

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

תוכן הקורס:

הגדרת המושג שפות פורמליות, הצגה של משפחות של שפות פורמליות. הגדרת מודלים מתמטייים של מכונות חישוב בסיסיות והשוואת כוח החישוב שלהן.

מהלך השיעורים:

תכנית הוראה מפורטת לכל השיעורים:

יחידת שיעור	נושא השיעור	הערות
	מבוא: מחרוזות, אלף-בית, שפות, גרפים.
	פעולות על שפות.
	אוטומטים סופיים דטרמיניסטיים.
	שפות רגולריות ותכונות סגירות של שפות רגולריות.
	אוטומטים סופיים לא דטרמיניסטיים.
	שקילות של אוטומטים דטרמיניסטיים ולא דטרמיניסטיים.
	אוטומטים סופיים עם מסעי ε, סגור ε.
	שקילות של אוטומטים עם מסעי ε ואוטומטים לא דטרמיניסטיים.
	ביטויים רגולריים, שקילות בין ביטויים רגולריים ושפות של אוטומט.
	למת הניפוח לשפות רגולריות
	תכונות סגירות נוספות של שפות רגולריות.
	בעיות הכרעה לאוטומטים סופיים
	אפיון אלגברי של השפות הרגולריות – מבוא

ג. חובות הקורס:

דרישות קדם: לוגיקה ותורת הקבוצות, מבנים דיסקרטיים למדעי המחשב, תורת המספרים האלגוריתמית

חובות / דרישות / מטלות:

מרכיבי הציון הסופי (ציון מספרי / ציון עובר): 60 ציון עובר (חובה לעבור את המבחן הסופי בציון 60 לפחות)

מטלות הקורס 10% תרגילי בית, מגן 90% מבחן סופי.

ד. ביבליוגרפיה: (חובה/רשות)- מסודרת לפי נושאי הקורס

E. Hopcroft, R. Motwani, and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison Wesley, 2001

אוטומטים ושפות פורמאליות, האוניברסיטה הפתוחה, 1991.