עריסטו
Active member
חידת מחרוזת
מתחילים מהמחרוזת הבאה: L בכל צעד מותר לעשות אחת משלושת הפעולות הבאות: 1. למחוק פעם אחת את האות L מהמחרוזת. 2. להוסיף את האות B אחרי האות L. 3. למחוק את האות B ובמקומה להכניס (L). מותר לעצור רק כאשר המחרוזת אינה מכילה אף B או L. דוגמה: L (מצב התחלתי) LB (בוצעה פעולה 2) LBB (בוצעה פעולה 2) BB (בוצעה פעולה 1) zzz B(L) zzz (בוצעה פעולה 3 - תתעלמו מה-zzz) zzz B() zzz (בוצעה פעולה 1) zzz (L)() zzz (בוצעה פעולה 3) zzz ()() zzz (בוצעה פעולה 1) כעת מותר לעצור כי אין B או L. התוצאה שקיבלנו היא המחרוזת ()(). שאלה: מה יכולות להיות המחרוזות המתקבלות בסיום התהליך? לאילו מחרוזות ניתן להגיע?
מתחילים מהמחרוזת הבאה: L בכל צעד מותר לעשות אחת משלושת הפעולות הבאות: 1. למחוק פעם אחת את האות L מהמחרוזת. 2. להוסיף את האות B אחרי האות L. 3. למחוק את האות B ובמקומה להכניס (L). מותר לעצור רק כאשר המחרוזת אינה מכילה אף B או L. דוגמה: L (מצב התחלתי) LB (בוצעה פעולה 2) LBB (בוצעה פעולה 2) BB (בוצעה פעולה 1) zzz B(L) zzz (בוצעה פעולה 3 - תתעלמו מה-zzz) zzz B() zzz (בוצעה פעולה 1) zzz (L)() zzz (בוצעה פעולה 3) zzz ()() zzz (בוצעה פעולה 1) כעת מותר לעצור כי אין B או L. התוצאה שקיבלנו היא המחרוזת ()(). שאלה: מה יכולות להיות המחרוזות המתקבלות בסיום התהליך? לאילו מחרוזות ניתן להגיע?