Mon, 29 Mar 1993 19:38:46 GMT

Related articles |
---|

Formal Language Calculations werts@grover.cecs.csulb.edu (1993-03-29) |

Re: Formal Language Calculations oudelutt@cs.utwente.nl (1993-03-30) |

Re: Formal Language Calculations norvell@csri.toronto.edu (1993-03-30) |

Newsgroups: | comp.compilers,comp.theory |

From: | werts@grover.cecs.csulb.edu (Michael Werts) |

Keywords: | theory, question, parse, comment |

Organization: | Cal State Long Beach |

Date: | Mon, 29 Mar 1993 19:38:46 GMT |

I'm looking for a couple of algorithms:

1. Given a cfg, G, find the "smallest" regular expression, R,

that accepts all the sentences in G.

2. Given regular expressions R1 and R2, determine if their

intersection is nonempty.

If anyone knows of solutions to these problems, I would appreciate

pointers to the appropriate texts and/or papers.

Thanks!

--

MICHAEL WERTS -- werts@csulb.edu

Computer Engineering Computer Science

California State University Long Beach

[I'd think the answer to number 1 would be (a|b|c|...)*, where a, b, c, etc.

are the tokens in the grammar. Yes, it accepts some sentences not in G, but

we all know that you can't recognize a CFG with a regular expression. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.