Sunday, November 30, 2008

S->S means empty

In this weeks lecture danny talked about the context free grammars. 

When danny ask a question about what the grammar S->S, stands for?

My first instinct is if s always return s itself, then s can't be anything that related to repetition which we are frequently used in the regular express, we called it Kleene star. Since Kleene star is out of the consideration, i made a conclusion that S->S represent a finite string.
However, danny said it represent empty. 

I think about it after class, found danny is right.

Here is the thing, since we start at S, and our destination is always S, the trick is S is start point and also a destination point. Thus, that's means you always stay at where you are. Thus, the S->S means empty. 

It may sounds confused by how about S is /epsilon (empty string), actually, in the lecture for FSA, we use /epsilon  to direct start state to another states, if S->S is /epsilon then is contradict with S->S where the destination state S is itself, it doesn't direct to any state other than itself. Thus S->S only should be empty.

Another way to think about this question is there is no other output, i.e. S-> B. Thus if any CFG that doesn't include a end point other than itself, this CFG either never ends or just empty. 

S->S means empty

No comments: