Re: Formal Language Calculations

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

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