1. (ա) Ճիշտ է, քանի որ յուրաքանչյուր կանոնավոր լեզու առանց համատեքստի է, յուրաքանչյուր առանց համատեքստի լեզու որոշելի է, և յուրաքանչյուր որոշելի լեզու ճանաչելի է Թյուրինգի կողմից:
Ինչու են առանց համատեքստի լեզուները որոշելի:
Անորոշելի խնդիրը չունի տվյալ մուտքագրման պատասխանը որոշելու ալգորիթմ Համատեքստից զերծ լեզուների երկիմաստություն. Եթե համատեքստից զերծ լեզու լինի, չկա Թյուրինգի մեքենա, որը կարող է միշտ կանգ առեք որոշակի ժամանակով և պատասխանեք՝ լեզուն երկիմաստ է, թե ոչ:
Հնարավո՞ր է որոշել առանց համատեքստի լեզվի ենթաբազմությունը:
2 Պատասխաններ. Σ-ն առանց համատեքստի է (իսկապես, սովորական է) և ունի բազմաթիվ ենթաբազմություններ: Եթե L-ն անսահման չափի լեզու է առանց համատեքստի, ապա կան L-ի J ենթաբազմություններ, որոնք որոշելի են, իսկ որոշները՝ անորոշ: Օրինակ՝ դատարկ ենթաբազմությունը որոշելի է։
Արդյո՞ք CFL-ը որոշելի է:
CFL: Դա որոշելի է դատարկության խնդրի, վերջավորության և անդամակցության խնդրի համար:
Քանի՞ լեզու է համատեքստից զուրկ:
(1) Գոյություն ունեն համարելի անսահման թվով լեզուներ, որոնք չեն համատեքստից: Սա ճիշտ է, քանի որ կոնտեքստից զերծ լեզվի յուրաքանչյուր նկարագրություն ունի վերջավոր երկարություն, հետևաբար կան անսահման թվով նման նկարագրություններ: (2) Կան անհաշվելի թվով լեզուներ:
