grammargeneric-derivation

How can I derivate these Grammar


G = (V={S,X,Y}, T={0,1,2},P,S)

S -> 0X1
X ->S | 00S2 | Y | ε
Y ->X | 1

The Problem is I don´t know how to derivate numbers..

How can I derivate this here: 00111 ∈ L(G)

And here I have to give a derivation three: 0000121 ∈ L(G)


Solution

  • To do a derivation you start with the start symbol (in this case S) which is the fourth item in the grammar tuple). You then apply the production rules (P) in whatever order seems appropriate to you.

    A production like:

    X → S | 00S2 | Y | ε
    

    means that you can replace an X with

    In other words, you read production rules as follows:

    Everything else is just a possible symbol in the string. You keep doing replacements, one at a time, until you reach the string you are trying to derive.

    Here's a quick example:

    S
     → 0X1      (using S → 0X1)
     → 000S21   (using X → 00S2)
     → 0000X121 (using S → 0X1)
     → 0000121  (using X → ε)
    

    That's it. Nothing complicated at all. Just a bunch of search and replace operations. (You don't need to replace the first occurrence, if there is more than one possibility. You can do the replacements in any order you like. But it's convenient to be systematic.)