4
$\begingroup$

I have a context-free language $L(G)$. I'm reading in a book that $L(G') = L(G) - \{{\epsilon}\}$ is context-sensitive but I cannot find a proof or confirmation of this fact; moreover, in other texts the production $S\to\epsilon$ is allowed (as long $S$ isn't on the right hand side of any production) I'm quite confused.

The book is Formal Models of Computation: The Ultimate Limits of Computing by Arthur Charles Fleck and the passage in question says:

Given two context free grammars $G_1$ and $G_2$ first determine if $\epsilon\in L(G_1)$ and $\epsilon\in L(G_2)$. If so, $L(G_1)\cap L(G_2) \neq \emptyset$, otherwise $L(G_1) - \{{\epsilon}\}$ and $L(G_2) - \{{\epsilon}\}$ are context-sensitive.

Maybe what the book says is that they are also context sensitive (since the set of context-free languages is properly contained in the set of the context-sensitive)?

Improve this question
$\endgroup$
  • $\begingroup$ @D.W. $L(G)$ is a generic context-free language, and $L(G')$ is $L(G)$ minus the empty string. $\endgroup$ – Crysis85 Jul 27 '15 at 17:26
  • 1
    $\begingroup$ What do you mean by "$\otimes$"? Do you mean $\emptyset$, the empty set? And, yes, the passage just says that the languages are context-sensitive; it doesn't say they're not also context-free. In a sense, you can read it as "the languages are no worse than context-sensitive." $\endgroup$ – David Richerby Jul 27 '15 at 17:51
  • $\begingroup$ @David Richerby yes empty set, sorry, couldn't find the correct symbol. I get it now $\endgroup$ – Crysis85 Jul 27 '15 at 18:41
  • $\begingroup$ This is actually a very reasonable question, but hard to understand and answer unless one has all the facts. Hence the first comment by @D.W. was very effective in improving it so that it could get an answer. I wish more users would understand how much complete information is important, not just what they think is important. $\endgroup$ – babou Jul 27 '15 at 20:45
  • $\begingroup$ When you cannot find the proper symbol for writing your text, it can be legitimate to use another one, such as $\otimes$ instead of $\emptyset$. But in such as case, you must warn the reader, not count on similarity for the reader to understand. This is not just for this site, but a general rule. ( CC @DavidRicherby) $\endgroup$ – babou Jul 27 '15 at 20:50
4
$\begingroup$

Saying that CF grammars are properly contained in CS grammars is not quite correct, at least according to some authors (Hopcroft-Ullman 1979, page 223). Their reason is that the CS languages cannot contain the empty word $\epsilon$, at least according to a strict definition of what a CS grammar is: the right-hand side must be at least as long as the left-hand side. Other definitions of CS grammars, such as given in wikipedia, do allow the rule $S\to\epsilon$, provided $S$ never appears in a right-hand side. The purpose is to allow CS languages to contain the empty word, so that they define the same family of languages as the linear bounded automata (LBA). And it also makes CF languages a subset of CS languages.

Context-free (CF) languages can contain the empty word.

Thus, for an author belonging to the strict school (no $\epsilon$ in CS languages), only $\epsilon$-free CF languages are contained in the CS languages.

From what I read in your question, my understanding is that the authors of your book belong to the strict school. So they will not consider a CF language as CS, unless they first remove the empty word, which does not change their CF character as shown in the answer by D.W. that indicates how to obtain the CF grammar $G'$ from the CF grammar $G$.

Apparently the author is analyzing the intersection of two CF grammar, and wants to use the fact that (for him) $\epsilon$-free CF languages are contained in the CS languages. So he considers separately the case when the intersection contains $\epsilon$, and the case when it does not contains it. If it does no contain it, he can remove it from the two languages, and then consider them CS languages, for whatever he is doing.

That is my explanation of what you are reading. Of course, a larger piece of context would help ascertain that view. Or even better, the definition of CS language they give.

Improve this answer
$\endgroup$
  • $\begingroup$ CFL not a subset of CSL seems to conflict some with the chomsky hierarchy where CFLs are a (proper) subset of CSLs. afaik, apparently the "most natural" defn of CSLs seems to support this hierarchy. maybe hopcroft/ ullman 1979 is old wrt this issue & predates concept of chomsky hierarchy & CSL defn has been normalized better since then? $\endgroup$ – vzn Jul 29 '15 at 15:22
  • 1
    $\begingroup$ @vzn The "concept" of Chomsky Hierarchy dates back, according to Wikipedia, to Chomsky'original paper on phrase-structure grammars. From reading this 1956 paper, it is not even clear that the status of the empty word (U) was clear in Chosmsky's mind (p. 117). Though he sees it as the identity on strings, he also considers it as a special symbol (rather than a meta-symbol). He does precludes using it as replacement, thus excluding it from any language in the hierarchy. Hopcroft-Ullman 1969 uses Type n grammars (n∈[0-4]), allow ϵeverywhere (p.15), but does not use the name "Chomsky Hierarchy". $\endgroup$ – babou Jul 30 '15 at 9:52
2
$\begingroup$

It's a straightforward to show that if $L_1$ is context-free, then $L_2 = L_1 \setminus \{\epsilon\}$ is also context-free. Take any context-free grammar for $L_1$, then find nullable variables (variables that can derive $\epsilon$). In particular, the following is a basic theorem that's useful:

Theorem. If $L$ is a context-free language, then $L \setminus \{\epsilon\}$ has a context-free grammar with no $\epsilon$-productions.

My claimed result follows immediately from the theorem. The proof of the theorem follows by building an algorithm to identify all nullable variables of the context-free grammar, then change them so they can no longer derive $\epsilon$ and fix up the rules. You can find the detailed proof in standard textbooks: it goes under the name of removing $\epsilon$-productions.

Improve this answer
$\endgroup$

Your Answer

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

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