MHB Convert the grammar into Chomsky Form

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Convert Form
AI Thread Summary
The discussion revolves around converting a given grammar into Chomsky Normal Form (CNF). The original grammar includes rules for combining symbols and terminal values. The user proposes an initial transformation that introduces new variables but retains unit rules and mixed forms, which are not allowed in CNF. Feedback highlights the need to eliminate unit rules by replacing them with their possible expansions and to introduce new variables for terminals like '+'. The conversation progresses to analyzing the expression "a+b+c" using the CNF. The analysis involves applying the appropriate rules step by step, recognizing each component of the expression. The user successfully identifies the sequence of rules leading to the final expression, although some confusion arises regarding the structure of the rules and the necessity for distinct start symbols. Ultimately, the correct CNF is confirmed, and the analysis is validated as a syntax analysis, demonstrating a clear understanding of the conversion and analysis processes.
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
Views
2K
I No structure in ##(d,x)## in ##\textbf{Met*}(X)## is admissible
Replies
0
Views
1K
MHB Determine if the string is in L(G)
Replies
2
Views
1K
B Special Relativity & Lorentz Transformation Q: Clock C2 Reading?
Replies
12
Views
2K
Chemistry How do we interpret the steps in the algorithm to balance a redox equation?
Replies
7
Views
2K
MHB Translate the statements into set inclusion
Replies
5
Views
1K
MHB Is left recursion present in this grammar with the given productions?
Replies
10
Views
3K
MHB How to Prove a Complex Number Equation and Its Trajectory Forms a Circle?
Replies
2
Views
3K
MHB Solving T(n) = O(n lg n) using substitution method?
Replies
2
Views
2K
A Finding a suitable form factor for a given set of conditions
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top