1. (a) Ырас, ар бир кадимки тил контекстсиз болгондуктан, ар бир контекстсиз тилди чечүүгө болот жана ар бир чечүүчү тил Тьюринг тарабынан таанылат.
Эмне үчүн контекстсиз тилдер чечилет?
Чечилгис көйгөйдүн берилген киргизүүгө жоопту аныктоочу алгоритми жок Контекстсиз тилдердин бүдөмүктүүлүгү: Контекстсиз тилди эске алганда, Тьюринг машинасы жок ар дайым чектүү убакытта токтоп, тил түшүнүксүзбү же жокпу деп жооп бериңиз.
Контекстсиз тилдин ички жыйындысы чечилеби?
2 Жооптор. Σ контекстсиз (чындыгында, бул кадимки) жана анын көптөгөн ички топтомдору бар. Эгерде L чексиз көлөмдөгү контекстсиз тил болсо, анда L нин чечүүчү J бөлүмдөрү бар, ал эми кээ бирлери чечилбейт. Мисалы, бош топтомду чечүүгө болот.
CFL чечеби?
CFL: Бул боштук маселеси, чектүүлүк көйгөйү жана мүчөлүк көйгөйү үчүн чечилет.
Канча тилде контекст жок?
(1) чексиз сандагы контекстсиз тилдер бар. Бул туура, анткени контекстсиз тилдин ар бир сүрөттөлүшү чектүү узундукка ээ, ошондуктан мындай сыпаттамалардын эсептик чексиз саны бар. (2) Тилдердин сансыз саны бар.
