Convert the grammar into Chomsky Form

  • Context:
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Convert Form
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
29 replies · 6K views
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o
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?
 
Physics news on Phys.org
mathmari said:
Hey! :o
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.
 
I like Serena said:
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?
 
I like Serena said:
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$$
 
mathmari said:
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.
 
I like Serena said:
Yep!
There you go - Chomsky normal form.

Great! Thanks a lot for your help!
 
And if I want to analyze the expression $$a+b+c$$ based on the Chomsky normal form, how can I do this?
 
mathmari said:
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:

[table="width: 500, class: grid"]
[tr]
[td]Rule[/td]
[td]Recognized[/td]
[/tr]
[tr]
[td]$S \to a$[/td]
[td]$a$[/td]
[/tr]
[tr]
[td]$S \to S|T$[/td]
[td]$a|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+|S$[/td]
[/tr]
[tr]
[td]...[/td]
[td]...[/td]
[/tr]
[/table]

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

Perhaps you can continue the analysis...
 
I like Serena said:
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:

[table="width: 500, class: grid"]
[tr]
[td]Rule[/td]
[td]Recognized[/td]
[/tr]
[tr]
[td]$S \to a$[/td]
[td]$a$[/td]
[/tr]
[tr]
[td]$S \to S|T$[/td]
[td]$a|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+|S$[/td]
[/tr]
[tr]
[td]...[/td]
[td]...[/td]
[/tr]
[/table]

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:

[table="width: 500, class: grid"]
[tr]
[td]Rule[/td]
[td]Recognized[/td]
[/tr]
[tr]
[td]$S \to a$[/td]
[td]$a$[/td]
[/tr]
[tr]
[td]$S \to S|T$[/td]
[td]$a|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+|S$[/td]
[/tr]
[tr]
[td]$S \to b$[/td]
[td]$a+b$[/td]
[/tr]
[tr]
[td]$S \to S|T$[/td]
[td]$a+b|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a+b|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+b+|S$[/td]
[/tr]
[tr]
[td]$S \to c$[/td]
[td]$a+b+c$[/td]
[/tr]
[/table]

Could you tell me if it is correct?
 
mathmari said:
I tried to continue and this is what I found:

[table="width: 500, class: grid"]
[tr]
[td]Rule[/td]
[td]Recognized[/td]
[/tr]
[tr]
[td]$S \to a$[/td]
[td]$a$[/td]
[/tr]
[tr]
[td]$S \to S|T$[/td]
[td]$a|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+|S$[/td]
[/tr]
[tr]
[td]$S \to b$[/td]
[td]$a+b$ FAILED due to ending prematuraly[/color][/td]
[/tr]
[tr]
[td]$S \to S|T$ No S to expand[/color][/td]
[td]$a+b|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a+b|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+b+|S$[/td]
[/tr]
[tr]
[td]$S \to c$[/td]
[td]$a+b+c$[/td]
[/tr]
[/table]

Could you tell me if it is correct?

There is a problem that I've marked in RED[/color].
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:

[table="width: 500, class: grid"]
[tr]
[td]Rule[/td]
[td]Recognized[/td]
[/tr]
[tr]
[td]$S_0 \to ST$
$S_0 \to a$[/td]
[td]$|ST$
$a| \qquad$ FAIL[/td]
[/tr]
[tr]
[td]$S \to a$[/td]
[td]$a|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+|S$[/td]
[/tr]
[tr]
[td]$S \to b$
$S \to ST$[/td]
[td]$a+b| \qquad$ FAIL
$a+|ST \quad$ only other possibility[/td]
[/tr]
[tr]
[td]$S \to b$[/td]
[td]$a+b|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a+b|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+b+|S$[/td]
[/tr]
[tr]
[td]$S \to c$
$S \to ST$[/td]
[td]$a+b+c| \qquad$ SUCCESS :D
$a+b+|ST \quad$ will fail after 2 more steps[/td]
[/tr]
[/table]
 
