Definition of regular languages

Question

I 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 this definition is in this book. On page (789), I rephrase the definition:

Type 3 grammars are defined as:

w1 --> w2 

Where w1 is not a terminal, and w2 has the form:

 w2 = aB w2 = a 

Where B is not a terminal and a is a terminal. A special case is when w1 is the start character and w2 is the lambda (empty string):

 w1 = S S --> lambda 

Two questions that I could not find an answer to. First, why w2 cannot have the form Ba . Secondly, why lambda is allowed only for the initial character . The book says that regular languages ​​are equivalent to a finite state machine, and it is easy to see that we can build FSA for both cases. I looked at other resources, and these restrictions do not exist in these resources.

Answer 1

First, why w2 cannot have the form Ba.

Take the following grammar with the letter W as the starting character:

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

it spawns {a ⁿ b ⁿ : n natural}, which is not a regular language. Therefore, this limitation is important if you want to generate only ordinary languages. Alternatively, you can enable w2 = Ba, but prohibit rules of the form w2 = aB - this also gives regular languages. This grammar builds the word back.

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

Secondly, why lambda is allowed only for the initial character.

This is not a mandatory limitation.

You can exclude all uses of lambda for nonterminal characters: take some rule W → lambda, delete it and replace all the rules U → aW with U → aW and U → a. Obviously, you cannot rule out the use of lambda for a terminal character (the language will no longer generate an empty word).

So, every type 3 grammar that uses lambda in many places can be “normalized” to a grammar that uses lambda only for the start character.