1. (a) Sandt nok, eftersom ethvert regulært sprog er kontekstfrit, hvert kontekstfrit sprog er afgøreligt, og ethvert afgørbart sprog er Turing-genkendeligt.
Hvorfor kan kontekstfri sprog bestemmes?
Et ubeslutsomt problem har ingen algoritme til at bestemme svaret for et givet input Tvetydighed af kontekstfri sprog: Givet et kontekstfrit sprog, er der ingen Turing-maskine, der vil stop altid i begrænset tid og giv svar, om sproget er tvetydigt eller ej.
Er delmængden af et kontekstfrit sprog afgjort?
2 svar. Σ er kontekstfri (det er faktisk almindeligt), og det har en masse undersæt. Hvis L er et kontekstfrit sprog af uendelig størrelse, så er der delmængder J af L, der kan afgøres, og nogle, der ikke kan afgøres. For eksempel kan den tomme delmængde bestemmes.
Kan CFL's bestemmes?
CFL: Det kan afgøres for tomhedsproblem, finitetsproblem og medlemskabsproblem.
Hvor mange sprog er kontekstfri?
(1) Der er et tælleligt uendeligt antal kontekstfrie sprog. Dette er sandt, fordi enhver beskrivelse af et kontekstfrit sprog er af begrænset længde, så der er et utalligt uendeligt antal af sådanne beskrivelser. (2) Der er et utalligt antal sprog.
