Awesome q2a theme
+2 votes
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 _?
in Theory of Computation by (10 points) | 72 views
0
1 correct statement.

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

Actually a good question from ME.

@srestha, can you elaborate your answer ?

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
I added my explanation as answer, please check.

1 Answer

+2 votes

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 (690 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?
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users 2020 Aug 03 - 09
  1. Ashutosh07091999

    18 Points

  2. Mellophi

    13 Points

  3. prashastinama

    6 Points

  4. manas_kulkarni

    4 Points

  5. srestha

    2 Points

  6. Unnayan kumar

    1 Points

  7. aryashah2k

    1 Points

  8. Jhaiyam

    1 Points

  9. prabhat0987

    1 Points

  10. Kushagra गुप्ता

    1 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Ashutosh07091999

    21 Points

  2. Mellophi

    19 Points

  3. Unnayan kumar

    8 Points

  4. Sourav Kar

    7 Points

  5. anurag_yo

    7 Points

  6. Shaik Masthan

    7 Points

  7. prashastinama

    6 Points

  8. sureshthiyam

    6 Points

  9. manas_kulkarni

    6 Points

  10. srestha

    4 Points

7,688 questions
1,815 answers
11,053 comments
95,077 users