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: 303
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