1. (a) Рас, әрбір қалыпты тіл контекстсіз болғандықтан, әр контекстсіз тіл шешіледі және шешілетін тіл Тьюринг арқылы танылады.
Неге контекстсіз тілдерді таңдауға болады?
Шешілмейтін мәселеде берілген кірістің жауабын анықтайтын алгоритм жоқ Мәтінмәнсіз тілдердің анық еместігі: Мәтінмәнсіз тілді ескере отырып, Тьюринг машинасы жоқ. әрқашан шектеулі уақытта тоқтап, тіл анық емес пе, жоқ па жауап беріңіз.
Мәтінмәнсіз тілдің ішкі жиынын шешуге болады ма?
2 Жауаптар. Σ мәтінмәнсіз (шынымен де, бұл қалыпты) және оның көптеген ішкі жиындары бар. Егер L шексіз өлшемді мәтінмәнсіз тіл болса, L жиынының J ішкі жиындары шешілетін, ал кейбіреулері шешілмейтін болады. Мысалы, бос жиынды шешуге болады.
CFL шешуге бола ма?
CFL: бостық мәселесі, шектілік мәселесі және мүшелік мәселесі үшін шешіледі.
Қанша тіл контекстсіз?
(1) контекстсіз тілдердің сансыз шексіз саны бар. Бұл дұрыс, себебі мәтінмәнсіз тілдің әрбір сипаттамасы шекті ұзындыққа ие, сондықтан мұндай сипаттамалардың сандық шексіз саны бар. (2) Тілдердің сансыз саны бар.
