# Re: Formal Language Calculations

## norvell@csri.toronto.edu (Theo Norvell)Tue, 30 Mar 1993 19:07:35 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 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