Finishing converting to Chomsky Normal Form from a CFG?

[Lolligirl]

Hello everyone! Here is a question I am working on:

Consider the context-free grammar G = ( { S, B, E }, { 0, 1, i, e, s }, R, S ), where R is:

S --> iBSE | s
B --> 0 | 1
E --> lambda | eS

Convert this to Chomsky Normal Form, showing all steps.

Alrighty, so I removed the lambda and got:

S₀ --> S
S --> iBS | iBSE | s
B --> 0 | 1
E --> eS

And now I'm trying to remove the unit/chain rules and the rest, and this is what I have so far:

S₀ --> X
X --> YS
S --> BS
S --> BSE
S --> s
B --> 0
B --> 1
E --> ZS
Y --> i
Z --> e

But I know S₀ --> X and S --> BSE are not valid. From here I am a bit unsure: How can I fix this? Can I do this?

S₀ --> YS
S --> BS
S --> BT
S --> s
B --> 0
B --> 1
E --> ZS
T --> SE
Y --> i
Z --> e

Thank you for any help! :)

 

[I like Serena]

Hi Lolligirl!

Are you still busy with this problem? (Wondering)

S --> iBSE | s
B --> 0 | 1
E --> lambda | eS

Convert this to Chomsky Normal Form, showing all steps.

Alrighty, so I removed the lambda and got:
S₀ --> S
S --> iBS | iBSE | s
B --> 0 | 1
E --> eS

And now I'm trying to remove the unit/chain rules and the rest, and this is what I have so far:
S₀ --> X
X --> YS
S --> BS
S --> BSE
S --> s

Hmm... it looks like you have recycled S to mean something else now... (Worried)
But hold on!
The language in the previous step contained $S_0 \to S \to s$.
But your new language only contains the equivalent $S_0 \to X \to YS \to is$.
You have lost a word from your language!

 

[Lolligirl]

Oh! Could I fix it by doing this?

S₀ --> YS | s
S --> BS | BT
B --> 0 | 1
T --> SE
E --> ZS
Y --> i
Z --> eOr maybe I'm nuts.

 

[I like Serena]

Oh! Could I fix it by doing this?

S₀ --> YS | s
S --> BS | BT
B --> 0 | 1
T --> SE
E --> ZS
Y --> i
Z --> eOr maybe I'm nuts.

That would take care of the missing word 's'... but I do not think the reduction of the rules is right.

You started from:
S0 --> S
S --> iBS | iBSE | s

With your reduction, you no longer have the rule S-->s that could be applied recursively. Now it can only be applied once a the beginning. I think this will go better if you keep the meaning of S the same as it was.
Your might do for instance:
S0 --> S
S --> YU | YV | s
U --> BS
V --> BT
Y --> i
(Wasntme)

 

[LudusRex]

I would like to commend you on your progress in converting the given context-free grammar to Chomsky Normal Form. It is a complex and time-consuming task, but your approach seems to be on the right track.

To address your question about the validity of the rules S0 --> X and S --> BSE, I would suggest looking at the rules carefully to see if they follow the format of Chomsky Normal Form. In this form, all rules must have a single non-terminal symbol on the left-hand side and either two non-terminal symbols or a terminal symbol on the right-hand side.

In the case of S0 --> X, the left-hand side contains a single non-terminal symbol, which is good. However, the right-hand side contains a non-terminal symbol followed by a terminal symbol, which is not allowed in Chomsky Normal Form. To fix this, you can introduce a new non-terminal symbol, say V, and rewrite the rule as S0 --> V. Then, you can add a new rule V --> X to maintain the same meaning as the original rule.

Similarly, for the rule S --> BSE, the right-hand side has three non-terminal symbols, which is not allowed in Chomsky Normal Form. To fix this, you can introduce another new non-terminal symbol, say U, and rewrite the rule as S --> BU. Then, you can add a new rule U --> SE to maintain the same meaning as the original rule.

Overall, your approach to removing unit/chain rules and the rest seems to be correct. Just make sure to carefully check the format of the rules in Chomsky Normal Form and make necessary changes as suggested above. Keep up the good work!