Question

Compare the language generated by Grammar #2 to the language generated by Grammar #1. How do the two languages compare to each other? (Is one language a proper subset of the other? Does each language contain a string that the other one does not? Do both grammars generate the very same language?)

grammar #1 where S is the start symbol  

S → tV | iC | iV | i

C → tV

V → iC | iV | i

Grammar #2 where S is the start symbol

S → W

W → YW | Y

Y → CV | V

C → t

V → i

Answer 1

we have two grammar,

grammar #1 where S is the start symbol  

S → tV | iC | iV | i

C → tV

V → iC | iV | i

Grammar #2 where S is the start symbol

S → W

W → YW | Y

Y → CV | V

C → t

V → i

we need to generate languages from the given grammars.

There are three rules for the simplification of CFG ( Context Free Grammar).

1. Elimination of useless symbols

2. Eliminate unit productions

3. Eliminate null productions

take the first grammar,

S → tV | iC | iV | i

C → tV

V → iC | iV | i

take  V → i and put this to in place of v

and we get

S → tV | iC | iV | i

C → tV

V → iC | ii | i

again substitute the values in the grammar

S → tii | ti | tiC | itV | i

C → tiC | tii | ti

V → itV | ii | i

S → tii | ti | tiC | itV | i

C → titii | titi | tii | ti

V → itii | iti | ii | i

and finally we get  the language from grammar 1 , L( G1 )

S → tii | ti | tititii | tititi | titii |titi | ititii | ititi | itii | iti | i

Consider the second Grammar

S → W

W → YW | Y

Y → CV | V

C → t

V → i

Rewrite the given grammar by applying the values of  C → t , V → i

S → W

W → YW | Y

Y → ti | i

apply  Y → ti | i into  W → YW | Y

S → W

W →tiW | iW | ti | i

apply values of W into the grammar

S → W

W →titi | tii | iti | ii | ti | i

and finally we get language from grammar 2, L( G₂ )

S → titi | tii | iti | ii | ti | i

Now we have two languages from the given grammar,

L( G₁ ) :  S → tii | ti | tititii | tititi | titii |titi | ititii | ititi | itii | iti | i

L(G₂ ) : S → titi | tii | iti | ii | ti | i

Compare the both languages by using their string. ( titi | tii | iti | ii | ti | i these all strings belongs to L( G₁ ) )

All the strings of the language L(G₂ ) does belongs to language  L( G₁ ) but both languages are not same . So L( G₂ ) is a proper subset of L( G₁ ).