Theory of Automata

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…

Contact Us

Burewala, Vehari, Punjab, Pakistan


Pin It on Pinterest