patternMinor
Can every context free language written as a intersection of another context free language and a regular language?
Viewed 0 times
canwrittenfreeandeveryregularlanguageanotherintersectioncontext
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#33913, answer score: 5
Revisions (0)
No revisions yet.