# Construct grammar and find its type

• MHB
• evinda
In summary: Oh yes, right! (Wait)The language is represented by the following rules, right?S->a^2DbD->aDbD->aD->λThat seems correct to me, yes. In summary, This conversation involved a discussion about constructing a grammar for the language $L=\{ a^i b^j \mid i,j \geq 1, i>j\}$. The conversation included suggestions for starting with the commands $S \to aSb$ and $S \to aDb$, and then considering additional commands such as $D \to aD$ and $D \to a$. The conversation then moved on to discussing the minimum possible power
evinda
Gold Member
MHB
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
D->a

Hey evinda!

What is $A$?

Klaas van Aarsen said:
Hey evinda!

What is $A$?

Oh sorry! I meant :

D->a

:unsure: :unsure: :unsure:

evinda said:
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?

Klaas van Aarsen said:

So is the grammar the following one?

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

:unsure: :unsure:

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

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->λ

That looks correct to me. (Nod)

Klaas van Aarsen said:
That looks correct to me. (Nod)

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

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?

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,

evinda said:
S->a^2Db
D->ab
D->a
D->λ
Isn't the language generated by this grammar finite?

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?

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->a
D->λ

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?

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?

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?

evinda said:
The language is represented by the following rules, right?

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

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->a
D->λ

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

evinda said:
S->a^2Db
D->λ
Yes, I think this is right.

Evgeny.Makarov said:
Yes, I think this is right.

Great! Thank you! (Blush)

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

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

## 1. What is the purpose of constructing grammar?

The purpose of constructing grammar is to create a set of rules and guidelines for how language is used and structured. This allows for effective communication and understanding between speakers of a particular language.

## 2. What are the key components of a constructed grammar?

The key components of a constructed grammar include phonology (the study of speech sounds), morphology (the study of word structure), syntax (the study of sentence structure), and semantics (the study of meaning). These components work together to form a complete system for a language.

## 3. How do you determine the type of a constructed grammar?

The type of a constructed grammar is determined by its structure and features. Some common types of grammar include analytical, synthetic, agglutinative, and polysynthetic. The type can also be influenced by the language's word order, use of affixes, and other linguistic features.

## 4. What are some examples of constructed languages with unique grammar systems?

Some examples of constructed languages with unique grammar systems include Esperanto, a constructed language with a regular and simplified grammar system; Klingon, a fictional language with a complex grammar system; and Lojban, a constructed language with a logical and unambiguous grammar system.

## 5. How does the process of constructing grammar differ from studying natural languages?

The process of constructing grammar involves deliberately creating a set of rules and guidelines for a language, while studying natural languages involves analyzing and describing the grammar systems that have naturally developed in a language. Constructed grammar is often more structured and consistent, while natural languages can have many exceptions and variations in their grammar systems.

• Set Theory, Logic, Probability, Statistics
Replies
24
Views
4K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• General Discussion
Replies
38
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
240
• Set Theory, Logic, Probability, Statistics
Replies
18
Views
1K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
932
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
949
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
440