Question: 1 . If L is regular, and L L , then L is also regular. True or False 2 . If language L 1 ,

1. If L is regular, and L L, then L is also regular.
True or False
2. If language L1, L2 are Context-Free languages, then L1 L2 is also Context-Free.
True or False
3. Both AT M ={< M, w >| M accepts w} and its compliment AT M ={< M, w >| M does not accept
w} are TM recognizable but undecidable.
True or False
4. Both ET M ={< M >| M is a Turing Machine with L(M )=} and its compliment ET M ={< M >|
M is a Turing Machine with L(M )=} are Turing-unrecognizable and undecidable.
True or False
5. If SAT is in P, then any language in NP is also in P.
True or False

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!