פתרון חלקי.
קודם כל אתה צריך לדעת שהבעיה הבאה כריעה: קלט: דקדוק חסר הקשר G. שאלה: האם L(G)zzz סופית. הבעיה כריעה כי L(G) zz סופית אם ורק אם קיימת מילה w ב L(G)zzz כאשר האורך של w הוא בין n ל2n (כולל n ו2n) כאשר n הוא הקבוע מלמת הניפוח. לכן אפשר פשוט לבדוק עבור כל מילה שאורכה בין n ל2n (כולל n ו2n) אם היא ב L(G1)zz על ידי הרצה של האוטומט מחסנית המתאים לG1 (ואין בעיה עם זה כי PDA תמיד עוצר) על w. כעת אם L(G1) zzz אינסופית או L(G2)zzz אינסופית אז התשובה היא לא. אחרת, הן סופיות ואפשר איכשהו ליצור רשימה של המילים בכל אחת מהן ואז אפשר לדעת כמה מילים יש באיחוד. הבעיה היא שאני לא זוכר איך אפשר ליצור רשימה של כל המילים בL(G1)zzz גם אם נתון שהיא סופית. מישהו יכול לעזור?
