These slides will be explaining decidability and Rice’s theorem. You can ask if anything is not clear.

Part 2 is added now...

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

These slides will be explaining decidability and Rice’s theorem. You can ask if anything is not clear.

Part 2 is added now...

@Shaik

Ullman says on page 362:

$L_e$ is not RE

It defines $L_e=\{M | L(M) = \phi\}$

I guess this is different from $L=\phi$ and $\phi$ is regular. Seems that I unnecessarily got confused. Right?

L(M) is not regular. How is it non monotonic?

L(M) is not regular ---YES case will have all languages except regular languages and NO case will have languages which are not (not regular) i.e. regular. but Yes case is not a subset of no case. Then how non monotonic? where am i going wrong please correct!

L(M) is not regular ---YES case will have all languages except regular languages and NO case will have languages which are not (not regular) i.e. regular. but Yes case is not a subset of no case. Then how non monotonic? where am i going wrong please correct!

Ok sir... so can I say that a^nb^n being a non regular language (Here, YES case) is a subset of (a+b)*--regular (NO case) . So, non monotonic and hence not even semi decidable?

Can someone help me understand examples on slide page 23. Not able to get meaning of solutions. For example:

L = { <M> | L(M) = {}] - We can say “no” is M accepts some string, but can we every say “yes” as we need to check infinite number of strings?

@Arjun Sir,Thanks a lot

One doubt regarding *Slide no. 30 : Some trivially decidable properties*

L = {<M> | L(M) is countable} --> for this language is it correct to argue that since we have diagonalisation procedure, so this problem becomes decidable?

How diagonalization helps in deciding that? Actually any recursively enumerable language is countable and that is why it becomes a trivial property (Answer is always yes irresepective of the given TM)

Diagonalization proves that there are languages which are not recursively enumerable.

Diagonalization proves that there are languages which are not recursively enumerable.

Ok sir..got it now.

All RE languages and Recursive languages have some enumeration procedure for them and the ones which don't have are non-RE.

All RE languages and Recursive languages have some enumeration procedure for them and the ones which don't have are non-RE.

@Arjun sir confused in this one (https://gateoverflow.in/83694/turing-machine).

Understood your answer given there but here can't we create Tyes= {epsilon} Tno= {a,aa,aaa...} ?

For semi-deciding we can say, we may consider a TM having initial state as final state. So for yes instance it can output Yes but cannot say for any NO instance.

- All categories
- Testimonials 50
- Numerical Ability 0
- Verbal Ability 1
- Engineering Mathematics 13
- Algorithms 3
- Databases 5
- Digital Logic 4
- CO & Architecture 4
- Computer Networks 5
- Compiler Design 3
- Programming & Data Structures 6
- Motivation 27
- Preparation Advice 64
- Theory of Computation 5
- Preparation Experience 37
- Useful Links 24
- Study Materials 26
- Others 203
- Interview Experience 50
- Announcements 80
- Jobs 4

47,931 questions

52,334 answers

182,381 comments

67,816 users

ϕis a Regular language then it should be Recursive enumerable language, right @raj+singh