Re: Formal Language Calculations

werts@grover.cecs.csulb.edu (Michael Werts) writes:
|> 1. Given a cfg, G, find the "smallest" regular expression, R,
|> that accepts all the sentences in G.


What is the meaning of 'smallest' here? If you really mean the smallest
*expression*, this must be (a|b|c|...)* indeed, as John states below. If
you want to have the smallest regular *set* that is a superset of the
context-free language, then I'd be very interested in the algorithm as
well, because it does not exist ;=}.


Proof: Take some CFG G and regular expression R. Let R be such that L(R)
is a superset of L(G) and L(R) is minimal, that is, there is no regular
expression R' such that L(R') is a superset of L(G) and L(R') is a
*proper* subset of L(R).


First, suppose that L(G) is not equal to L(R). Then, L(G) is a proper
subset of L(R). Then, take some string w from L(R)-L(G). Then,
obviously, L(R)-{w} is also regular and a superset of L(G). But this
contradicts our assumption that L(R) is minimal.


So, we must have L(G)=L(R) in all cases. And this is not possible,
because there are CFGs that do not generate a regular set.


|> 2. Given regular expressions R1 and R2, determine if their
|> intersection is nonempty.


Just build the automaton of L(R1) \intersect L(R2) in the obvious way (the
new state set is cartesian product of both old ones).
----------------------------------------------------------------------
Paul Oude Luttighuis phone: +31 53 893776
Department of Computer Science email: oudelutt@cs.utwente.nl
University of Twente fax: +31 53 315283
P.O. Box 217
7500 AE Enschede
The Netherlands
--

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