Generating functions of ambiguous regular languages are still rational?

49 Views Asked by At

The Chomsky-Schützenberger theorem states that any context-free unambiguous language admits an algebraic generating function. For unambiguous regular languages, the generating function is always rational. However, there are ambiguous regular grammars, for example:

$A \to abA \ |\ aB$

$B \to \epsilon \ | \ baB$

Then $ababa$ can be parsed as either $(ab)(ab)a\epsilon$ or $(ab)a(ba)\epsilon$, which is ambiguous.

I wonder if such ambiguous regular languages admit a rational or an algebraic generating function. If so, how can I prove that?

1

There are 1 best solutions below

0
On BEST ANSWER

There are no inherently ambiguous regular languages, see https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous.

As such every regular language admits a rational generating function.