1. (a) Вярно е, тъй като всеки нормален език е без контекст, всеки език без контекст е разрешим и всеки език, който може да се реши, е разпознаваем по Тюринг.
Защо езиците без контекст се решават?
Неразрешим проблем няма алгоритъм за определяне на отговора за даден вход Неяснота на контекстно-свободните езици: Като се има предвид свободен от контекст език, няма машина на Тюринг, която да винаги спирайте за ограничен период от време и дайте отговор дали езикът е двусмислен или не.
Разрешима ли е подмножеството на език без контекст?
2 отговора. Σ е без контекст (всъщност, това е редовно) и има много подмножества. Ако L е безконтекстно свободен език с безкраен размер, тогава има подмножества J на L, които са разрешими, и някои, които са неразрешими. Например празното подмножество може да се реши.
Разрешими ли са CFL?
CFL: може да се реши за проблем с празнотата, проблем с ограничеността и проблем с членството.
Колко езика са без контекст?
(1) Има изброимо безкраен брой езици без контекст. Това е вярно, защото всяко описание на свободен от контекст език е с крайна дължина, така че има изброимо безкраен брой такива описания. (2) Има неизброим брой езици.
