Convert the grammar into Chomsky Form

[mathmari]

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]

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]

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]

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]

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]

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]

Yep!
There you go - Chomsky normal form.

Great! Thanks a lot for your help!

 

[mathmari]

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]

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]

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]

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]

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]

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]

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]

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]

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]

$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]

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]

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]

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]

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]

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]

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]

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]

They are in CNF.

Ok!!

Any reason to think otherwise?

No,I wanted to know if I can write your version like that.