MHB Construct grammar and find its type

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Type
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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
 
Physics news on Phys.org
Hey evinda!

What is $A$? 🤔
 
Klaas van Aarsen said:
Hey evinda!

What is $A$? 🤔

Oh sorry! I meant :

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

:unsure: :unsure: :unsure:
 
evinda said:
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)
 
Klaas van Aarsen said:
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:
 
Indeed. It is not true.
Additionally we can get $a$ now, which is not in the language either is it? (Worried)
 
Klaas van Aarsen said:
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:
 
evinda said:
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. 🤔
 
Klaas van Aarsen said:
Sounds about right yes. 🤔

So is the grammar the following one?

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

:unsure: :unsure:
 
  • #10
But a, ab, and $\lambda$ are not in the language are they? (Worried)
 
  • #11
Klaas van Aarsen said:
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->λ
 
  • #12
That looks correct to me. (Nod)
 
  • #13
Klaas van Aarsen said:
That looks correct to me. (Nod)

Great! (Blush) And how do we find what type of grammar it is? :unsure:
 
  • #14
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:
 
  • #15
evinda said:
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:

evinda said:
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. 🤔

evinda said:
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,
 
  • #16
evinda said:
S->a^2Db
D->ab
D->a
D->λ
Isn't the language generated by this grammar finite?
 
  • #17
Klaas van Aarsen said:
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... 🤓


Klaas van Aarsen said:
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? 🧐
 
  • #18
Evgeny.Makarov said:
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->λ
 
  • #19
evinda said:
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? 🤔
 
  • #20
Klaas van Aarsen said:
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? 🤔
 
  • #21
evinda said:
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? 🤔
 
  • #22
evinda said:
The language is represented by the following rules, right?

S->a^2Db
D->aDb
D->a
D->λ
This grammar does not derive aaaab.
 
  • #23
Klaas van Aarsen said:
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->λ
 
  • #24
Evgeny.Makarov said:
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:
 
  • #25
evinda said:
S->a^2Db
D->aDb
D->aD
D->λ
Yes, I think this is right.
 
  • #26
Evgeny.Makarov said:
Yes, I think this is right.

Great! Thank you! (Blush)
 
  • #27
evinda said:
So the following grammar is of type 2, right?

S->a^2Db
D->aDb
D->a
D->λ
Yep. (Nod)
 
Back
Top