The Definition of Regular Languages

Question

I have tried, and burned my brain to understand the definition of Regular Languages in Discrete Mathematics and its Applications(Rosen) without reaching the goal of understanding why the definition is like that in this book. On page(789), I am rephrasing the definition:

Type 3 grammars are defined as:

w1 --> w2

Where w1 is a non-terminal, and w2 is of the form:

w2 = aB
w2 = a

Where B is a non-terminal, and a is a terminal. A special case is when w1 is the starting symbol and w2 is lambda(the empty string):

w1 = S
S --> lambda

Two questions I couldn't find an answer for. First, Why can't w2 be of the form Ba. Second, Why lambda is only allowed for the starting symbol only. The book states that, regular languages are equivalent to Finite State Automaton, and we can easily see that a we can build FSA for both cases. I took a look at other resources, and these restrictions don't exist in these resources.

Renitarenitent

Did you check on whether the book has any errata? – Calcification

@David M No, I didn't do that but I will do it now. Interestingly, on page(795) exercise#19 (i, j) exactly are solved according to this definition. – Renitarenitent

I just have checked the errata of the 6th ed. and without finding any thing:highered.mcgraw-hill.com/sites/dl/free/0072880082/299357/… – Renitarenitent

Answer 1

First, Why can't w2 be of the form Ba.

Take the following grammar with W as starting symbol:

W -> lambda
W -> aX
X -> Wb

it generates {aⁿ bⁿ : n natural } which is not a regular language. So this restriction is essential, if you want to generate only regular languages. Alternatively, you may allow w2 = Ba, but forbid rules of kind w2 = aB - this also gives regular languages. That grammar will build a word "backwards".

If you allow both types of rules, you'll get a class known as linear languages.

Second, Why lambda is only allowed for the starting symbol only.

This is not a neccesary restriction.

You may eliminate all uses of lambda for nonterminal symbols: take some rule W -> lambda, remove it, and replace all rules U -> aW with U -> aW and U -> a. Obviously you cannot eliminate use of lambda for terminal symbol (the language won't produce empty word anymore).

So, every type 3 grammar that uses lambda in many places can be "normalized" to a grammar that uses lambda only for the starting symbol.

Weintrob