The Definition of Regular Languages

Posted by AraK on Stack Overflow See other posts from Stack Overflow or by AraK
Published on 2010-05-21T22:11:32Z Indexed on 2010/05/21 22:50 UTC
Read the original article Hit count: 274

Good Day,

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.

Thanks,

© Stack Overflow or respective owner

Related posts about computer-science

Related posts about grammar