I have following information:

Alphabet $\Sigma$ , where $\Sigma \cap \{T,U\} = \emptyset $
and language $L = L(G) $ over $\Sigma$ generated by context free grammar $G$.

Then I consider another language $L'$ that is defined as follows

$L' = \{w.a | w \in \Sigma^* \land (w \in L \iff a = T) \land (w \notin L \iff a = U) \}$

Based on this information I have to conclude whether there is an algorithm that can create context free grammar $G'$ so that $L(G') = L'$. If there is no such algorithm I should prove it.

I concluded that there is not such algorithm, since I know that context free languages are not closed against complement, therefore the complement of language can be even context-sensitive language.

If I am right, how do I now write down a proof of it? And I am not right, where did I make a mistake?

  • $\begingroup$ Focusing on whether there is an algorithm in particular seems to be a slightly wrong approach. Instead the core question here is whether $L'$ is necessarily context-free at all. And you seem to be on the right path for proving it's not. What you need to argue now is that if $L'$ is context-free, then $\Sigma^*\setminus L$ would also be. $\endgroup$ – Henning Makholm Nov 20 '16 at 13:08
  • $\begingroup$ @HenningMakholm I got to the point where I realized that $L' = L . {T} \cup \overline{\rm L} . {U} $ Based on that I proceeded to realize that union of context-free with complement of non-context free language could result in language that can not be generated by context-free grammar. Is this valid approach, or I'm of the right path now? $\endgroup$ – FanaticD Nov 20 '16 at 15:28
  • $\begingroup$ x @FanaticD: No you're going in the wrong direction -- you would need to assume that $L'$ is already context-free and then prove that if this is the case then $\bar L$ would be that too. A first step would be to intersect with a regular language to get that $\bar L\mathtt U$ would be context-free, but you may need to describe some ad-hoc rewriting of grammars to argue that if $\bar L\mathtt U$ is context-free, then $\bar L$ is context-free too. $\endgroup$ – Henning Makholm Nov 20 '16 at 16:31
  • $\begingroup$ @HenningMakholm Alright, but when I am supposed to write an algorithm so that $L(G') = L'$ where $G'$ is context-free grammar, wouldn't that mean that $L'$ must be generated by context-free grammar, therefore at worst it's context-free or regular? Maybe I could assume that $L'$ is context-free? And to backup my comment theory - given language $L$ of type-2 (Chomsky hierarchy) and a language $L'$ of type-1 or type-0 ("more general" I would say) what will be the type of $L'' = L \cup L'$? $\endgroup$ – FanaticD Nov 20 '16 at 16:39
  • $\begingroup$ Your task is to describe such an algorithm OR prove that it cannot exist. You have already decided that it cannot exiat, so now your task is to prove that. $\endgroup$ – Henning Makholm Nov 20 '16 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.