Formal Language Calculations

werts@grover.cecs.csulb.edu (Michael Werts)
Mon, 29 Mar 1993 19:38:46 GMT

          From comp.compilers
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)
| List of all articles for this month |
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.