The Gateway to Computer Science Excellence
+1 vote
305 views
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$

Is $L_1$ RE or not RE?
in Theory of Computation by Active (5.1k points) | 305 views
0
i think it is RE,

even though xy ∉ L(M), it may belong to some other L(M1), where M1 is another turing machine. and also x ∈ ∑*
0
answer is given as not re.

2 Answers

+3 votes
Best answer

$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$

So, here the Turing Machine for $L_1$ must decide if any input Turing Machine $M$ is having this property. Is this property non-trivial for the recursively enumerable set?

  • $L(T_{yes}) = \{\}$ - $L$ is having no elements and so the given property holds
  • $L(T_{no}) = \Sigma^*$ - since $L$ is having all the strings, any concatenated (with any one) string, $xy$ will also be in $L$ violating the given property

(We can have any other $T_{yes}$ and $T_{no},$ I just took one)

Since, we have an element for "yes" case as well as "no" case, the property is non-trivial. Any non-trivial property of recursively enumerable set is undecidable (Rice's theorem part 1).

Here, $L(T_{yes}) \subset L(T_{no}),$ which makes the property non-monotonic. And any non-monotonic property of recursively enumerable set is not-even semi-decidable (Rice's theorem part 2) which makes its language not recursively enumerable. 

Reference

by Veteran (432k points)
selected by
+1

@Arjun Sir Is my approach correct?

Σ={a,b}

Let the language being accepted by Tyes be Lyes and language being accepted by Tno is Lno. Let us consider Lyes={a} (since there exists an x i.e x=b such that for all y belonging to Lyes, xy doesn't belong to Lyes) and Lno* (since there exists an x i.e. ϵ such that xy belongs to Lno for all y belonging to Lno). So as Lyes is a proper subset of Lno, so this is a non-monotonic property and hence from rice's second theorem, the language L1 becomes not recursively enumerable.

Is this correct?

 

0

@arjun sir

by writing this statement

L(Tyes)={ } - L is having no elements and so the given property holds

do you want to say that there is no turing machine which accept the condition given in the question?

 

 

+2
@Somoshree Yes, that is correct (y)

@Gurdeep No, I mean one of the Turing machine which is having the given property accepts empty language.
0
@Somoshree

Can u tell me plz what is ur x,y, and how $xy\notin L(M)$?
0

There exists x∈Σ* such that for every yL(M),xyL(M)

 

Let P(y) denote that yL(M)

And Q(x,y) denote that xyL(M) where x∈Σ*

So this statement can be written like:

∃x,∀y P(y)⋀Q(x,y)

∃x,∀y P(y)⋀Q(x,y) = {P(y1)⋀Q(x1,y1) ⋀ P(y2)⋀Q(x1,y2)⋀.....⋀ P(yn)⋀Q(x1,yn) } ⋁

{P(y1)⋀Q(x2,y1) ⋀ P(y2)⋀Q(x2,y2)⋀.....⋀ P(yn)⋀Q(x2,yn) }⋁

{P(y1)⋀Q(xm,y1) ⋀ P(y2)⋀Q(xm,y2)⋀.....⋀ P(yn)⋀Q(xm,yn) }

where yi belongs to L(M) and xj belongs to Σ*.

Now if L(M)= { } is Tyes then this predicate logic should be valid.

@Arjun Sir please help me proceed..I am stuck! And if all what i wrote is wrong then please correct me..

+1

@Srestha maam Consider language Lyes is defined over $\Sigma$={a,b}. Let Lyes={a}. Then there exists an x(here x=b satisfies this property) in $\Sigma$* such that for all y in Lyes, xy(here x.y gives the string ba which isnt present in Lyes) xy doesnt belong to Lyes.

0
yes, right :)
0

@MiniPanda

why u take for all y

it maynot true for all y

this line is very important to satisfy non-monotonic property

we have an element for "yes" case as well as "no" case, the property is non-trivial.

0

@srestha

L1={⟨M⟩∣ there exists x∈Σ∗ such that for every yL(M),xyL(M)}.
 

It should be true for all y that belong to L(M)..isn't it?

0
yes,

After ur last line of proof

$\left \{ \right \}\subset \Sigma ^{*}$

So, non-monotonic property satisfies

So, nonRE

ok now?
0

@srestha

Actually I am not getting how L(Tyes) is  { }. This might be silly but still :/

0
same here..even i am not getting as to how empty set is satisfying the condition of the language..
0
nothing is subset of everything

right?

Here { } is the string which even not contain $\epsilon$

{ } here is empty set, which is in $L(M)$

but when concatenate $\left \{ \right \}.\Sigma ^{*}=\Sigma ^{*}$ which is not in $L(M)$

So, we can apply Rice theorem

And $\left \{ \right \}\subset \Sigma ^{*}$

----------------------------------------------------------------------------------------------------------------------------------

Note: Here concatenation doesnot contain empty set, but subset of concatenated set contain empty set
+1
@Somoshree Suppose I say every one in the class should come with their parents. Now, if there is no one in the class, the condition is satisfied rt?
0

but when concatenate {}.Σ∗=Σ∗ which is not in L(M)

{ } concatenated with anything gives { } right?? 

+1
Concatenation is for strings in $L$. Since there is no string in $L$, concatenation cannot happen.
0
@Arjun sir,  so when we concatenate empty language with some other language then we get empty language right?  But here we are concatenating strings right?
0

@Arjun Sir plz chk it

yes, I too think the empty set or null set is the unique set having no elements

So,

  empty set always unreachable from start state, So, it's concatenation also will be unreachable from start state

https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/15/Small15.pdf

So, how Tyes here subset of Tno

$T_{yes}=\Phi$ and also $T_{no}=\Phi$

isnot in this example Tyes=Tno?

I am not getting difference between empty set and NULL set

0 votes

We can have $Tyes$ for $L(M)$ and $Tno$ for $ϕ$. Hence, $L_1$ is no recursive for sure.

$L(M)$ is recursive so obviously $\exists$ TM for it, so this TM says $T_{yes}$ for L(M) and also there exists a TM which says no for $\Sigma^*$

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable

For a property of recursively enumerable set to be non-monotonic, there should exist at least two recursively enumerable languages (hence two Turing machines), the property holding for one ($Tyes$ being its TM) and not holding for the other ($Tno$ being its TM) and the property holding set (language of $Tyes$) must be a proper subset of the set not having the property (language of $Tno$).

we are pretty sure that $L(M)$ is a proper subset because it is given in the definition of the $L_1$ there exists x ϵ Σ* such that for every y ϵ L(M), xy ∉ L(M).

So there exist a TM which is holding properties of L(M), which can say $Tyes$ for L(M), and another TM which says $Tno$ for $\Sigma^*$. 

$L(M) \subset \Sigma^*$

Property holding set is non monotonic because it is proper subset of of the set $ \Sigma^*$

Hence $L_1$ is non RE

by Boss (36.6k points)
edited by
0

@Mk Utkarsh how are you getting $\Sigma$* for Tyes??Can you please elaborate on this point a bit more?

0
Can you please explain as to how u are applying rice's 2nd theorem here?
0

Somoshree check the edit

0

@Mk Utkarsh the property is holding  if Tyes is $\Sigma$* and the property isnt holding if Tno is $\phi$ and Tyes has to be a proper subset of Tno for the property to be non monotonic. But $\Sigma$* isnt a preoper subset of $\phi$, then how is rice's theorem applicable here?? I am not getting this :(

0
$Tyes$ for L(M) this language contains all $y's$

$Tno$ for $\Sigma^*$

$L(M) \subset $ $\Sigma^*$
0
how are you saying L(M) is recursive ? there isnt any clue about L(M) in question. am i missing something ? @utkarsh
0
<M> is encoding of TM, so L(M) is language accepted by that TM
0

@Mk Utkarsh

Can this be an approach to this question?

$\Sigma$={a,b}

Let the language being accepted by Tyes be Lyes and language being accepted by Tno is Lno. Let us consider Lyes={a} (since there exists an x i.e x=b such that for all y belonging to Lyes, xy doesnt belong to Lyes) and Lno =$\Sigma$* (since there exists an x i.e. $\epsilon$ such that xy belongs to Lno for all y belonging to Lno). So as Lyes is a proper subset of Lno, so this is a non-monotonic property and hence from rice's second theorem, the language L1 becomes not recursively enumerable.

Is this correct?

0

 Lno =Σ*(since there exists an x i.e. ϵ such that xy belongs to Lno for all y belonging to Lno).

i lost you here, can you explain this sentence more?

0

If the language accepted by the turing machine Tno is $\Sigma$*, then there exists such an x such that for every y belonging to Lno(i.e. $\Sigma$* here), xy belongs to Lno. This is true because if we take x to be equal to $\epsilon$, then x.y= $\epsilon$.y=y which is already known to belong to Lno.

0
if x is $\epsilon$ then for $\forall y (xy \in L(M)$

if you don't worry about what x is as x can be anything, $xy$ will still be in $\Sigma^*$
0
Yes. So is this approach is correct?
0

Somoshree yes according to me, but i'm no expert :p

0
ok..thanks :)
0
Your examples are wrong - not sure how you got the answer :)
0

Arjun sir please tell how examples are wrong?

i assumed both x and L(M) to be non empty

$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$  Is $L_1$ RE or not RE?

so L(M) is containing some property which is unknown but the only thing we know it prepending some string x $ \in \Sigma^*$ will violate the property of L(M). But we also know that L(M) is a language of some turing machine, this makes L(M) recursive so $\exists TM$ which satisfied L(M).

$L(T_{yes}) = L(M)$ 

$L(T_{no}) = \Sigma^* $

0
if $\Phi$ concatenate with $\Sigma$ then $\Phi$ comes

then how $xy!\in L(M)$ satisfies?
0

srestha not getting you

0
x cannot be $\epsilon$

if it is then $y \in L(M)$ and y $\notin L(M)$ both will be true

which is contradiction
0
Can anyone point out my mistake?
+1
@Mk Utkarsh

very simple example Somoshree gave

Say L(M) ={a}

and x=a too

Say y=b

So, xy=ab which is not in L(M)

So, $T_{yes}=a$

$T_{no}=ab$

and also $T_{yes}\subset T_{no}$

So, non monotonic property is satisfied

Hence it is non RE

Hope u got it
+1

srestha i agreed to all comments and answer on this question, but i wanted to know the mistake i made so that i'll not make it in future :)

0

@Mk Utkarsh how are you getting Tyes as  $\Sigma$* ? Give an example..

0

Somoshree ok while applying 1st part of rice's theorem i shouldn't have use $\Sigma ^*$ but is it correct now?

0

@Mk Utkarsh so what is Tyes now??

0
$L(M)$

Related questions

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
50,737 questions
57,405 answers
198,629 comments
105,468 users