1. (a) Het is waar, aangezien elke reguliere taal contextvrij is, elke contextvrije taal is beslisbaar, en elke beslisbare taal is Turing-herkenbaar.
Waarom zijn contextvrije talen beslisbaar?
Een onbeslisbaar probleem heeft geen algoritme om het antwoord voor een gegeven invoer te bepalen Ambiguïteit van contextvrije talen: bij een contextvrije taal is er geen Turing-machine die stop altijd binnen een beperkte tijd en geef antwoord of de taal dubbelzinnig is of niet.
Is de subset van een contextvrije taal beslisbaar?
2 Antwoorden. Σ is contextvrij (inderdaad, het is normaal) en het heeft veel subsets. Als L een contextvrije taal is van oneindige grootte, dan zijn er deelverzamelingen J van L die beslisbaar zijn en sommige onbeslisbaar. De lege subset is bijvoorbeeld beslisbaar.
Zijn CFL's beslisbaar?
CFL: Het is beslisbaar voor het leegteprobleem, het eindigheidsprobleem en het lidmaatschapsprobleem.
Hoeveel talen zijn contextvrij?
(1) Er zijn een aftelbaar oneindig aantal contextvrije talen. Dit is waar omdat elke beschrijving van een contextvrije taal een eindige lengte heeft, dus er zijn een aftelbaar oneindig aantal van dergelijke beschrijvingen. (2) Er zijn ontelbaar veel talen.
