Tue, 30 Mar 1993 19:07:35 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 |

From: | norvell@csri.toronto.edu (Theo Norvell) |

Keywords: | theory, parse |

Organization: | CSRI, University of Toronto |

References: | 93-03-121 |

Date: | Tue, 30 Mar 1993 19:07:35 GMT |

I hope this isn't Michael's homework.

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

As John pointed out, you probably want that it accepts all and only

sentences in L(G). Also, let's assume L(G) is regular.

This problem is PSPACE-complete.

Proof: Transformation from regular-expression non-universality.

0 Read a regular expression S on alphabet Sigma

1 Find an equivalent grammar G

2 Find the smallest regular expression R for G

3 If R = (a|b|c|...)* where Sigma = {a, b, c, ...} then S is

universal.

Of course there might be heuristic approaches or approaches that work well

for small grammars.

See Garey and Johnson, Computers and Intractability.

*>2. Given regular expressions R1 and R2, determine if their*

*> intersection is nonempty.*

This should work: Convert R1 and R2 to NFAs N1 = (Q1, Sigma, d1, q1, F1)

and N2 = (Q2, Sigma, d2, q2, F2), removing all empty transitions.

Construct N = (Q, Sigma, d, q, F) as

Q = Q1 x Q2 (Cartesian product)

q = (q1, q2)

(p1, p2) in d(x) iff p1 in d1(x) and p2 in d2(x)

(p1, p2) in F iff p1 in F1 and p2 in F2

Now see if any p in F is reachable from q.

See Hopcroft and Ullman, Intro to Automata Theory, Languages, and

Computation.

Theo Norvell

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.