Select Page

# Production Rules and Strings

As we Know every Grammar generates a specific language. And each Grammar holds some rules which are called Production Rules. By using production rules strings are generated. Let explain both Production Rules and Strings

## What is string?

String is a part of language. Grammar produce strings through its production rules. String is generally denoted as w and length of a string is denoted as |w|. There may be many strings, a language with Empty string represented as ebsilon (ε) or lamda (λ).

Suppose a language with four strings is given below

L(G) = {a, bb, abc, b}

Representation: (w|w€ L)

### Number of Strings

If Σ{a, b}

Number of Strings (of length 2) will be

a   a

a   b

b   a

b   b

Length of String |w| = 2

Possible Number of Strings = 4

Conclusion: For alphabet {a, b} with length n, number of strings can be generated = 2n.

## Production Rule

Production rule is denoted by P. Examples of production rules is given below

P: S → aSb / ∈

Then above production rule can be written as

• S → aSb
• S → ∈

The Production Rule (P: S → aSb / ∈) can generate the following

∈, ab, aabb, aaabbb…….

So, all above symbols are strings which are generated through production rules.

The language with grammar, generates the strings through production rules is represented as below

L(G) = { ∈, ab, aabb, aaabbb…….} = L = { anbn , n>=0 }

Help Other’s By Sharing…