Theory of Computation #10

Exercise 2.6.3P: Write a program to convert context-free grammars that do not generate the empty string into grammars in Chomsky normal form.

Again, a challenging problem. The choice of the data structure will be very important I think. Let’s start with an example.

So we how would this look in CNF?

We basically do two operations. The first step is to guarantee that the right-hand side is either only a terminal or consists of two terminals.

Let’s write a function for that. This function will return true if it’s already in CNF otherwise false.


Ok, we take a string and check two things. First, the length has to be less or equal 2. And then if the length is 2 if all characters are uppercase. And if the length is one, if the character is lowercase.

We also write a few tests which all work fine. Great.

Although it doesn’t look like much it saved us time.

Continue tomorrow

Theory of Computation #9

Exercise 2.4.3: Design an LL(1) parse table for the following grammar.

The table consists of columns which have terminals and rows for non-terminals.

x y z lambda EOS
S xSz ySz z lambda error

Exercise 2.4.4: How many symbols of lookahead would be required by an LL parser when parsing strings based on the following grammar? Design a corresponding parse table.

Ok, let’s take a look at some derivations:

You can see that we need LL(2). And get the following table.

xx xy yy yx
S xSy xy yy yx

Exercise 2.5.4: Construct an LR(1) parse table for the grammar below.

Ok, let’s start with some examples again of possible derivatives:

And here’s the table:

x y lambda S
1 shift 2 S -> lambda
2 shift 4 shift 3 5
3 S -> xSy S -> xSy 6
4 shift 3
5 shift 3
6 accept

Pretty simple, however took some thinking through. I started with the simplest example and implemented it, and then did the other one. Thanks to the recursive nature of the problem you solve one problem for all problems basically.

Here’s the stack content for xxyy:

It works.

Theory of Computation #8

Excercise 2.1.2: What language is accepted by the pushdown automaton whose transition diagram is shown below?


So, we have one state which is also an acceptance state. We also have to transitions. The first one reads x, pops empty string and pushes x. The second one reads y, pops x and pushes empty string.

We can pop empty strings immediately therefore it starts with reading x. As soon as a y is read it we have to pop an x, i.e. we can only read as many ys as xs but we can read as many xs as we want.

Therefore the language is consists of all elements which hold x^n  y^m where m <= n. Some examples: x, xxxy, xxyxyyx, etc.



Exercise 2.3.5: Convert the following grammar, with start symbol S, into grammar in Chomsky normal form that generates the same language.

As a reminder the Chomsky normal form (CNF) can have the following constructs:

This language doesn’t include the empty string therefore we will only need the first two constructs.

Start with the first rule: S -> xSy. We can transform it to:


The next rule is: S -> wNz. N can either be S or lambda, therefore this rule can be expanded to:

S -> wz and S -> wSz. We can rewrite this in CNF as:


Theory of Computation #7

Let’s say we want to parse the string: xzy. We need a function which takes the string and returns whether it parses or not.

For this I’m thinking about a function which takes the current state and character and returns the next state.

Ok. We work with non-deterministic grammars therefore there are several paths available. But let’s start with the first one. The filter function seems to do a fine job extracting our options.

which returns

That’s helpful. Now, we need to get the correct candidate and extract the next state. I changed my initial design a bit. I started out with the following format: {:State [\character :State]} but changed it to two hashmaps because of the nature of the problem.

First we extract the values, i.e. the right-hand side of the candidates. Here’s the code for candidates:

Now we can mapcat the right-hand side:

which returns

The next step is to map the characters on that list. This is a nice characteristics of hashmaps because our characters are our keywords. Then we filter it and return the first one. That’s the next state.

And it passed all the tests:

Oki doki. So, now that we have the state, we need a function which takes a string and looks at the return value of our get-state stuff. It stops if the returning state is either nil (not valid) or true (valid).

The code is surprisingly super-straight forward.

We just get the state, compare it and return true or false. Now let’s throw some tests in:

And that’s it. That was surprisingly easy. And the code is super nice and easy. I have to say pretty great.