Production Rules and Strings

As we know, every grammar generates a specific language. Each grammar holds some rules, which are called Production Rules. Strings are generated by using production rules. Let’s explain both Production Rules and Strings.

What is a string?

The string is a part of the language. Grammar produces strings through its production rules. The length of a string is denoted as |w|, where w is the string. There may be multiple strings in a language, including an empty string represented by epsilon (ε) or lambda (λ).

The following language contains four strings

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

Representation: (w|w€ L) 

Number of Strings

If Σ{a, b}

The number of Strings (length 2) will be {aa,ab, ba, bb}. Length of String |w| = 2. Possible Number of Strings = 4.

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

Production Rule

A production rule is represented by the letter P. Here are some examples of production rules:

P: S → aSb / ∈

The above production rule can be written as

• S → aSb
• S → ∈

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

∈, ab, aabb, aaabbb, …….

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

The language with its grammar produces strings using production rules that are represented below.

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