I like Serena said:
[table="width: 500, class: grid"]
[tr]
[td]Rule[/td]
[td]Recognized[/td]
[/tr]
[tr]
[td]$S_0 \to ST$
$S_0 \to a$[/td]
[td]$|ST$
$a| \qquad$ FAIL[/td]
[/tr]
[tr]
[td]$S \to a$[/td]
[td]$a|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+|S$[/td]
[/tr]
[tr]
[td]$S \to b$
$S \to ST$[/td]
[td]$a+b| \qquad$ FAIL
$a+|ST \quad$ only other possibility[/td]
[/tr]
[tr]
[td]$S \to b$[/td]
[td]$a+b|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a+b|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+b+|S$[/td]
[/tr]
[tr]
[td]$S \to c$
$S \to ST$[/td]
[td]$a+b+c| \qquad$ SUCCESS :D
$a+b+|ST \quad$ will fail after 2 more steps[/td]
[/tr]
[/table]
Could you explain me how you filled the matrix? I got stuck right now..
 
I like Serena said:
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?
 
mathmari said:
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. :o)

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...
 
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. :o
 
I like Serena said:
$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 +$$
 
I like Serena said:
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$ ?
 
mathmari said:
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.
 
I like Serena said:
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$$
 
mathmari said:
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.
 
I like Serena said:
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$$
 
mathmari said:
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?
 
I like Serena said:
They are in CNF.
Ok!

I like Serena said:
Any reason to think otherwise?

No,I wanted to know if I can write your version like that. :o
 
Last edited by a moderator:
I like Serena said:
Well... they are in CNF, but they represent different languages. :eek:

Ok.. Thanks! :p
 
And something else... :o Is the following analysis a syntax analysis?
I like Serena said:
[table="width: 500, class: grid"]
[tr]
[td]Rule[/td]
[td]Recognized[/td]
[/tr]
[tr]
[td]$S_0 \to ST$
$S_0 \to a$[/td]
[td]$|ST$
$a| \qquad$ FAIL[/td]
[/tr]
[tr]
[td]$S \to a$[/td]
[td]$a|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+|S$[/td]
[/tr]
[tr]
[td]$S \to b$
$S \to ST$[/td]
[td]$a+b| \qquad$ FAIL
$a+|ST \quad$ only other possibility[/td]
[/tr]
[tr]
[td]$S \to b$[/td]
[td]$a+b|T$[/td]
[/tr]
[tr]
[td]$T \to PS$[/td]
[td]$a+b|PS$[/td]
[/tr]
[tr]
[td]$P \to +$[/td]
[td]$a+b+|S$[/td]
[/tr]
[tr]
[td]$S \to c$
$S \to ST$[/td]
[td]$a+b+c| \qquad$ SUCCESS :D
$a+b+|ST \quad$ will fail after 2 more steps[/td]
[/tr]
[/table]
 
I like Serena said:
Yes.

Ok..Thanks a lot! :o
 

Similar threads

Finishing converting to Chomsky Normal Form from a CFG?
  • Lolligirl
  • · Replies 3 ·
  • Programming and Computer Science
Replies
3
Undergrad No structure in ##(d,x)## in ##\textbf{Met*}(X)## is admissible
  • elias001
  • · Replies 0 ·
  • Topology and Analysis
Replies
0
Determine if the string is in L(G)
  • mathmari
  • · Replies 2 ·
  • Programming and Computer Science
Replies
2
High School Special Relativity & Lorentz Transformation Q: Clock C2 Reading?
  • alan123hk
  • · Replies 12 ·
  • Special and General Relativity
Replies
12
Chemistry How do we interpret the steps in the algorithm to balance a redox equation?
  • zenterix
  • · Replies 7 ·
  • Biology and Chemistry Homework Help
Replies
7
Translate the statements into set inclusion
  • mathmari
  • · Replies 5 ·
  • Set Theory, Logic, Probability, Statistics
Replies
5
How to Prove a Complex Number Equation and Its Trajectory Forms a Circle?
  • WMDhamnekar
  • · Replies 2 ·
  • Topology and Analysis
Replies
2
Is left recursion present in this grammar with the given productions?
  • mathmari
  • · Replies 10 ·
  • Programming and Computer Science
Replies
10
Solving T(n) = O(n lg n) using substitution method?
  • evinda
  • · Replies 2 ·
  • Programming and Computer Science
Replies
2
Graduate Finding a suitable form factor for a given set of conditions
  • codebpr
  • · Replies 1 ·
  • Beyond the Standard Models
Replies
1