# Convert the grammar into Chomsky Form

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!
I am asked to convert the following grammar into Chomsky Form
$$\Sigma=\{a,b,c,+\}, \Sigma_Q=\{S,V\},I=S$$
$$S -> S+S|V$$
$$V -> a|b|c$$

My idea is the following:
$$S_0 \rightarrow S$$
$$S \rightarrow ST|V$$
$$T \rightarrow +S$$
$$V \rightarrow A|B|C$$
$$A \rightarrow a$$
$$B \rightarrow b$$
$$C \rightarrow c$$

Could you tell me if my idea is right?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hey!!
I am asked to convert the following grammar into Chomsky Form
$$\Sigma=\{a,b,c,+\}, \Sigma_Q=\{S,V\},I=S$$
$$S -> S+S|V$$
$$V -> a|b|c$$

My idea is the following:
$$S_0 \rightarrow S$$
$$S \rightarrow ST|V$$
$$T \rightarrow +S$$
$$V \rightarrow A|B|C$$
$$A \rightarrow a$$
$$B \rightarrow b$$
$$C \rightarrow c$$

Could you tell me if my idea is right?
Looks like you are going in the right direction.
Introducing $S_0$ makes sure the start symbol does not appear on the right of any rule.
Replace $+S$ by $T$ brings the number of variables on the RHS down to 2, as they should.

However, you still have unit rules, like $S \to V$, which are not supposed to be there.
And you also have a mixed form, $T \to +S$, which I don't think you should have.

#### mathmari

##### Well-known member
MHB Site Helper
However, you still have unit rules, like $S \to V$, which are not supposed to be there.
And you also have a mixed form, $T \to +S$, which I don't think you should have.
How can I change this?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
How can I change this?
In a rule like $S \to V$, replace $V$ with its possibilities.
In the rule $T \to +S$, introduce a new variable that maps to $+$.

#### mathmari

##### Well-known member
MHB Site Helper
In a rule like $S \to V$, replace $V$ with its possibilities.
In the rule $T \to +S$, introduce a new variable that maps to $+$.
Do you mean the following?

$$S_0 \rightarrow S$$
$$S \rightarrow ST$$
$$T \rightarrow PS$$
$$P \rightarrow +$$
$$S \rightarrow a$$
$$S \rightarrow b$$
$$S \rightarrow c$$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Do you mean the following?

$$S_0 \rightarrow S$$
$$S \rightarrow ST$$
$$T \rightarrow PS$$
$$P \rightarrow +$$
$$S \rightarrow a$$
$$S \rightarrow b$$
$$S \rightarrow c$$
Yep!
There you go - Chomsky normal form.

#### mathmari

##### Well-known member
MHB Site Helper
Yep!
There you go - Chomsky normal form.
Great! Thanks a lot for your help!

#### mathmari

##### Well-known member
MHB Site Helper
And if I want to analyze the expression $$a+b+c$$ based on the Chomsky normal form, how can I do this?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
And if I want to analyze the expression $$a+b+c$$ based on the Chomsky normal form, how can I do this?
Let's try to walk through your expression from left to right.

We begin with $a$.
There is only 1 rule that has $a$ in its RHS ($S \to a$), so obviously that one needs to be applied.
That leaves us with $S$. There is only 1 rule that begins with $S$ in its RHS: $S \to ST$.

Summing it up, we get:

 Rule Recognized $S \to a$ $a$ $S \to S|T$ $a|T$ $T \to PS$ $a|PS$ $P \to +$ $a+|S$ ... ...

The vertical line $|$ marks the point to where we have matched the expression.

Perhaps you can continue the analysis...

#### mathmari

##### Well-known member
MHB Site Helper
Let's try to walk through your expression from left to right.

We begin with $a$.
There is only 1 rule that has $a$ in its RHS ($S \to a$), so obviously that one needs to be applied.
That leaves us with $S$. There is only 1 rule that begins with $S$ in its RHS: $S \to ST$.

Summing it up, we get:

 Rule Recognized $S \to a$ $a$ $S \to S|T$ $a|T$ $T \to PS$ $a|PS$ $P \to +$ $a+|S$ ... ...

