Register

Automata P problems

400 views
1 votes
1 votes
Which of the following problems is/are P-problems?
I. Equivalence of DFA's
II. Equivalence of NFA
III. Equivalence of RE

(a) Only I
(b) Only I and II
(c) Only II and III
(d) All
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
3
ryan sequeira asked Feb 1, 2016
4,018 views
Decidable and Undecidable problems of automata
Please list down all the decidable and undecidable problems for FA, PDA, TM. Since there isnt a single place where all are listed.
Please list down all the decidable and undecidable problems for FA, PDA, TM.Since there isnt a single place where all are listed.
User Avatar
0 votes
0 votes
0 answers
4
baofbuiafbi asked Nov 14, 2023
148 views
Michael Sipster Decidability Problems
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
User Avatar
Link Copied!