We can represent questions about context-free languages and regular languages by

Question

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

Explanation / Answer

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

Ans: As l(G)=(0+1)*

By Defination of Complement of CFL, Comp(L(G)) should not contain (0+1)* and CFL in closed under complementation so this problem is  decidable.

Is Comp(L(G)) empty? decidable

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

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

• Is L(G) finite? decidable

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

• Is L(G) = L(H)?undecidable

• Is L(G) = L(R)? undecidable

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

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

Then, identify the true statement from the list

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.