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

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