Какая из следующих проблем неразрешима?
(A) Решение, является ли данная грамматика без контекста неоднозначной.
(B) Решение о том, генерируется ли данная строка заданной контекстно-свободной грамматикой.
(C) Решение, является ли язык, генерируемый данной контекстно-свободной грамматикой, пустым.
(D) Решение о том, конечен ли язык, генерируемый данной контекстно-свободной грамматикой.
Ответ: (А)
Пояснение: контекстно-свободная грамматика не закрыта из-за неоднозначности . Множество закрыто под операцией, значит, когда мы оперируем элементом этого множества с этим оператором, мы получаем элемент из этого множества.
Здесь контекстно-свободная грамматика генерирует контекстно-свободный язык, и набор всех контекстно-свободных языков также является набором. Но, двусмысленность не является операцией, и, следовательно, мы никогда не можем сказать, что CFG закрыт под двусмысленностью.
Таким образом, проблема, упомянутая в варианте (A), неразрешима.
Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.
Тест на этот вопрос
Рекомендуемые посты:
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
- ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65
0.00 (0%) 0 votes