מאגר שאלות ותשובות להוראת מודלים חישוביים:

תכונות סגירות של שפות חופשיות הקשר

דגנית מורן

 

שאלה 1

תהי L השפה הבאה מעל הא"ב: 0} L={anb2nan ï n >

תלמיד מסויים הציע להוכיח כי L חופשית הקשר בדרך הבאה:

הוא הציג את L כך:  L1=L1 × L2 כך ש:

, L1= {anbn | n>0}            0} L2={bnan ï n >

ידוע כי L1 ו- L2 חופשיות הקשר, ומסגירות משפחת השפות חופשיות ההקשר לשרשור גם L רגולרית.

האם ההוכחה נכונה? הצדק את טענתך.

 

פתרון

ההוכחה שגויה משום ש: L¹L1×L2.

למשל, המילה aabb שייכת ל-L1  והמילה bbbaaa שייכת ל-L2 ולכן שרשורן, המילה aabbbbbaaa, שייכת לשפה L1×L2 .

אבל המילה aabbbbbaaa לא שייכת לשפה L.

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים