Department of Information Technology

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.

Updated  2014-09-23 10:01:16 by Mohamed Faouzi Atig.