Convert the grammar into Chomsky Form

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Convert Form
Click For Summary

Discussion Overview

The discussion revolves around converting a given grammar into Chomsky Normal Form (CNF). Participants explore the necessary transformations and rules involved in this process, including addressing unit rules and mixed forms, while analyzing specific expressions based on the CNF.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants propose a transformation of the grammar, introducing new variables to eliminate unit rules and mixed forms.
  • Others argue that the initial transformation contains issues, such as the presence of unit rules like $S \to V$ and mixed forms like $T \to +S$.
  • A later reply suggests replacing unit rules by substituting $V$ with its possible values and introducing a new variable for $+$.
  • Participants discuss the step-by-step analysis of the expression $a+b+c$ based on the CNF, highlighting the application of rules and the need to track multiple paths.
  • Some participants identify potential failures in the analysis and suggest corrections, emphasizing the importance of adhering to CNF rules.
  • There is a point raised about the validity of the starting rule $S_0 \to S$, with a suggestion that it should be replaced to conform to CNF requirements.

Areas of Agreement / Disagreement

Participants generally agree on the need to transform the grammar into CNF, but there are multiple competing views on the specific steps and rules involved in the transformation process. The discussion remains unresolved regarding the final form of the grammar and the correctness of the analysis of the expression.

Contextual Notes

Limitations include unresolved issues with unit rules and mixed forms, as well as the need for clarity on the starting rule in CNF. The discussion reflects varying interpretations of the transformation process and the analysis of expressions.

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?
 
Technology 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?
 
mathmari said:
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 $+$.
 
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...
 
  • #10
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?
 
  • #11
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]
 
  • #12
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..
 
  • #13
mathmari said:
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?
 
  • #14
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?
 
  • #15
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...
 
  • #16
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
 
  • #17
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 +$$
 
  • #18
mathmari said:
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$.
 
  • #19
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$ ?
 
  • #20
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.
 
  • #21
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$$
 
  • #22
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.
 
  • #23
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$$
 
  • #24
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?
 
  • #25
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:
  • #26
mathmari said:
Ok!

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

Well... they are in CNF, but they represent different languages. :eek:
 
  • #27
I like Serena said:
Well... they are in CNF, but they represent different languages. :eek:

Ok.. Thanks! :p
 
  • #28
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]
 
  • #29
mathmari said:
And something else... :o Is the following analysis a syntax analysis?

Yes.
 
  • #30
I like Serena said:
Yes.

Ok..Thanks a lot! :o
 

Similar threads

MHB Finishing converting to Chomsky Normal Form from a CFG?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad No structure in ##(d,x)## in ##\textbf{Met*}(X)## is admissible
  • · Replies 0 ·
Replies
0
Views
2K
MHB Determine if the string is in L(G)
  • · Replies 2 ·
Replies
2
Views
1K
High School Special Relativity & Lorentz Transformation Q: Clock C2 Reading?
  • · Replies 12 ·
Replies
12
Views
3K
Chemistry How do we interpret the steps in the algorithm to balance a redox equation?
  • · Replies 7 ·
Replies
7
Views
3K
MHB Translate the statements into set inclusion
  • · Replies 5 ·
Replies
5
Views
1K
MHB How to Prove a Complex Number Equation and Its Trajectory Forms a Circle?
  • · Replies 2 ·
Replies
2
Views
3K
MHB Is left recursion present in this grammar with the given productions?
  • · Replies 10 ·
Replies
10
Views
3K
MHB Solving T(n) = O(n lg n) using substitution method?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Finding a suitable form factor for a given set of conditions
  • · Replies 1 ·
Replies
1
Views
2K