equivalent grammars


Two formal grammars G1=(Σ1,N1,P1,σ1) and G2=(Σ2,N2,P2,σ2) are said to be equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath if they generate the same formal languages:

L(G1)=L(G2).

When two grammars G1 and G2 are equivalent, we write G1G2.

For example, the languagePlanetmathPlanetmath {anb2nn is a non-negative integer} over T={a,b,c} can be generated by a grammar G1 with three non-terminals x,y,σ, and the following productions:

P1={σλ,σxσy,xa,yb2}.

Alternatively, it can be generated by a simpler grammar G2 with just the starting symbol:

P2={σλ,σaσb2}.

This shows that G1G2.

An alternative way of writing a grammar G is (T,N,P,σ), where T=Σ-N is the set of terminals of G. Suppose G1=(T1,N1,P1,σ1) and G2=(T2,N2,P2,σ2) are two grammars. Below are some basic properties of equivalence of grammars:

  1. 1.

    Suppose G1G2. If T1T2=, then L(G1)=.

  2. 2.

    Let G=(T,N,P,σ) be a grammar. Then the grammar G=(T,N,P,σ) where NN is equivalent to G.

  3. 3.

    If (T1,N1,P1,σ1)(T1,N1,P2,σ2), then (T,N,P1,σ1)(T,N,P2,σ2), where T=T1T2 and N=N1N2.

  4. 4.

    If we fix an alphabet Σ, then is an equivalence relation on grammars over Σ.

So far, the properties have all been focused on the underlying alphabets. More interesting properties on equivalent grammars center on productions. Suppose G=(Σ,N,P,σ) is a grammar.

  1. 1.

    A production is said to be trivial if it has the form vv. Then the grammar G obtained by adding trivial productions to P is equivalent to G.

  2. 2.

    If uL(G), then adding the production σu to P produces a grammar equivalent to G.

  3. 3.

    Call a production a filler if it has the form λv. Replacing a filler λv by productions ava and aav using all symbols aΣ gives us a grammar that is equivalent to G.

  4. 4.

    G is equivalent to a grammar G without any fillers. This can be done by replacing each filler using the productions mentioned in the previous section. Finally, if λL(G), we add the production σλ to P if it were not already in P.

  5. 5.

    Let S(P) be the set of all symbols that occur in the productions in P (in either antecedentsPlanetmathPlanetmathPlanetmath or conseqents). If aS(P), then G obtained by replacing every production uvP with production u[a/b]v[a/b] and ba, with a symbol XΣ, is equivalent to G. Here, u[a/b] means that we replace each occurrence of a in u with X.

  6. 6.

    G is equivalent to a grammar G, all of whose productions have antecedents in N+ (non-empty words over N).

Remark. In fact, if we let

  1. 1.

    XXY,

  2. 2.

    XYZT,

  3. 3.

    Xλ,

  4. 4.

    Xa

be four types of productions, then it can be shown that

  • any formal grammar is equivalent to a grammar all of whose productions are in any of the four forms above

  • any context-sensitive grammar is equivalent to a grammar all of whose productions are in any of forms 1, 2, or 4, and

  • and any context-free grammar is equivalent to a grammar all of whose productions are in any of forms 1, 3, or 4.

References

  • 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
Title equivalent grammars
Canonical name EquivalentGrammars
Date of creation 2013-03-22 17:37:17
Last modified on 2013-03-22 17:37:17
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Definition
Classification msc 91F20
Classification msc 68Q42
Classification msc 68Q45
Classification msc 03D05