1. (a) Düzdür, hər adi dil kontekstsiz olduğundan, hər kontekstsiz dil həll edilə bilər və hər bir həll edilə bilən dil Turing tərəfindən tanınır.
Niyə kontekstsiz dillər həll edilə bilər?
Qərarlaşdırıla bilməyən problemin verilmiş giriş üçün cavabı təyin etmək üçün alqoritmi yoxdur Kontekstdən azad dillərin qeyri-müəyyənliyi: Kontekstdən azad dil nəzərə alınmaqla, heç bir Turinq maşını yoxdur. həmişə sonlu vaxtda durun və dilin birmənalı olub olmadığına cavab verin.
Kontekstsiz dilin alt çoxluğu həll edilə bilərmi?
2 Cavablar. Σ kontekstsizdir (həqiqətən də müntəzəmdir) və onun çoxlu alt qrupları var. Əgər L sonsuz ölçülü kontekstsiz bir dildirsə, L-nin həll edilə bilən J alt çoxluqları var, bəziləri isə qeyri-müəyyəndir. Məsələn, boş alt çoxluq həll edilə bilər.
CFL həlledicidirmi?
CFL: boşluq problemi, sonluq problemi və üzvlük problemi üçün həll edilə bilər.
Neçə dil kontekstsizdir?
(1) hesabsız sayda kontekstdən azad dillər var. Bu doğrudur, çünki kontekstsiz dilin hər təsviri sonlu uzunluğa malikdir, ona görə də belə təsvirlərin sayıla bilməyəcək qədər sonsuz sayda var. (2) Saysız-hesabsız dillər var.
