Register

properties of languages

382 views
1 votes
1 votes
Which of the following statements is false ?
(A) Every NFA can be converted to a
equivalent DFA
(B) Every non-deterministic turning machine
can be converted to an equivalent
deterministic turning machine
(C) Every regular language is also a context
for language
(D) Every subset of a recursively
enumerable set is recursive
User Avatar

1 Answer

Best answer
2 votes
2 votes

OPTION D IS FALSE, there is atleast one recursive enumerable language which is not recursive,you might have taken help of this theorem to prove why Halting problem is undecidable.

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
2
UltraRadiantX asked Oct 9, 2021
472 views
Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.
let L = “CFL but not REGULAR”, Can we get complement of L as CFL?Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, it...
User Avatar
1 votes
1 votes
0 answers
3
Savvy asked Jun 6, 2018
337 views
Introduction to Automata Theory- Properties of regular Languages - Q 4.2.10
Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
User Avatar
Link Copied!