3 votes 3 votes Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example? Theory of Computation theory-of-computation finite-automata ambiguous regular-language context-free-language context + – logan1x asked May 10, 2019 logan1x 1.2k views answer comment Share Follow See all 14 Comments See all 14 14 Comments reply Shaik Masthan commented May 10, 2019 reply Follow Share i have a doubt that, is ambiguity present in Regular grammars ? i mean to say, there is only one path to accept the strings which are belongs to Regular languages/grammars, then how it leads to ambiguity ? am i missing something ? 0 votes 0 votes srestha commented May 10, 2019 reply Follow Share @Shaik Masthan $S\rightarrow aS|Sa|a$ LR parser contains regular grammar. @logan1x how far I know ambiguity always undecidable, if it is regular or CFL 0 votes 0 votes Shaik Masthan commented May 10, 2019 reply Follow Share $S\rightarrow aS|Sa|a$ is it regular grammar ? 0 votes 0 votes srestha commented May 10, 2019 reply Follow Share @Shaik Masthan why not?? it is generating $L=a^{+}$ 0 votes 0 votes Shaik Masthan commented May 10, 2019 reply Follow Share V->V.T* | T or V -> T*V|T are the rules but V ->V.T* | T*V|T are not the rule 1 votes 1 votes srestha commented May 10, 2019 reply Follow Share ohk , yes. Left linear and right linear grammar cannot present at the same time in regular grammar. @Shaik Masthan Then if I generate a grammar like $S\rightarrow aS|Sa|a$ then which grammar is it?? Is it directly comes under a CFL?? Moreover why cannot we generate left linear and right linear at the same time?? What is problem with it? 0 votes 0 votes logan1x commented May 11, 2019 reply Follow Share how far I know ambiguity always undecidable, if it is regular or CFL ambiguity is not always undecidable, In case of regular grammar(right linear), ambiguity is decidable but Not in case of context free grammar. I have a doubt why it is decidable in case of regular. 0 votes 0 votes vizzard110 commented Jul 11, 2019 reply Follow Share NO, it is not a regular grammar. As given in Peter Linz " A regular grammar is one that is either right-linear or left-linear". The given grammar is linear grammar. 1 votes 1 votes logan1x commented Jul 16, 2019 reply Follow Share As given in Peter Linz " A regular grammar is one that is either right-linear or left-linear". The given grammar is linear grammar. So Is linear grammer is always unambigious? If yes then can you tell me reason behind it? 0 votes 0 votes vizzard110 commented Jul 16, 2019 reply Follow Share I don't think linear grammar is always unambiguous. Some CFG are linear and they are ambiguous. 0 votes 0 votes logan1x commented Jul 18, 2019 reply Follow Share Okay understood. what is your views about my parent question i.e. Why is ambiguity in regular language is decidable and not decidable in CFL ? 0 votes 0 votes abhishekmehta4u commented Jul 18, 2019 reply Follow Share if you have a regular language then there must exist a unambiguas grammar . so we can say ambiguity problem of regular language is decidable. example S---> aS/Sa/a it is regular language and also ambiguous . but there exist a unambiguous grammar S-->as/a . 0 votes 0 votes logan1x commented Jul 21, 2019 reply Follow Share it is regular language and also ambiguous . but there exist a unambiguous grammar but doesn't one unambiguous grammar makes the whole language unambiguous? 0 votes 0 votes Spidey_guy commented Dec 31, 2019 reply Follow Share but every regular grammar is either left linear or right linear. and every right linear grammar and left linear grammar is unambigous. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes There is no inherent ambiguity in regular languages. Every regular language is convertible to an NFA. An NFA is convertible to a DFA. A DFA is conertible to a minimal DFA. The minimal DFA is unique. https://cs.stackexchange.com/questions/63171/how-to-prove-that-minimal-dfa-is-unique Joey answered Jan 3, 2021 Joey comment Share Follow See all 0 reply Please log in or register to add a comment.