3
$\begingroup$

I'm preparing an Formal language exam, One question from previous year's final is:

Prove or disprove:If L is a context free language, then there exists a language P that is generated by a pure context-free grammar and a regular language R so that $L = P \cap R$.

My solution to this question is quite simple. Assume context-free language P is equal to context free language L, and let regular language R to be $\Sigma^*$, where $\Sigma$ is the alphabet set. $\Sigma^*$ is definitely a regular language. So the answer to this question is yes.

However, I do came up with a more difficult problem. What if I add a limitation $P \neq L?$ Will this statement still hold? I current have no idea about this.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
5
$\begingroup$

The question in the title of your contribution "Can every context free language written as a intersection of another context free language and a regular language?" is the one you answer above, by taking $P=L$ and $R=\Sigma^*$.

However that is not the question you quote from your test: "If $L$ is a context free language, then there exists a language $P$ that is generated by a pure context-free grammar and a regular language $R$ so that $L=P\cap R$." This additionally requires $P$ to be pure context-free, that is, generated by a grammar that has no dictinction between terminals and nonterminals.

Let $G$ be a context-free grammar with alphabet $\Sigma$ (terminals and nonterminals) and terminal alphabet $\Delta$. As an ordinary context-free grammar the language of $G$ equals $L(G) = \{ w\in \Delta^* \mid S\Rightarrow^* w\}$. Interpreted as pure grammar it cannot "see" terminals and the language is $P(G) = \{ w\in \Sigma^* \mid S\Rightarrow^* w\}$. Or, $L(G) = P(G) \cap \Delta^*$, which gives the answer to your final exam. The elements in $P(G)$ are usually called sentential forms.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you Hendrik, I didn't realize that this "pure" will make such a difference. We didn't talk about pure context grammar in this semester but this might taught in previous year. Thanks again! $\endgroup$
    – jinxuan Wu
    Dec 6, 2014 at 18:27
  • $\begingroup$ Glad I could help you. Good luck with your exam. $\endgroup$
    – Hendrik Jan
    Dec 7, 2014 at 0:51
  • 1
    $\begingroup$ I disagree (mildly) with your first paragraph: to me, "another context-free language" implies that you're not allowed to take $P=L$. OTOH, if that was the intended reading, then $\Sigma^*$ is a CFL that is not the intersection of a CFL distinct from $\Sigma^*$ and a regular language. So maybe I agree with you after all. $\endgroup$
    – David Richerby
    Apr 23, 2015 at 16:55
3
$\begingroup$

If you are allowed to change the alphabet, then the answer is trivially yes. For example, let $\Sigma$ be the original alphabet, and let $\alpha$ be a new symbol. Then $P = L \cup \{\alpha\}$ is context-free, and $L = P \cap \Sigma^*$.

If you are not allowed to change the alphabet, then the answer is trivially no. For if you take $L = \Sigma^*$, you must take $P = \Sigma^*$.

What if you are not allowed to change the alphabet and $L \neq \Sigma^*$? Again the answer is trivially yes. Choose some word $w \notin L$. Then $P = L \cup \{w\}$ is context-free and $R = \overline{\{w\}}$ is regular, and $L = P \cap R$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.