# Tag Info

Every CFL language can be describes as a PDA. Every regular language can be described as a DFA. The orthogonal product of a DFA and PDA can be defined as follows: The new states of the automaton are all $(q_{PDA}, q_{DFA})$. That start state is $(s_{PDA}, s_{DFA})$ and the final states are all $(f_{PDA}, f_{DFA})$ where $f_{PDA}\in F_{PDA}$ and $f_{DFA} \... 1 For your specific question, you are asking to generate a string in$\bar{L} \cap P$. Note that since$L$is regular, so is$\bar{L}$; and note that$P$is context-free. It is known that the intersection of a regular and context-free language is context-free. So, you're asking: given a context-free language, how do we generate a word in that language? ... 0 The relevant set-theoritic relations are $$\mathsf{REXP} = \mathsf{DFSA} = \mathsf{NFSA} \subsetneq \mathsf{CFG} = \mathsf{PDA}.$$ The corresponding Venn diagram consists of two circles, one inside the other. 0 Here is a proof that context-free languages in general, not only regular ones, are not closed against making them prefix-free. Bare with me, as I will try to make it as formal as possible. We will demonstrate that: Theorem 1.$NOPREFIX(L)$are the$u\in L$such that no proper prefix of$u$is in$L$. Context-free languages are not closed under$NOPREFIX$... 1$L_1\circ L_2$can certainly still be non-regular. For example, when$L_1$contains exactly one word. However,$L_1\circ L_2$can be regular, too. Here is an example. Let$L_1=\{\epsilon,0\}$. Let$L_2$be the complement of$\{ 0^n1^n \mid n \gt 0 \}$. As the complement of a non-regular language,$L_2$is not regular while$L_1\circ L_2$, the set of all ... 1 Your second method to arrive at$\phi$is bogus - consider the case where$B$is the empty language. Where you are confused here is you are looking at the difference between the sets of all regular languages and all context free languages, instead of the difference between the two concrete languages. The correct answer is d. None (you can't say anything) ... 2 As for closure under complementation -- consider the following hint: context-free languages are not closed under complementation. Regarding concatenation, this is slightly more tricky, but non-context free languages are not closed under complementation. There are many ways of finding counterexamples for the latter, one is the following "trick": Let$L$... 2 It might be context sensitive as well... example:- let L1=${\{a^n b^n c^m | n>0, m>0\}}$and L2=${\{a^m b^n c^n | m>0, n>0\}}$Here L1 and L2 are context free but L1-L2 will be L1-L2 =${\{a^n b^n c^m | n>0, m>0 \space \& \space n \neq m\}}\$ which is NOT context free.