0 votes 0 votes Does ambiguity problem is decidable in regular grammar(right linear grammar)? Theory of Computation theory-of-computation finite-automata + – sandyoverflow asked Oct 20, 2018 sandyoverflow 1.9k views answer comment Share Follow See 1 comment See all 1 1 comment reply Verma Ashish commented Oct 21, 2018 reply Follow Share https://cstheory.stackexchange.com/questions/19102/ambiguity-in-regular-and-context-free-languages 2 votes 2 votes Please log in or register to add a comment.
2 votes 2 votes No. In case of context free languages ambiguity problem is undecidable. But coming to regular grammar it is decidable. Verma Ashish answered Oct 20, 2018 Verma Ashish comment Share Follow See all 2 Comments See all 2 2 Comments reply sandyoverflow commented Oct 20, 2018 reply Follow Share Would you like to proof it in a casual way?Because i didn't get any exact explanation. 0 votes 0 votes Verma Ashish commented Oct 20, 2018 reply Follow Share Refer this https://gateoverflow.in/124706/peter-linz-5-1?show=124741#c124741 Read all the comments. it might clear your doubts. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes YES, ambiguity of regular is decidable, inface it is trivially decidable. It can be done using product automata or tree method. manikantsharma answered Mar 11, 2020 manikantsharma comment Share Follow See all 0 reply Please log in or register to add a comment.