In this article, we have created a Grammar for the Language aⁿbⁿcⁿ in Theory of Computation. We have explored the possibility of Regular Grammar, Context Free Grammar and Context Sensitive Grammar.

Table of contents:

1. Problem Statement: Grammar for aⁿbⁿcⁿ
2. Can we create a Regular Grammar?
3. Can we create a Context Free Grammar?
4. Context Sensitive Grammar

Prerequisite: Regular Grammar, Context Free Grammar and Context Sensitive Grammar.

Let us get started with the development of a Grammar for aⁿbⁿcⁿ.

Problem Statement: Grammar for aⁿbⁿcⁿ

Create a Grammar which can generate a Language L where:

L = { aⁿbⁿcⁿ | n >= 1}

Note:

• We are adding same number of 3 characters a, b and c in sorted order.
• We are tracking three information: count of a, count of b and count of c.

Can we create a Regular Grammar?

No, a Regular Grammar cannot create this language because this Language L requires us to keep track of 3 information while Regular Grammar can keep track of 1 information at most.

Therefore, Regular Grammar is weak to create the given Language.

Can we create a Context Free Grammar?

Context Free Grammar is stronger than Regular Grammar but still it cannot be used to generate the given language.

A Context Free Grammar cannot create this language because this Language L requires us to keep track of 3 information while Context Free Grammar can keep track of 2 information at most.

Therefore, Context Free Grammar is weak to create the given Language.

Context Sensitive Grammar

Consider a Language where aⁿbⁿcⁿ. For this, we need Context Sensitive Grammar.

We cannot generate this language with Context Free Grammar because it keeps track of only two properties while in this case, we have 3 properties that is count of a, b and c. Similarly, Regular Grammar cannot be used as it is weaker than Context Free Grammar and tracks only 1 property.

The rules of Context Sensitive Grammar for this language will be:

S -> abc
S -> A
A -> aABc
A -> abc
cB -> Bc
bB -> bb

For example, if N=3, then the resultant string will be aaabbbccc and the derivation using our Context Sensitive Grammar will be:

S->A
-> aABc
-> aaABcBc (using Rule: A->aABc)
-> aaabcBcBc (using Rule: A->abc)
-> aaabBccBc (using Rule: cB->Bc)
-> aaabBcBcc (using Rule: cB->Bc)
-> aaabbcBcc (using Rule: bB->bb)
-> aaabbBccc (using Rule: cB->Bc)
-> aaabbbccc (using Rule: bB->bb)

With this, we have our resultant string aaabbbccc.

Note, this Language cannot be generated by Context Free Grammar or Regular Grammar but this is possible with Context Sensitive Grammar which is more powerful.

With this article at OpenGenus, you must have a strong idea of the Context Sensitive Grammar used to create the Language aⁿbⁿcⁿ.