For all languages A and B, if A and are not context-free, then A union B is not

Question

For all languages A and B, if A and are not context-free, then A union B is not context-free. This statement is TRUE/FALSE (circle your answer). If you answered "TRUE, " informally and briefly explain your answer. If you answered "FALSE, " give a simple counterexample. For all languages A and B, if A and B are not context-free, then A intersection B is not context-free. This statement is TRUE/FALSE (circle your answer). If you answered "TRUE, " informally and briefly explain your answer. If you answered "FALSE, " give a simple counterexample. For every language A, if A is not context-free, then A- is not context-free. This statement is TRUE/FALSE (circle your answer). If you answered "TRUE, " informally and briefly explain your answer. If you answered "FALSE, " give a simple counterexample.

Explanation / Answer

A) true
Proof: For given non context-free languages L1 and L2, let
G1 = (N1,T1, P1, S1) and G2 = (N2,T2, P2, S2) be non context-free
grammars where L1 = L(G1) and L2 = L(G2).

B) false

Proof:The languages
L1 = {0m1m0n
: m, n > 0} and L2 = {0m1
n
0
n
: m, n > 0},
are both non context-free but have the context-free intersection
L1 L2 = {0m1m0m : m > 0}.

C)false

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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