Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 17: | Line 17: | ||
So, suppose <math>L_2</math> is decidable. Now we have a <math>TM</math> <math>T</math>, which can enumerate all strings of <math>L_2</math>. For each of these strings <math>w</math>, we can find <math>x</math>, such that <math>f(x) = w</math> using the function $f^{-1}$. Since $f^{-1}$ is bijective, it ensures that for each of the string <math>w</math> enumerated by <math>T</math>, we are getting a unique $f^{-1}(w)$ (because of one-one property of bijection) and we are guaranteed that we'll generate all strings of $L_1$ (because of "co-domain = range" property of bijection),. i.e.; we are actually enumerating all strings of <math>L_1</math>. Thus, <math>L_1</math> should also be recursively enumerable. | So, suppose <math>L_2</math> is decidable. Now we have a <math>TM</math> <math>T</math>, which can enumerate all strings of <math>L_2</math>. For each of these strings <math>w</math>, we can find <math>x</math>, such that <math>f(x) = w</math> using the function $f^{-1}$. Since $f^{-1}$ is bijective, it ensures that for each of the string <math>w</math> enumerated by <math>T</math>, we are getting a unique $f^{-1}(w)$ (because of one-one property of bijection) and we are guaranteed that we'll generate all strings of $L_1$ (because of "co-domain = range" property of bijection),. i.e.; we are actually enumerating all strings of <math>L_1</math>. Thus, <math>L_1</math> should also be recursively enumerable. | ||
| + | |||
| + | |||
| + | |||
| + | <div class="fb-like" data-layout="standard" data-action="like" data-share="true"></div> | ||
| + | |||
| + | |||
| + | <div class="fb-share-button" data-type="button_count"></div> | ||
| + | |||
| + | |||
| + | |||
| + | <disqus/> | ||
| + | |||
| + | |||
| + | [[Category: GATE2003]] | ||
| + | [[Category: Automata Theory]] | ||
| + | [[Category: Previous year GATE questions]] | ||
Consider two languages $L_1$ and $L_2$ each on the alphabet $\sigma$. Let $f : ∑ → ∑$ be a polynomial time computable bijection such that $(\forall x) [x\in L1 \iff f(x) \in L2]$. Further, let $f^{-1}$ be also polynomial time computable.
Which of the following CANNOT be true ?
(A) L_1 Image not present P and L_2 is finite
(B) L_1 Image not present NP and L_2 Image not present P
(C) L_1 is undecidable and L_2 is decidable
(D) L_1 is recursively enumerable and L_2 is recursive
A language <math>L</math> is recursively enumerable, iff there is a Turing Machine <math>M</math>, which can enumerate all the strings of <math>L</math>.
So, suppose <math>L_2</math> is decidable. Now we have a <math>TM</math> <math>T</math>, which can enumerate all strings of <math>L_2</math>. For each of these strings <math>w</math>, we can find <math>x</math>, such that <math>f(x) = w</math> using the function $f^{-1}$. Since $f^{-1}$ is bijective, it ensures that for each of the string <math>w</math> enumerated by <math>T</math>, we are getting a unique $f^{-1}(w)$ (because of one-one property of bijection) and we are guaranteed that we'll generate all strings of $L_1$ (because of "co-domain = range" property of bijection),. i.e.; we are actually enumerating all strings of <math>L_1</math>. Thus, <math>L_1</math> should also be recursively enumerable.
Consider two languages $L_1$ and $L_2$ each on the alphabet $\sigma$. Let $f : ∑ → ∑$ be a polynomial time computable bijection such that $(\forall x) [x\in L1 \iff f(x) \in L2]$. Further, let $f^{-1}$ be also polynomial time computable.
Which of the following CANNOT be true ?
(A) L_1 Image not present P and L_2 is finite
(B) L_1 Image not present NP and L_2 Image not present P
(C) L_1 is undecidable and L_2 is decidable
(D) L_1 is recursively enumerable and L_2 is recursive
A language <math>L</math> is recursively enumerable, iff there is a Turing Machine <math>M</math>, which can enumerate all the strings of <math>L</math>.
So, suppose <math>L_2</math> is decidable. Now we have a <math>TM</math> <math>T</math>, which can enumerate all strings of <math>L_2</math>. For each of these strings <math>w</math>, we can find <math>x</math>, such that <math>f(x) = w</math> using the function $f^{-1}$. Since $f^{-1}$ is bijective, it ensures that for each of the string <math>w</math> enumerated by <math>T</math>, we are getting a unique $f^{-1}(w)$ (because of one-one property of bijection) and we are guaranteed that we'll generate all strings of $L_1$ (because of "co-domain = range" property of bijection),. i.e.; we are actually enumerating all strings of <math>L_1</math>. Thus, <math>L_1</math> should also be recursively enumerable.
GATECSE