Awesome q2a theme
0 votes
39 views
  1. L={<M>|L(M) is finite}- undecidable.
  2. $L=\left \{ L\left ( M \right ) |L\left (M\right )=\Sigma ^{*} \right \}$-undecidable
  3. L={<M>|L(M) is recursive}- undecidable.
  4. L={<M>|L(M) is PROPER subset of $\Sigma ^{*}$}- undecidable   [while, L={<M>|L(M) is  subset of $\Sigma ^{*}$}- decidable ]

How these four conclusion is correct? Plz. explain 

in Theory of Computation by (757 points) | 39 views
0
In original site, you have answers for all these questions... Just search
0
yes. All are correct. But "why" matters more.
0
Actually all looks like regular language, but then how undecidable, that part was confusing me. After that I got proof by rices theorem.But I was finding  some more explanation, specially for last one.
Actually their looks were confusing me, that if they are regular or unecidable.

Please log in or register to answer this question.

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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jul 2020
  1. Shaik Masthan

    39 Points

  2. pritishc

    10 Points

  3. Charuji24

    9 Points

  4. hiteshpujari

    9 Points

  5. srestha

    9 Points

  6. fazin

    7 Points

  7. divi2719

    7 Points

  8. sthakur369

    6 Points

  9. Richa Agrawal

    6 Points

  10. gaurav2697

    6 Points

7,577 questions
1,785 answers
10,885 comments
90,507 users