What does =*> mean with regards to context free grammars?

views:

answers:

+4 Q:

What does =*> mean with regards to context free grammars?

I've been reading a couple books/online references about compiler theory, and keep seeing that particular operator coming up every once in a while (as seen here), specifically when the current topic is context free grammars. What does it mean? As well, how does it differ from =>?

Explanations with examples distinguishing => from =*> would be most helpful.

+5 A:

=> means derives in one step while =*> derives in zero or more steps (the reflexive transitive closure of =>).

Firas Assaad 2010-06-13 22:50:52

Oh - that makes sense! Actually, could you clarify how something could be derived in 0 steps?

Cam 2010-06-13 22:51:38

In other words, the `*` modifies `=>` in the same way it modifies items in regular expressions.

Joel Coehoorn 2010-06-13 22:51:44

@incrediman: It's when something derives itself. e.g. 01b =*> 01b (zero steps) vs. 01b =*> 011 (one step)

Firas Assaad 2010-06-13 22:56:53

@Firas: Cool, thanks. (+1)

Cam 2010-06-13 22:58:40

ansaurus

tags:

views:

answers:

What does =*> mean with regards to context free grammars?

related questions