Question

Can Regular Grammar be ambiguous ?

Answer 1

if a grammar is regular then it will be Context free also [as per chomsky hierarchy] it may be or may be not ambiguous depending on grammar.

as
S->bS|aX
X->bS|aY
Y->aY|bY|^
is regular having regular expression (a+b)*aa(a+b)* and unambiguous

but grammar
S->aS|bS|aX
X->aY
Y->aY|bY|^
is also regular having regular expression (a+b)*aa(a+b)* and ambiguous.[check aaa]

But it is sure any ambiguous regular grammar can be converted into unambiguous regular grammar.

Comments

Is S->aS|Sa|a Regular ??

It contains both left linear and right linear production.

---

nopes, regular grammar must have either right linear production or left linear production but not both.

---

"But it is sure any ambiguous regular grammar can be converted into unambiguous regular grammar. "

say something more about it...

---

@aditya changed the example

@Bhagirathi , if regular grammar is ambiguous, it means that we have corresponding Nondeterministic FA. but equivalent DFA will result in unambiguous grammar. As I think.

---

Because no regular language is inherently ambiguous- no DCFL actually is actually inherently ambiguous. So, we can always find an equivalent grammar (generating the same set of strings) for them which is not ambiguous.

---

So only NCFL, CSL etc will be inherently ambiguous ??

---

Yes. Sure. But are all NCFL inherently ambiguous?

---

I think 'NO'.. Some NCFL may have unambiguous grammar.

---

Language ambiguity always starts form cfl in chomsky hierarchy.it is not possible in regular and dcfl.but grammer ambiguity also possible in regular and dcfl.

---

what about decidability ?? I mean checking whether a regular grammar is decidable or not ?