Welcome to our community

Be a part of something great, join today!

Construct grammar and find its type

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
Hey evinda !!

What is $A$? 🤔
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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->aD


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

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
Indeed. It is not true.
Additionally we can get $a$ now, which is not in the language either is it? (Worried)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
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
Apr 13, 2013
3,718

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
But a, ab, and $\lambda$ are not in the language are they? (Worried)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
That looks correct to me. (Nod)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
I have found the following about the possible types of a grammar:

type0.PNG

type1.PNG

type2.PNG

type3.PNG

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

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
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,
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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->λ
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
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
Apr 13, 2013
3,718
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
Mar 5, 2012
8,679
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
Jan 30, 2012
2,488
The language is represented by the following rules, right?

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

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,488