Generating Bounded Languages using Bounded Control Sets
Radu Iosif, VERIMAG Laboratory, France
Date and Time
Thursday, September 24th, 2014 at 15:15.
Polacksbacken, room 4306
We study context-free grammars whose generated language is bounded (that is, subset of some expression w_1∗...w_d* called bounded expression). We investigate the underlying generating process of such language and show that there exists a bounded expression u_1*...u_m* over the production rules, such that the language is generated only by sequences of production rules conforming to the bounded expression. We give an algorithm to compute such a bounded expression, and an upper bound on its running time.