یک ردیف از قطار با شماره‌های ۱ تا ۱۰ پشت سر هم مطابق شکل زیر قرار دارند. این ردیف را با دنباله‌ی $\langle 1, 2, 3, ..., 10\rangle$ نمایش می‌دهیم. قطار ۱ آخرین قطار است. بین ریل ورودی و ریل خروجی ریلی به نام «پارکینگ» دقیقاً مطابق زیر قرار گرفته است. هر قطار برای آن‌که در ریل خروجی ظاهر شود باید ابتدا به پارکینگ وارد شود. همیشه هم آخرین قطار موجود در پارکینگ دنده عقب به خروجی منتقل می‌شود. با این ترتیب در خروجی یک دنباله از قطارها (به ترتیب از راست به چپ) ظاهر خواهد شد که با $\langle a_1, a_2, ..., a_{10}\rangle$ نشان می‌دهیم و به آن دنباله‌ی «قابل تولید» می‌گوییم. دقت کنید که $a_1$ آخرین قطاری است که خارج می‌شود. چند تا از دنباله‌های زیر قابل تولید هستند؟

• $\langle 10, 9, 8, 7, 4, 6, 3, 2, 1, 5\rangle$
• $\langle 9, 9, 1, 6, 7, 5, 1, 3, 2, 10\rangle$
• $\langle 8, 6, 7, 1, 10, 5, 4, 3, 9, 2\rangle$
• $\langle 10, 9, 8, 1, 7, 6, 5, 3, 2, 4\rangle$

1. ۰
2. ۱
3. ۲
4. ۳
5. ۴

• سوال بعد
• سوال قبل