0 0 votes Theory of Computation decidability bad-question + – monty 1.4k views answer comment Share Follow Print See all 2 Comments 2 2 Comments reply monty commented Oct 28, 2016 reply Follow flag @arjun Sir Pls explain 0 0 replyShare Arjun commented Oct 28, 2016 reply Follow flag What is the source of question? 0 0 replyShare Please log in or register to add a comment.
1 1 vote Here both the languages can be implemented by DFA in Polynomial time So Both are not NPC . NPC problems are very tough problems like:-> https://en.m.wikipedia.org/wiki/List_of_NP-complete_problems So D is Ans. Rajesh Pradhan answered Oct 28, 2016 • edited Oct 29, 2016 by Rajesh Pradhan Rajesh Pradhan comment Share Follow See all 6 Comments 6 6 Comments reply Arjun commented Oct 28, 2016 reply Follow flag DFA falls under P? 0 0 replyShare monty commented Oct 28, 2016 reply Follow flag Regular expressions Fall under P or NP ? 0 0 replyShare Rajesh Pradhan commented Oct 28, 2016 reply Follow flag @arjun sir not Sure abt DFA is possible in P time but I think that €* and Phi Possible in P time. Plz verify me. http://math.stackexchange.com/questions/28194/how-to-show-that-all-dfa-is-in-p 0 0 replyShare Arjun commented Oct 28, 2016 reply Follow flag So that means we need to know in what form the languages are given here rt? 0 0 replyShare sudsho commented Oct 28, 2016 reply Follow flag sir we have to know languages or machines accepting them? i mean like regular languages are accepted by both DFA and NFA....means DFA and NFA boh are P?? 0 0 replyShare Rajesh Pradhan commented Oct 29, 2016 reply Follow flag @arjun sir Yes. 0 0 replyShare Please log in or register to add a comment.
