Re: HELP : Algorithm to generate context free grammar

Nitin Shah <lnustoc.cztmb9@eds.com> writes:
> I am looking for an algorithm that will generate context-free
> grammar from given set of strings.


> For example, Given a language set L = {aaabbbbb,aab}.


> One of the grammar is


> G -> AB A -> aA|a B -> b|bB


> So, I am looking for an algorithm that takes set of strings of the
> language as input and gives its context-free grammar.


Unfortunately, there are infinitely many context-free grammars for any
given set of strings (Consider for example adding A->C,
C->D,...,Y->Z,Z->A to the above grammar. You can obviously add as many
pointless rules as you want this way, and the string set doesn't
change). What's worse, there are several reasonable questions that can
be asked about context-free grammars that can be shown to be
undecidable. You can't write down an algorithm which will always tell
you whether two CFGs are equivalent, and under one idealisation of the
grammar learning process (Gold's in Information and Control (10)
447-74, 1967) you can even show that a learning algorithm is
impossible. However, I doubt if this has much to do with what you
really want. If the issue is compact representation of a finite string
set, consider using regular expressions, or (equivalently) finite
state automata.


Chris
--
------------------------------------------------------------------
Email: Chris.Brew@edinburgh.ac.uk
Address: Language Technology Group,
                    HCRC, 2 Buccleuch Place, Edinburgh EH8 9LW
                    Scotland
Telephone: +44 131 650 4631
Fax: +44 131 650 4587
--

Return to the comp.compilers page.
Search the comp.compilers archives again.