Register

Complexity

1,231 views
1 1 vote

How to decide the complexity of any language?

1 Answer

1 1 vote

Don't know what that complexity is about.

The question says that TM halts on every input i.e it outputs Yes for all strings belonging to L and NO for those that doesn't.

It implies its a halting TM which accepts Recursive language. (Recursive is superset of CFL and CSL).

For Recursively Enumerable languages, TM halts for acceptable strings but doesn't halt always if string doesn't belong to L and goes into infinite looping.

So answer is Recursive language

Voting & Accepting an answer helps improve the community
← Previous · universal turing mac...Next → · Which of the followi...
← Previous in category · universal turing mac...Next in category → · Which of the followi...
Position:
Show:

Related questions

0 0 votes
1 1 answer
42
42 views
GO Classes asked 6 days ago
42 views
GO Classes DPP | GATE CS | Theory of Computation | Computability and Complexity
Which of the following statements is INCORRECT?The union of two recursive languages is recursive. According to the Church-Turing Thesis, Turing machines capture the compu...
2 2 votes
1 1 answer
111
111 views
GO Classes asked Sep 19
111 views
GO Classes DPP | GATE CS | Theory of Computation | State Complexity
Which statements are true?Every language recognized by an $n$-state DFA can be recognized by an NFA with $n$ states. Every language recognized by an $n$-state NFA can be ...
3 3 votes
1 answers 1 answer
2.4k
2.4k views
ankitgupta.1729 asked Mar 27, 2018
2,367 views
Time complexity to minimize Finite Automata
According to this Hopcroft's algorithm , we can efficiently minimize a Finite automata in $O(nlogn)$ time (polynomial time algo) then why it is said that Minimizing Fin...
0 0 votes
0 0 answers
881
881 views
hacker16 asked Dec 24, 2017
881 views
did P and NP is still in the syllabus? @ COMPUTABILITY AND COMPLEXITY{TOC}
did P and NP is still in the syllabus? @ COMPUTABILITY AND COMPLEXITY{TOC}