Are Type 3 sets closed under the union operation? Prove it using a grammar-based argument.

Ansesr:

Type 3 grammars are also known as regular grammars.

Type 3 grammars are CLOSED under union.

Proof:-

A regular grammar (or type 3 grammar) is defined as:-

a grammar with productions of the form:-

A -> aB | c

where a and c are terminals. A and B are variables.

To prove that type 3 grammars are closed under union, it is sufficient to give a method to construct a type 3 grammar for union of two type 3 grammars:-

Suppose there are two type 3 grammars, G1 and G2 with start symbols S1 and S2 respectively.

Then a new grammar G corresponding to union of G1 and G2 can be constructed as follows:-

Terminals in G = Terminals in G1 U terminals in G2

Variables = Variables in G1 U Variables in G2 U {S}

Productions = All productions in G1 or G2 along with some new productions:-

S ->  α

where  α appears in RHS of production of the form S1 ->  α or S2 ->  α

Start Symbol = S

Since  α appears in RHS of some production of G1 or G2; G1 and G2 are type 3 grammars, G will also be a type 3 grammar.

Also G will accept any string that is accepted by G1(start symbol S1 ) or G2(start symbol S2).

Thus, type 3 grammars are closed under union.

Example:-

G1:- S1 -> aA, A-> a

G2:- S2 -> bS2, S2-> b

G:- S-> aA | bS2 | b, S1->aA, A->a, S2->bS2 | b

Assuming that the variables used in G1 and G2 are different. If they are same, just rename them.