Welcome to our community

Be a part of something great, join today!

Convert the grammar into Chomsky Form

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Hey!! :eek:
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
Mar 5, 2012
8,776
Hey!! :eek:
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,776
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,776
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
Apr 14, 2013
4,047

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
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
Mar 5, 2012
8,776
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:

RuleRecognized
$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
Apr 14, 2013
4,047
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:

RuleRecognized
$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:

RuleRecognized
$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
Mar 5, 2012
8,776
I tried to continue and this is what I found:

RuleRecognized
$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:

RuleRecognized
$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 :D
$a+b+|ST \quad$ will fail after 2 more steps
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
RuleRecognized
$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 :D
$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
Mar 5, 2012
8,776
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,776
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. :cool:

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. :eek:)

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
Mar 5, 2012
8,776
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. :eek:
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
$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
Mar 5, 2012
8,776
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,776
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,776
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,776
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?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Last edited: