RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2009 Number 3(5), Pages 112–116 (Mi pdm139)

Mathematical Foundations of Informatics and Programming

An analitic approach in the theory of context-free languages Greibach normal form

O. I. Egorushkina, K. V. Safonovb

a Krasnoyarsk State Agricultural University, Krasnoyarsk, Russia
b M. F. Reshetnev Siberian State Aerospace University, Krasnoyarsk, Russia

Abstract: Context-free languages are consider as formal power series, which are solutions of the polynomial equations systems with noncommutative variables respectively multiplication. It is suggested to investigate these systems in Greibach normal form, that allows to research it more effectively. Commutative images of languages and defining systems are considered in complex domain.

UDC: 519.682



© Steklov Math. Inst. of RAS, 2025