|Formal Language Calculations firstname.lastname@example.org (1993-03-29)|
|Re: Formal Language Calculations email@example.com (1993-03-30)|
|Re: Formal Language Calculations firstname.lastname@example.org (1993-03-30)|
|From:||email@example.com (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.
MICHAEL WERTS -- firstname.lastname@example.org
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]
Return to the
Search the comp.compilers archives again.