Ambiguity and transcendence. (English) Zbl 0571.68058

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.


68Q45 Formal languages and automata


Zbl 0563.00018