Construct grammar and find its type

evinda

Well-known member
MHB Site Helper
Hello!!!

I want to construct a grammar for the language $L=\{ a^i b^j \mid i,j \geq 1, i>j\}$. What type of grammar is it?

I have thought to start with the command $S \to aSb$.
Since we can have several times $a,b$ I have thought to continue with the command $S \to aDb$.
Since there have to be more $a$s than $b$s, do we continue with the commands $D \to aD$ and $D \to a$ ?

So is the grammar the following?

S-> aSb
D->a

Klaas van Aarsen

MHB Seeker
Staff member
Hey evinda !!

What is $A$?

MHB Site Helper

Klaas van Aarsen

MHB Seeker
Staff member
D->a
Ah okay.

The word $aaabb$ is part of the language isn't it?
But we can't construct it with those rules can we?

evinda

Well-known member
MHB Site Helper
Ah okay.

The word $aaabb$ is part of the language isn't it?
But we can't construct it with those rules can we?
Oh yes, right!! We cannot construct it with those rules....

We have to reuse S...

I have thought of the following grammar so far:

S->aSb
S->D
D->a

But as I see this is not true, since we cannot get as many b's as we want. Or am I wrong?

Klaas van Aarsen

MHB Seeker
Staff member
Indeed. It is not true.
Additionally we can get $a$ now, which is not in the language either is it?

evinda

Well-known member
MHB Site Helper
Indeed. It is not true.
Additionally we can get $a$ now, which is not in the language either is it?
So the minimum possible power of $a$ is $2$ and of $b$, $1$.

So the initial rule should be this one: S->a^2Sb. Right?
Then S can either get the value ab or a or it finishes.
Is this right?

Klaas van Aarsen

MHB Seeker
Staff member
So the minimum possible power of $a$ is $2$ and of $b$, $1$.

So the initial rule should be this one: S->a^2Sb. Right?
Then S can either get the value ab or a or it finishes.
Is this right?
Sounds about right yes.

evinda

Well-known member
MHB Site Helper
Sounds about right yes.
So is the grammar the following one?

S->a^2Sb
S->ab
S->a
S->λ

Klaas van Aarsen

MHB Seeker
Staff member
But a, ab, and $\lambda$ are not in the language are they?

evinda

Well-known member
MHB Site Helper
But a, ab, and $\lambda$ are not in the language are they?
Oh yes, right!

So is the grammar the following?

S->a^2Db
D->ab
D->a
D->λ

Klaas van Aarsen

MHB Seeker
Staff member
That looks correct to me.

evinda

Well-known member
MHB Site Helper
That looks correct to me.
Great!!! And how do we find what type of grammar it is?

evinda

Well-known member
MHB Site Helper
I have found the following about the possible types of a grammar:

From the above, I understand that if a grammar is of type-2, then it is also of type-1, right?

Also, all the types 1,2,3 are also type 0, right?

As for the type-3 grammars, I haven't understood something... It says that on the left-hand side we have a single nonterimal and at the right-hand side a single terminal, possibly followed by a single nonterminal. Then why is A->abcB allowed, as it stated at the example? Shouldn't we only have rules of the form A->aB? Could you explain it to me?

Klaas van Aarsen

MHB Seeker
Staff member
I have found the following about the possible types of a grammar:
From the above, I understand that if a grammar is of type-2, then it is also of type-1, right?
Maybe, but it does not seem to follow directly from the definition.
That is because I think $\gamma$ can be empty in the type-2 grammar, but must specifically be non-empty in the type-1 grammar.
That depends on how a 'string' is defined though - whether it is allowed to be empty or not.

Also, all the types 1,2,3 are also type 0, right?
I believe so, yes.
We should be able to recursive apply each possible rule and backtrack, making each of the types 1, 2, and 3 recursively enumerable, and therefore a type 0-grammar.

As for the type-3 grammars, I haven't understood something... It says that on the left-hand side we have a single nonterimal and at the right-hand side a single terminal, possibly followed by a single nonterminal. Then why is A->abcB allowed, as it stated at the example? Shouldn't we only have rules of the form A->aB? Could you explain it to me?
It seems to me that they either consider "abc" a single terminal.
Or they imply that $A\to abcB$ can be rewritten as $A\to aA_1,\,A_1\to bA_2,\,A_2\to cB$, after which the condition is satisfied.

However we interpret it, a language that allows $A\to abcB$ will be equivalent to a type-3 grammar,

Evgeny.Makarov

Well-known member
MHB Math Scholar
S->a^2Db
D->ab
D->a
D->λ
Isn't the language generated by this grammar finite?

evinda

Well-known member
MHB Site Helper
Maybe, but it does not seem to follow directly from the definition.
That is because I think $\gamma$ can be empty in the type-2 grammar, but must specifically be non-empty in the type-1 grammar.
That depends on how a 'string' is defined though - whether it is allowed to be empty or not.

I believe so, yes.
We should be able to recursive apply each possible rule and backtrack, making each of the types 1, 2, and 3 recursively enumerable, and therefore a type 0-grammar.
Ok...

It seems to me that they either consider "abc" a single terminal.
Or they imply that $A\to abcB$ can be rewritten as $A\to aA_1,\,A_1\to bA_2,\,A_2\to cB$, after which the condition is satisfied.

However we interpret it, a language that allows $A\to abcB$ will be equivalent to a type-3 grammar,
But when a language allows $A\to abcB$ then isn't the language also of type 2?

evinda

Well-known member
MHB Site Helper
Isn't the language generated by this grammar finite?
Oh yes, right!!!

The language is represented by the following rules, right?

S->a^2Db
D->a
D->λ

Klaas van Aarsen

MHB Seeker
Staff member
But when a language allows $A\to abcB$ then isn't the language also of type 2?
How so?
How can we rewrite a rule like for instance $A\to Ba$ to that form?

evinda

Well-known member
MHB Site Helper
How so?
How can we rewrite a rule like for instance $A\to Ba$ to that form?
I thought so since $\gamma$ is any string of terminals and non-terminals. Am I wrong?

Klaas van Aarsen

MHB Seeker
Staff member
I thought so since $\gamma$ is any string of terminals and non-terminals. Am I wrong?
In a type-2 grammar $\gamma$ is indeed any string of terminals and non-terminals, allowing for instance $A\to Ba$.
But in a type-3 grammar all rules must have terminal(s) left and non-terminal(s) right, don't they?

Evgeny.Makarov

Well-known member
MHB Math Scholar
The language is represented by the following rules, right?

S->a^2Db
D->a
D->λ
This grammar does not derive aaaab.

evinda

Well-known member
MHB Site Helper
In a type-2 grammar $\gamma$ is indeed any string of terminals and non-terminals, allowing for instance $A\to Ba$.
But in a type-3 grammar all rules must have terminal(s) left and non-terminal(s) right, don't they?
Oh yes, right!!!

So the following grammar is of type 2, right?

S->a^2Db
D->a
D->λ

evinda

Well-known member
MHB Site Helper
This grammar does not derive aaaab.
Oh yes, right....
We have to include D also at the rule with a, i.e. it should be as follows:

S->a^2Db