2 votes 2 votes Given a finite automata M, is it the minimum state FA accepting L(M) is this problem decidable, if yes then why? Theory of Computation gateforum-test-series theory-of-computation + – charul asked Jan 11, 2018 charul 235 views answer comment Share Follow See 1 comment See all 1 1 comment reply Anu007 commented Jan 11, 2018 reply Follow Share yes it is decidable, An algorithm like that: check if two states are equal or not , if you find any two states are equal then it says yes else no. If you can find the Algorithm for any problem to solve then TM can also solve that problem. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes All the properties of Regular Languages and Finite Automata are decidable and algorithms possible. Your question falls in the category of membership problem of regular languages, which is decidable. Gupta731 answered Oct 10, 2018 Gupta731 comment Share Follow See all 0 reply Please log in or register to add a comment.
