Tue, 30 Mar 1993 11:41:02 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: | 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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.