edited by
461 views
0 votes
0 votes
  1. Use the languages $A=\{a^{m}b^{n}c^{n}|m,n\geq 0\}$ and $B=\{a^{n}b^{n}c^{m}|m,n\geq 0\}$ together with $\text{Example 2.36}$ to show that the class of context-free languages is not closed under intersection.
  2. Use part $(a)$ and $\text{DeMorgan’s law (Theorem 0.20)}$ to show that the class of context-free languages is not closed under complementation.
edited by

1 Answer

Related questions

2 votes
2 votes
1 answer
2
admin asked Oct 12, 2019
310 views
Let $B = \{a^{i}b^{j}c^{k}\mid i,j,k \geq 0\: \text{and}\: i = j\: \text{or}\: i = k \}$. Prove that $B$ is not a DCFL.
0 votes
0 votes
1 answer
4