Concept drill
many-one reduction
GATE CSE & IT · Turing Machines & Computability · 2014-2016
2
PYQs
100%
keyed
0
elite explanations
2
years appeared
Study anchor
Hopcroft-Ullman / Dragon Book
Automata, languages, parsing, syntax-directed translation
Practice action
Start latest PYQPYQs in this concept
All concepts →2016 PYQ
Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\overline Y $$ reduces to $$W,$...
mediumanswer key
2014 PYQ
Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?
mediumanswer key