The vertical line $|$ marks the point to where we have matched the expression.

Perhaps you can continue the analysis...
I tried to continue and this is what I found:

 Rule Recognized $S \to a$ $a$ $S \to S|T$ $a|T$ $T \to PS$ $a|PS$ $P \to +$ $a+|S$ $S \to b$ $a+b$ $S \to S|T$ $a+b|T$ $T \to PS$ $a+b|PS$ $P \to +$ $a+b+|S$ $S \to c$ $a+b+c$

Could you tell me if it is correct?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
I tried to continue and this is what I found:

 Rule Recognized $S \to a$ $a$ $S \to S|T$ $a|T$ $T \to PS$ $a|PS$ $P \to +$ $a+|S$ $S \to b$ $a+b$ FAILED due to ending prematuraly $S \to S|T$ No S to expand $a+b|T$ $T \to PS$ $a+b|PS$ $P \to +$ $a+b+|S$ $S \to c$ $a+b+c$

Could you tell me if it is correct?
There is a problem that I've marked in RED.
At that point there are 2 rules that can be applied.
So you need to apply them simultaneously until one of the 2 paths fails, which happens to be right after.
The same "problem" occurs when recognizing $c$ at the end.

EDIT: Also fixed the first couple of steps.

Properly, it is:

 Rule Recognized $S_0 \to ST$ $S_0 \to a$ $|ST$ $a| \qquad$ FAIL $S \to a$ $a|T$ $T \to PS$ $a|PS$ $P \to +$ $a+|S$ $S \to b$ $S \to ST$ $a+b| \qquad$ FAIL $a+|ST \quad$ only other possibility $S \to b$ $a+b|T$ $T \to PS$ $a+b|PS$ $P \to +$ $a+b+|S$ $S \to c$ $S \to ST$ $a+b+c| \qquad$ SUCCESS $a+b+|ST \quad$ will fail after 2 more steps

#### mathmari

##### Well-known member
MHB Site Helper
 Rule Recognized $S_0 \to ST$ $S_0 \to a$ $|ST$ $a| \qquad$ FAIL $S \to a$ $a|T$ $T \to PS$ $a|PS$ $P \to +$ $a+|S$ $S \to b$ $S \to ST$ $a+b| \qquad$ FAIL $a+|ST \quad$ only other possibility $S \to b$ $a+b|T$ $T \to PS$ $a+b|PS$ $P \to +$ $a+b+|S$ $S \to c$ $S \to ST$ $a+b+c| \qquad$ SUCCESS $a+b+|ST \quad$ will fail after 2 more steps

Could you explain me how you filled the matrix? I got stuck right now..

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Could you explain me how you filled the matrix? I got stuck right now..
How much did you understand?
Or more to the point, where are you stuck?

#### mathmari

##### Well-known member
MHB Site Helper
How much did you understand?
Or more to the point, where are you stuck?
From all the possible rules for $S$, we take $S \to a$, since the expression we want to analyze is $a+b+c$, right?
So, by the rule $S \to ST$ we have $S \to aT$
Then we replace the rule of $T$, so $S \to aPS$ $\Rightarrow$ $S \to a+S$.

We continue by replacing S with the next symbol of the expression, that is $b$ $(S \to bT)$.
So, $S \to a+bT \Rightarrow S \to a+bPS \Rightarrow S \to a+b+S$.

And then we do the same for $c$.
$S \to a+b+c$.

Could you tell me if I understood the procedure of the analysis right?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
From all the possible rules for $S$, we take $S \to a$, since the expression we want to analyze is $a+b+c$, right?
So, by the rule $S \to ST$ we have $S \to aT$
Then we replace the rule of $T$, so $S \to aPS$ $\Rightarrow$ $S \to a+S$.

We continue by replacing S with the next symbol of the expression, that is $b$ $(S \to bT)$.
So, $S \to a+bT \Rightarrow S \to a+bPS \Rightarrow S \to a+b+S$.

And then we do the same for $c$.
$S \to a+b+c$.

