Which of the following is/are undecidable?1. G is a CFG. Is L(G) = Î¦?2. G is

Question

Which of the following is/are undecidable?

1. G is a CFG. Is L(G) = Î¦?

2. G is a CFG. Is L(G) = Î£*?

3. M is a Turing machine. Is L(M) regular?

4. A is a DFA and N is an NFA. Is L(A) = L(N)?

Options:

A . 3 only

B . 3 and 4 only

C . 1, 2 and 3 only

D . 2 and 3 only

Answer: Option D

-NA-

Was this answer helpful ?

Next Question

More Questions on This Topic :

Question 1. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the followi....following is the postorder traversal sequence of the same tree?

Question 2. A RAM chip has a capacity of 1024 words of 8 bits each (1K Ã— 8). The number of 2 Ã— 4 decoders with enable line ....16K Ã— 16 RAM from 1K Ã— 8 RAM is

Question 3. The following code segment is executed on a processor which allows only register operands in its instructions. Each ins....minimum number of spills to memory in the compiled code?

Question 4. Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction (FI), Decode Instruc....the time (in ns) needed to complete the program is

Question 5. Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. M....sequence of n queue operations on an initially empty queue?

Question 6. The cost function for a product in a firm is given by 5q2, where q is the amount of production. The firm can sell the p....by the firm such that the profit is maximized is

Question 7. Choose the grammatically INCORRECT sentence: ....

Question 8. Which one of the following options is the closest in meaning to the word given below? Mitigate ....

Question 9. Wanted Temporary, Part-time persons for the post of Field Interviewer to conduct personal interviews to collect and col....the following is the best inference from the above advertisement?

Question 10. Choose the most appropriate alternative from the options given below to complete the following sentence: Despite sever....the mission succeeded in its attempt to resolve the conflict.

Chapter 1 - GLOBAL STEEL SCENARIO & INDIAN STEEL INDUSTRY Part 1 : (13-04-2024) INDUSTRY AND COMPANY AWARENESS (ICA)

Direction Sense Test Part 1 Reasoning (Hindi)

Chapter 1 - RMHP / OHP / OB & BP Part 1 : (14-02-2024) GPOE

Cube & Cuboid Part 1 Reasoning (Hindi)

Data Interpretation (DI) Basic Concept Reasoning (Hindi)

Counting Figures Part 1 Counting Of Straight Lines Reasoning (Hindi)

Sail E0 free webinar Webinars

Real Numbers Part 7 Class 10 Maths

Real Numbers Part 1 Class 10 Maths

Polynomials Part 1 Class 10 Maths

DSP Combined 1 Free Revision Test SAIL JO E-0

GPOE / GPA Combined 1 Free Revision Test SAIL JO E-0

BSP Plant Specific Review Test SAIL JO E-0

BSL Combined 1 Free Revision Test SAIL JO E-0

GFM Combined 1 Free Revision Test SAIL JO E-0