# Collapsing adjacent states in a grammar

I am trying to write a program which can induce a grammar from an example of the code(really more of a corpus than an example).

I'm ignoring the decision problem, because I am doing two things that I foresee bringing that issue into play: Tokens are separated by spaces and any production rule is terminated at the newline character, and the grammar is context-free(not necessarily unambiguous).

However, the grammars being produced are inefficient because the start state goes to things like $$S\rightarrow a bc \vee abcd \vee abce$$ The start rule contains all of the terminals, and it does so without breaking it down into anything more efficient.

Is there an algorithm that can attempt to extract the grammar in a better form(with smaller production rules)?

Or does this attempt turn into something utterly within the decidability problem?

• What algorithm do you use to infer the grammar? If you have $n$ string $\omega_1,\ldots,\omega_n$, then "inferring" the grammer "$S \to \omega_1 \lor \omega_2 \lor \ldots \lor \omega_n$" is trivial, and rather meaningless... – fgp May 4 '14 at 20:16
• That however is the problem, wikipedia does not link to any algorithms that do this other than ADIOS. What it attempts to do is build a table of structures that it has seen, however, in most contexts, it produces a finite grammar which only accepts the input. My algorithm is broken, which would you suggest then? – jaked122 May 4 '14 at 20:19