Is λ allowed in Deterministic CFG?

Question

I have a non-deterministic CFG that says

S-> aS | aB | bB | λ;
B-> bB | λ

And I'm asked to create a deterministic CFG from that. I understand why the given CFG is non-deterministic because it contains

S-> aS | aB | [...]

But I think what I'm confused is why in my book does it say that A->λ productions are not allowed? I can't think of any other way to keep the solution a deterministic CFG if λ is not allowed.

[EDIT] The book defines deterministic CFG

"To recognize the full set of context-free languages, we require a non-deterministic stack automaton. We saw that any NFA could be replaced by an equivalent DFA but we cannot do this in the case of non-deterministic stack automaton. It is our good fortune that practical programming languages can be adequately described by deterministic CFG"

"We said that in Type 1 grammars, the nonterminal on the left-hand side could be replaced by ε. Since these restrictions are cumulative as we go from one level of the hierarchy to the next, this implies that Type 2 grammars may not have productions of the form A-> ε. In fact, we will see many CFGs have such productions, we must allow such productions as exceptions to the Type-1 restriction." - Introduction to Compiler Construction by Thomas W. Parsons

Answer 1

Oh. That's a disappointing explanation in the book. I suggest that you don't rely on that explanation for precise details about deterministic CFGs; it looks like it is trying to give intuition, but it is not the place to look for formal definitions, rigor, or precision. I'd suggest looking at a well-regarded automata theory textbook. (Hopcroft, Motwani, and Ullman's book is well-regarded, though I haven't checked specifically whether it has a definition of deterministic CFG. Sipser is also good.)

As Yuval says, the definition of a deterministic CFG is not completely standard. I think I've seen multiple slightly different definitions. Here are the basic concepts:

• The definition of a deterministic pushdown automaton is standard. (There are two variants, acceptance by final state and acceptance by empty stack; normally we use acceptance by final state, unless otherwise specified.)

• The definition of a deterministic context-free language is standard: $L$ is a deterministic context-free language if it is accepted by any deterministic pushdown automaton.

• The definition of a deterministic context-free grammar is not completely standard. If I remember correctly, I think it can be defined in a few slightly different ways. The one thing everyone agrees on is that, no matter what definition of deterministic CFGs you pick, the languages that can be accepted by such grammars should be exactly the deterministic context-free languages. But there are a few different ways to place restrictions on a CFG, while achieving this property. In particular, you can define deterministic CFGs in a way that allows it to include $A \to \lambda$ rule. Perhaps there is another definition that doesn't allow such rules, and perhaps your textbook has that definition in mind. Since your book doesn't state a precise definition, one can only guess. Perhaps the author decided that the exact specifics aren't too important, for the book's purposes.

The bottom line is: your question seems perfectly reasonable. I don't think the problem is that you lack understanding of something important. I think the problem is that the textbook is just written in a confusing way, on this particular point.