KonkurStudy
همه کارت‌ها

Every context-free language over a unary alphabet is regular (Parikh)

Over a one-letter alphabet the language hierarchy collapses: every context-free L over a single symbol is already regular. This follows from Parikh's theorem (CFL Parikh images are semilinear, and over a unary alphabet the Parikh image IS the language, so the set of lengths is eventually periodic = regular). It does NOT say arbitrary subsets of a^* are regular.

کارت قضیه کنکور ارشد علوم کامپیوتر