Ambiguity and transcendence. (English) Zbl 0571.68058

Flajolet, Philippe

Automata, languages and programming, 12th Colloq., Nafplion/Greece 1985, Lect. Notes Comput. Sci. 194, 179-188 (1985).

[For the entire collection see Zbl 0563.00018.]
We establish that several classical context free languages are inherently ambiguous by proving that their counting generating functions, when considered as analytic functions, exhibit some characteristic form of transcendental behaviour.

MSC:

68Q45

Formal languages and automata

Keywords:

context free languages; counting generating functions; analytic functions; transcendental behaviour

Citations:

Zbl 0563.00018