# Re: Formal Language Calculations

## oudelutt@cs.utwente.nl (Paul Oude-Luttighuis)Tue, 30 Mar 1993 11:41:02 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: oudelutt@cs.utwente.nl (Paul Oude-Luttighuis) Keywords: theory, parse Organization: University of Twente, Dept. of Computer Science References: 93-03-121 Date: Tue, 30 Mar 1993 11:41:02 GMT

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
--

Post a followup to this message