On the context-free production complexity of finite languages

✍ Scribed by Zsolt Tuza

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 696 KB
• Volume: 18
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(87)80004-5

✦ Synopsis

The following problem is investigated. Let L be a given finite language, LcL,= {ub: I ~o,bsn, of/~}. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions. Among others, max c(L) = O(n'/log n) is proved, and languages satisfying c(L) = IL) are characterized.

In this paper we investigate the behavior of c(L) when LcL,.

Clearly, we may identify this class of languages with the class of loopless directed graphs on n vertices, in a natural way: ab is a directed edge (i.e., an arc from a to 6) if and only if ab is a word in L. According to this one-to-one correspondence, any graph G defines a language L,, and any language L determines a graph CL. Of course, lLGl = I,!?(G)], the number of arcs (directed edges) in G.

Estimates on c(LG) are given in Section 3. We prove

and that the maximum is essentially the same if, instead of context-free productions, we consider regular or context-sensitive (or length increasing) grammars producing