1. (a) Adevărat, deoarece fiecare limbă obișnuită nu are context, fiecare limbă fără context este decidabilă și fiecare limbă determinabilă este recunoscută de Turing.
De ce sunt limbile fără context decidabile?
O problemă indecidabilă nu are un algoritm care să determine răspunsul pentru o intrare dată Ambiguitatea limbilor fără context: Având în vedere un limbaj fără context, nu există nicio mașină Turing care va opriți-vă întotdeauna într-un interval de timp finit și răspundeți dacă limbajul este ambiguu sau nu.
Este determinabil subsetul unui limbaj fără context?
2 Răspunsuri. Σ nu are context (într-adevăr, este obișnuit) și are o mulțime de subseturi. Dacă L este un limbaj fără context de dimensiune infinită, atunci există submulțimi J din L care sunt decidabile și unele care sunt indecidabile. De exemplu, subsetul gol este determinabil.
Sunt CFL-urile decidabile?
CFL: este decidabil pentru problema de vid, problema de finisare și problema de membru.
Câte limbi sunt fără context?
(1) Există un număr infinit infinit de limbi fără context. Acest lucru este adevărat deoarece fiecare descriere a unui limbaj fără context este de lungime finită, deci există un număr infinit infinit de astfel de descrieri. (2) Există un număr nenumărat de limbi.
