72 views

Let L1 be decidable language and L2 be turing recognizable but not decidable language, then –

1. L2/L1 is turing recognizable
2. L1/L2 is decidable language

Number of correct statements _?
| 72 views
0
1 correct statement.

i.e. I)??
0
Yes!
How??
0

Actually a good question from ME.

0

@Shaik Masthan

I thought it like this.....

I) $L2/L1$ is a division, which is a short form of subtraction. right? Now, in case of $L2-L1=L2\cap \left ( L1 \right )'=T.Recog.\cap T. Deci.=$Turing recognizable.

right??

Similarly for II) too

0
Where you read L2/L1 is short form of subtraction?

It's right quotient operator.
0

@Shaik Masthan

now you elaborate .

0

@Shaik Masthan

What is your view, plz tell. Actually I applied some discrete math concept here.

0
As L1 and L2 both are Turing-recognigable languages and so, according to closure properties, quotient operation (whether it is left quotient or right quotient) on both, will give turing-recognizable language.
0

Let L$_1$ be decidable language and L$_2$ be Turing recognizable but not decidable language,

L$_1$ having a Halting TM. i.e., produce YES for correct inputs and Produce NO for wrong inputs of the Language.

L$_2$ having a TM. i.e., produce YES for correct inputs but may not Produce NO for wrong inputs of the Language.

For reference TM$_1$ is corresponding to L$_1$ and TM$_2$  is corresponding to L$_2$

1. L$_2$/L$_1$ is Turing recognizable

L = L$_2$/L$_1$ ( right quotient operator ), For reference TM$_{main}$ is corresponding to L

it means, if ∈ L, then there must be some y ∈ ∑*, w.y ∈ L$_2$ and y ∈ L$_1$

For saying L is Turing recognizable, you should have some TM which can surely say YES for the string which is belongs to L.

When i applied w on TM$_{main}$, internally we choose some y ∈ ∑*, and give to TM$_1$, due to TM$_1$ property, we understood that either y ∈ L$_1$ or y ∉ L$_1$

If y ∈ L$_1$, then we give w.y as input to TM$_2$, due to TM$_2$ property, it produce YES for YES input, So if TM$_2$ produce YES then TM$_{main}$ will produce for w. So, TM$_{main}$ is Turing recognizable.

Now my question is TM$_{main}$ is Turing decidable ?

NO, due to TM$_2$ property, it may not produce NO for NO input, So if TM$_2$ may fall in loop then TM$_{main}$ also wait in loop for producing NO for w. So, TM$_{main}$ is not Turing decidable.

L$_1$/L$_2$ is decidable language

L = L$_2$/L$_1$ ( right quotient operator ), For reference TM$_{main}$ is corresponding to L

it means, if ∈ L, then there must be some y ∈ ∑*, w.y ∈ L$_1$ and y ∈ L$_2$

For saying L is Turing recognizable, you should have some TM which can surely say YES for the string which is belongs to L.

When i applied w on TM$_{main}$, internally we choose some y ∈ ∑*, and give to TM$_1$, due to TM$_1$ property, we understood that either w.y ∈ L$_1$ or w.y ∉ L$_1$

If w.y ∈ L$_1$, then we give y as input to TM$_2$, due to TM$_2$ property, it produce YES for YES input, So if TM$_2$ produce YES then TM$_{main}$ will produce for w. So, TM$_{main}$ is Turing recognizable.

Now my question is TM$_{main}$ is Turing decidable ?

NO, due to TM$_2$ property, it may not produce NO for NO input, So if TM$_2$ may fall in loop then TM$_{main}$ also wait in loop for producing NO for w. So, TM$_{main}$ is not Turing decidable.

by (696 points)
0

@Shaik Masthan

that means for any language, these two will produce same output?

1. L2/L1 is turing recognizable
2. L1/L2 is decidable language

In 1st part of your answer , why you took $y\notin L1?$

0
I didn't understood your first question... Show with some examples.

For second one, read two more times... You will understood.
0
L2/L1 is turing recognizable- True.

L1/L2 is turing recognizable-True

is it not correct?