1. (a) Prawda, ponieważ każdy język regularny jest bezkontekstowy, każdy język bezkontekstowy jest rozstrzygalny, a każdy rozstrzygalny język jest rozpoznawalny przez Turinga.
Dlaczego można rozstrzygać w językach bezkontekstowych?
Nierozstrzygalny problem nie ma algorytmu do określenia odpowiedzi dla danego wejścia Niejednoznaczność języków bezkontekstowych: Biorąc pod uwagę język bezkontekstowy, nie ma maszyny Turinga, która zawsze zatrzymuj się w skończonej ilości czasu i udzielaj odpowiedzi, czy język jest niejednoznaczny, czy nie.
Czy podzbiór języka bezkontekstowego jest rozstrzygalny?
2 Odpowiedzi. Σ jest bezkontekstowy (w rzeczywistości jest regularny) i ma wiele podzbiorów. Jeśli L jest językiem bezkontekstowym o nieskończonej wielkości, to istnieją podzbiory J języka L, które są rozstrzygalne, a niektóre są nierozstrzygalne. Na przykład pusty podzbiór jest rozstrzygalny.
Czy CFL są rozstrzygalne?
CFL: rozstrzygane dla problemu pustki, problemu skończoności i problemu członkostwa.
Ile języków jest bezkontekstowych?
(1) Istnieje nieskończona liczba języków bezkontekstowych. To prawda, ponieważ każdy opis języka bezkontekstowego ma skończoną długość, a więc istnieje przeliczalnie nieskończona liczba takich opisów. (2) Istnieje niezliczona liczba języków.
