27 Feb 1996 16:42:48 -0500

Related articles |
---|

HELP : Algorithm to generate context free grammar lnustoc.cztmb9@eds.com (Nitin Shah) (1996-02-26) |

Re: HELP : Algorithm to generate context free grammar torbenm@diku.dk (1996-02-27) |

Re: HELP : Algorithm to generate context free grammar chrisbr@cogsci.ed.ac.uk (1996-02-27) |

From: | chrisbr@cogsci.ed.ac.uk (Chris Brew) |

Newsgroups: | comp.theory,comp.compilers |

Date: | 27 Feb 1996 16:42:48 -0500 |

Organization: | Centre for Cognitive Science, University of Edinburgh |

Distribution: | inet |

References: | 96-02-306 |

Keywords: | parse |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.