Could you tell me if I understood the procedure of the analysis right?
Looks like a sound analysis.

Here's an slightly alternative view.

We have to start with $S_0$, the start symbol.
(I didn't do that at first, which was a mistake on my part. )

There is only 1 rule that applies: $S_0 \to S$.
After that we are left with $S$.
From there we have 4 options:
1. $S \to ST$
2. $S \to a$
3. $S \to b$
4. $S \to c$
Since we're supposed to read $a+b+c$, only the first 2 rules might apply.
So let's keep track of both of them.

If we try $S \to ST$, we are again confronted with the same choice for $S$. Again only the first 2 choices apply. We'll continue with that later.

If we try $S \to a$, no other rules can be applied afterward.
Since there is still more to read, this does not work and we have to mark this as a failure.

So we stick with $S \to ST$ and see where we can go from there...

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Wait a second!
$S_0 \to S$ is not a valid Chomsky Normal Form rule, since they should always be either of the form $A \to BC$ or the form $A \to a$.
It should be replaced by $S_0 \to ST\ |\ a\ |\ b\ |\ c$.

Anyway, I'm glad that the rest of the arguments are still the same.

Sorry for being so obtuse.

#### mathmari

##### Well-known member
MHB Site Helper
$S_0 \to S$ is not a valid Chomsky Normal Form rule, since they should always be either of the form $A \to BC$ or the form $A \to a$.
It should be replaced by $S_0 \to ST\ |\ a\ |\ b\ |\ c$.
Do you mean that the Chomsky normal form of the grammar is the following?
$$S_0 \to ST | a | b | c$$
$$T \to PS$$
$$P \to +$$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Do you mean that the Chomsky normal form of the grammar is the following?
$$S_0 \to ST | a | b | c$$
$$T \to PS$$
$$P \to +$$
Almost. You also need a rule for $S$.

#### mathmari

##### Well-known member
MHB Site Helper
Almost. You also need a rule for $S$.
Oh yes...But what rule is left for $S$ since we have written the rule $S \to a|b|c$ at the first rule? Can I maybe replace $S$ with $S_0$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Oh yes...But what rule is left for $S$? Can I maybe replace $S$ with $S_0$ ?
The rule for $S$ is the same as the one for $S_0$.
Still, they have to be distinct, since CNF requires that the start symbol does not appear on the right hand side of a rule.

#### mathmari

##### Well-known member
MHB Site Helper
The rule for $S$ is the same as the one for $S_0$.
Still, they have to be distinct, since CNF requires that the start symbol does not appear on the right hand side of a rule.
Ok.. But what rule is then for $S$ ?

The only idea I have right now is:
$$S_0 \to ST$$
$$T \to PS$$
$$P \to +$$
$$S \to a|b|c$$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Ok.. But what rule is then for $S$ ?

The only idea I have right now is:
$$S_0 \to ST$$
$$T \to PS$$
$$P \to +$$
$$S \to a|b|c$$
Let's pick:
$$S_0 \to ST|a|b|c$$
$$S \to ST|a|b|c$$
$$T \to PS$$
$$P \to +$$

Yes, it may seem silly, but this fulfills the requirements of CNF.

#### mathmari

##### Well-known member
MHB Site Helper
Let's pick:
$$S_0 \to ST|a|b|c$$
$$S \to ST|a|b|c$$
$$T \to PS$$
$$P \to +$$

Yes, it may seem silly, but this fulfills the requirements of CNF.
So are the following forms not in CNF?
$$S_{0} \to ST$$
$$S \to ST$$
$$T \to PS$$
$$P \to +$$
$$S \to a|b|c$$

or

$$S_{0} \to ST$$
$$T \to PS$$
$$P \to +$$
$$S \to a|b|c$$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
So are the following forms not in CNF?
$$S_{0} \to ST$$
$$S \to ST$$
$$T \to PS$$
$$P \to +$$
$$S \to a|b|c$$

or

$$S_{0} \to ST$$
$$T \to PS$$
$$P \to +$$
$$S \to a|b|c$$
They are in CNF.
Any reason to think otherwise?

MHB Site Helper
Last edited: