Search code examples
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

    • S, or
    • 00S2, or
    • Y, or
    • nothing.

    In other words, you read production rules as follows:

    • → means "can be replaced with".
    • | means "or"
    • ε means "nothing" (Replacing a symbol with nothing means deleting it from the current string.)

    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.)