Register

decidability

248 views
2 votes
2 votes

A = { <M> | M is a DFA that accepts WR whenever it accepts W }. Then A is -

a) Turing recognizable

b) Turing unrecognizable

c) decidable

d) undecidable

User Avatar

1 Answer

0 votes
0 votes
I am not sure, Take the dfa, reverse it.. Find the intersection of 2 dfa which will be a dfa..if there is a final state for the new dfa, then accept it else no.Thus decidable.
correc me if i am worong
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
149 views
Michael Sipser Decidability Problem
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. L = {M | M is a Turing machine and L(M) ∈ TIME(2^n)}
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
User Avatar
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
149 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
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
153 views
Decidability and undecidability
How is equality problem for DCFL decidable?
How is equality problem for DCFL decidable?
User Avatar
Link Copied!