סמרטר - מאגר עבודות אקדמיות
  • פרסם עבודה
  • התחבר

ממן 13 אוטומטים ושפות פורמליות

שנת הגשה 2020, מילים
ILS 80.00 – קנה עכשיו קנה עכשיו התווסף לסל הקניות

מטלת מחה (ממ”ן) 13
הקורס: 20440 – אוטומטים ושפות פורמליות
חומר הלימוד למטלה: יחידה 4
מספר השאלות: 5 משקל המטלה: 2 קודות
סמסטר: ב2020 מועד אחרון להגשה: 2020.4.28
י.ק
אא שים לב:
מלא בדייקות את הטופס המלווה לממ”ן בהתאם לדוגמה שלפי המטלות.
העתק את מספר הקורס ומספר המטלה הרשומים לעיל.

הערה: אחת הדרכים להוכיח ששפה היא רגולרית, היא ביית אוטומט (או הצגת ביטוי רגולרי).
במקרה שבחרת בדרך זו איך דרש להוכיח שאכן השפה שהאוטומט מקבל (או השפה
שהביטוי יוצר) שווה לשפה המבוקשת.
ואולם, הגדר את האוטומט במדויק, באופן פורמלי, וכן הסבר מדוע הבייה מתאימה
לשפה המבוקשת.
(15%) 1 שאלה
ם”אם דרוםפלי קראת {a,b,c} מעל w מילה R . w  w
הוכח באמצעות למת היפוח ששפת הפלידרומים מעל {c,b,a {איה רגולרית.
(36%) 2 שאלה
הוכח באמצעות תכוות סגירות שהשפות הבאות אין רגולריות:
{a,b} מעל , L1  {bwbwb | w a*} .א
{ | ( )*, ( )*, # ( ) # ( )} .ב 2 L xey x a b y c d x y      a  c {a,b,c,d,e} מעל,
(14%) 3 שאלה
תהי L שפה רגולרית מעל  .יהי A אוטומט סופי דטרמייסטי המקבל את L .
בה באמצעות A אוטומט סופי המקבל את שפת כל המילים שב- L המקיימות: לכל רישא ממש
שלהן, הרישא איה ב- L .
הערה: u היא רישא ממש של v אם”ם u היא רישא של v ,ו- v  u .
(20%) 4 שאלה
תהי L שפה רגולרית מעל  .הוכח שגם השפה הבאה רגולרית:

8

; 112 2 1 … { * | w ww w    nnn Lˆ  w
1  n ;
;   :1  i  n 1,i לכל  i
; * :1  i  n ,i לכל wi 
L }  1
 2 … n n1 
(15%) 5 שאלה
L היא שפה רגולרית. NP היא שפת כל המילים השייכות ל-L שעבורן לא קיים אף פירוק uvw=z ,
uv w L i  0 שלכל כך | v | 0 שעבורו i . 
הוכח או הפרך את הטעה ש-NP רגולרית.

ILS 80.00 – קנה עכשיו קנה עכשיו התווסף לסל הקניות
מילות מפתח 13, אוטומטים, ושפות פורמליות, ממן
מקצוע/ות ממ"נים
מספר מילים
מספר מקורות 1
שנת הגשה 2020

מקצועות

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

מאגר עבודות אקדמיות

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