We can represent questions about context-free languages and regular languages by choosing a standard encoding for context-free grammars (CFG's) and another for regular expressions (RE's), and phrasing the question as recognition of the codes for grammars and/or regular expressions such that their languages have certain properties. Some sets of codes are decidable, while others are not.

In what follows, you may assume that G and H are context-free grammars with terminal alphabet {0,1}, and R is a regular expression using symbols 0 and 1 only. You may assume that the problem "Is L(G) = (0+1)*?", that is, the problem of recognizing all and only the codes for CFG's G whose language is all strings of 0's and 1's, is undecidable.

There are certain other problems about CFG's and RE's that are decidable, using well-known algorithms. For example, we can test if L

(G) is empty by finding the pumping-lemma constant n for G, and checking whether or not there is a string of length n or less in L(G). It is not possible that the shortest string in

L(G) is longer than n, because the pumping lemma lets us remove at least one symbol from a string that long and find a shorter string in L(G).

You should try to determine which of the following problems are decidable, and which are undecidable:

Is Comp(L(G)) equal to (0+1)*? [Comp(L) is the complement of language L with respect to the alphabet {0,1}.]

Is Comp(L(G)) empty?

Is L(G) intersect L(H) equal to (0+1)*?

Is L(G) union L(H) equal to (0+1)*?

Is L(G) finite?

Is L(G) contained in L(H)?

Is L(G) = L(H)?

Is L(G) = L(R)?

Is L(G) contained in L(R)?

Is L(R) contained in L(G)?

Then, identify the true statement from the list

a) "Is L(G) = L(R)?" is decidable.

b) "Is L(G) union L(H) equal to (0+1)*" is undecidable.

c) "Is L(R) contained in L(G)?" is decidable.

d) "Is L(G) = L(H)?" is decidable.

Plz can someone explain me step by step