in Books, Doing Books, Theory of Computation

Theory of Computation #11

The next major step is to transform existing rules to CNF. We have to do two things:

A) Transform the terminals to new non-terminals
B) Shorten the rule

A) seems easier, so let’s do that first.

Examples: xA, By

In this case, we have to create a new variable – for the sake of simplicity its name will be the name of the terminal in uppercase – and replace it.

Before that I need a function which decomposes the string.

Here’s the code and test: (I edited the input later to directly take a decomposed map)

Ok, now we can concentrate on the right-side of the rules. Want we want the function from before:

The idea is pretty basic. We extract each terminal, i.e. lower case, and create a new rule for that, afterwards we take the initial rule and uppercase everything.

Now we have a list of rules which may be too long. Let’s take care of that.

For the sake of simplicity I will use variables A to H for existing rules. And everything higher than that for new rules which are needed for shortening the existing one.

Let’s say we have the following transformed rules:

What we want is:

Here’s the function to do that:

It works. So, now we need to put everything together.

Continue tomorrow

Write a Comment

Comment