Construct grammar and find its type

[evinda]

Hello! (Wave)

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? :unsure:

S-> aSb
A->aDb
D->aD
D->a

 

[I like Serena]

Hey evinda!

What is $A$?

 

[evinda]

Hey evinda!

What is $A$?

Oh sorry! I meant :

S-> aDb
D->aD
D->a

:unsure: :unsure: :unsure:

 

[I like Serena]

S-> aDb
D->aD
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? (Worried)

 

[evinda]

Ah okay.

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

Oh yes, right! We cannot construct it with those rules... (Tmi)

We have to reuse S...

I have thought of the following grammar so far:

S->aSb
S->D
D->a
D->aDBut as I see this is not true, since we cannot get as many b's as we want. Or am I wrong? :unsure:

 

[I like Serena]

Indeed. It is not true.
Additionally we can get $a$ now, which is not in the language either is it? (Worried)

 

[evinda]

Indeed. It is not true.
Additionally we can get $a$ now, which is not in the language either is it? (Worried)

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? :unsure:
Then S can either get the value ab or a or it finishes.
Is this right? :unsure::unsure::unsure:

 

[I like Serena]

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]

Sounds about right yes.

So is the grammar the following one?

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

:unsure: :unsure:

 

[I like Serena]

But a, ab, and $\lambda$ are not in the language are they? (Worried)

 

[evinda]

But a, ab, and $\lambda$ are not in the language are they? (Worried)

Oh yes, right! (Nod)

So is the grammar the following? (Thinking)

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

 

[I like Serena]

That looks correct to me. (Nod)

 

[evinda]

That looks correct to me. (Nod)

Great! (Blush) And how do we find what type of grammar it is? :unsure:

 

[evinda]

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? (Thinking)

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

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? :unsure::unsure: Shouldn't we only have rules of the form A->aB? Could you explain it to me?

 

[I like Serena]

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. :unsure:

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]

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

Isn't the language generated by this grammar finite?

 

[evinda]

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. :unsure:
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]

Isn't the language generated by this grammar finite?

Oh yes, right! (Wait)

The language is represented by the following rules, right?

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

 

[I like Serena]

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]

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?

 

[I like Serena]

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]

The language is represented by the following rules, right?

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

This grammar does not derive aaaab.

 

[evinda]

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! (Nod)

So the following grammar is of type 2, right? :unsure:

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

 

[evinda]

This grammar does not derive aaaab.

Oh yes, right... (Nod)
We have to include D also at the rule with a, i.e. it should be as follows:S->a^2Db
D->aDb
D->aD
D->λRight? :unsure:

 

[Evgeny.Makarov]

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

Yes, I think this is right.

 

[evinda]

Yes, I think this is right.

Great! Thank you! (Blush)

 

[I like Serena]

So the following grammar is of type 2, right?

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

Yep. (Nod)