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 }