Self Doubt : Ambiguity

Question

Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?

Comments

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 ?

---

@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

---

$S\rightarrow aS|Sa|a$ is it regular grammar ?

---

@Shaik Masthan

why not??

it is generating $L=a^{+}$

---

V->V.T* | T  or V -> T*V|T are the rules but V ->V.T* | T*V|T are not the rule

---

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?

---

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.

---

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.

---

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?

---

I don't think linear grammar is always unambiguous. Some CFG are linear and they are ambiguous.

---

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 ?

 

---

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 .

---

it is regular language and also  ambiguous . but there exist a unambiguous grammar

but doesn't one unambiguous grammar makes the whole language unambiguous?

---

but every regular grammar is either left linear or right linear.

and every right linear grammar and left linear grammar is unambigous.

Answer 1

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