שאלה במודלים
שאלה במודלים‏ moti‏ (אוניברסיטת ת"א)‏ 21.08.2006 12:43
נגדיר את הפעולה הבאה על שפה:

\normalsize A(L) = \lbrace zx^R y \in \Sigma ^* : xyz \in L\rbrace

א. עבור כל שפה ח"ה L , \normalsize A(L)היא שפה ח"ה.

ב. קיימת שפה ח"ה L עבורה \normalsize A(L) היא שפה ח"ה, וקיימת שפה ח"ה K עבורה \normalsize A(K) היא שפה לא ח"ה.

ג. עבור כל שפה ח"ה L, \normalsize A(L)היא שפה לא ח"ה.

תודה
ב'‏ erancho‏ (אוניברסיטת ת"א)‏ 21.08.2006 15:05
קיימת שפה עבורה היא שפה לא חה.

לדוגמא

\normalsize L={a^nb^nc^md^m}

אם תפעיל את הפעולה, ותחתוך עם השפה הרגולרית

\normalsize L(a*c*b*d*)

תקבל את השפה

\normalsize L' = {a^nc^mb^nd^m}

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

ערן.
שתי שאלות נוספות במודלים.‏ גיל‏ (אוניברסיטת ת"א)‏ 22.08.2006 21:32
1. תהיינה L1 ו L2 שפות כלשהן תהא \normalsize L3=L1\cup L3. איזו מהטענות הבאות נכונה:

טענה 1: אם L3 וL1 רגולריות, אזי L2 בהכרח רגולרית.
טענה 2: אם L3 רגולרית וL1 סופית, אזי L2 בהכרח סופית.


א. טענה 1 נכונה וטענה 2 לא.
ב. טענה 2 נכונה וטענה 1 לא.
ג. שתי הטענות נכונות.
ד. שתי הטענות אינן נכונות.


התשובה הנכונה היא ב', אבל אני לא מבין מדוע.





2. נגדיר את הפעולה Drop1 על שפה L מעל א"ב {0,1} כך:

\normalsize Drop1(L)=\lbrace xy |x,y \in \lbrace0,1\rbrace, \exist a \in \lbrace 0,1\rbrace ,|y|=|x|^2, xay \in L)

איזו מהטענות הבאות נכונה:

טענה 1: משפחת השפות הרגולריות סגורה תחת הפעולה Drop1.
טענה 2: משפחת השפות חסרות ההקשר סגורה תחת הפעלה Drop1.

א. טענה 1 נכונה וטענה 2 לא.
ב. טענה 2 נכונה וטענה 1 לא.
ג. שתי הטענות נכונות.
ד. שתי הטענות אינן נכונות.

התשובה היא ד', אבל אני לא מצליח למצוא דוגמא נגדית.


תודה מראש.
מוזר. הlatex לא יצא טוב. נסיון שני:‏ גיל‏ (אוניברסיטת ת"א)‏ 22.08.2006 21:35
1. תהיינה L1 ו L2 שפות כלשהן תהא \normalsize L3=L1\cup L3. איזו מהטענות הבאות נכונה:

טענה 1: אם L3 וL1 רגולריות, אזי L2 בהכרח רגולרית.
טענה 2: אם L3 רגולרית וL1 סופית, אזי L2 בהכרח סופית.


א. טענה 1 נכונה וטענה 2 לא.
ב. טענה 2 נכונה וטענה 1 לא.
ג. שתי הטענות נכונות.
ד. שתי הטענות אינן נכונות.


התשובה הנכונה היא ב', אבל אני לא מבין מדוע.





2. נגדיר את הפעולה Drop1 על שפה L מעל א"ב {0,1} כך:

\normalsize Drop1(L)=\lbrace xy |x,y \in \lbrace0,1\rbrace, \exist a \in \lbrace 0,1\rbrace ,|y|=|x|^2, xay \in L)

איזו מהטענות הבאות נכונה:

טענה 1: משפחת השפות הרגולריות סגורה תחת הפעולה Drop1.
טענה 2: משפחת השפות חסרות ההקשר סגורה תחת הפעלה Drop1.

א. טענה 1 נכונה וטענה 2 לא.
ב. טענה 2 נכונה וטענה 1 לא.
ג. שתי הטענות נכונות.
ד. שתי הטענות אינן נכונות.

התשובה היא ד', אבל אני לא מצליח למצוא דוגמא נגדית.


תודה מראש.
ננסה בלי latex...‏ גיל‏ (אוניברסיטת ת"א)‏ 22.08.2006 21:39
1. תהיינה L1 ו L2 שפות כלשהן תהא L3=L1∪L2. איזו מהטענות הבאות נכונה:

טענה 1: אם L3 וL1 רגולריות, אזי L2 בהכרח רגולרית.
טענה 2: אם L3 רגולרית וL1 סופית, אזי L2 בהכרח סופית.


א. טענה 1 נכונה וטענה 2 לא.
ב. טענה 2 נכונה וטענה 1 לא.
ג. שתי הטענות נכונות.
ד. שתי הטענות אינן נכונות.


התשובה הנכונה היא ב', אבל אני לא מבין מדוע.





2. נגדיר את הפעולה Drop1 על שפה L מעל א"ב {0,1} כך:

Drop1(L)={xy | x,y ∈{0,1}*, ∃a∈{0,1}, |y|=|x|2 , xay∈L}zzz


איזו מהטענות הבאות נכונה:

טענה 1: משפחת השפות הרגולריות סגורה תחת הפעולה Drop1.
טענה 2: משפחת השפות חסרות ההקשר סגורה תחת הפעלה Drop1.

א. טענה 1 נכונה וטענה 2 לא.
ב. טענה 2 נכונה וטענה 1 לא.
ג. שתי הטענות נכונות.
ד. שתי הטענות אינן נכונות.

התשובה היא ד', אבל אני לא מצליח למצוא דוגמא נגדית.


תודה מראש.

כל ההודעות בערוץ