in Books, Doing Books, Theory of Computation

Theory of Computation #6

Exercise 1.7.16: Write regular expressions that describe the following languages.
a) All strings consisting of an odd number of xs.
b) All strings consisting of an odd number of xs and an even number of ys.
c) All strings of xs and ys such that each y is immediately preceded by an x and immediately followed by an x.

Let’s take a look at a). We want an odd number of xs, i.e. x, xxx, xxxxx, etc. That is, we want at least one x and if so than two addition ones.

(x o (xx)*)

b) We solved the first problem in a) so now we generate an even number of ys which is also easy because we solved that already in a).

(yy)*

Now we just union both expressions: ((x o (xx)*) U (yy) *)

And c). Some example strings are: xyx, xxyx, xxyxx, xxxyx, etc.

((x o x*) o y o (x o x *)) *

Which is just at least one x concatenated to y to at least one x. This creates one sequence and now we just need to create each of them with *.

Exercise 1.7.P3: Develop a software package that automatically generates parsers for regular languages. First, write a program that accepts regular grammars as its input and generates corresponding transition tables as its output. Then, write a program that analyzes its input string according to the transition table generated by the previous program.

I was quite surprised reading this problem but I like the challenge. Our first task is to write a program which takes regular grammars and generates corresponding transition tables.

I will take the same format as previously for the transition tables, i.e. a vector of hashmaps. The grammar can presented similarly.

Let’s work with a simple example which helps understanding the problem and creating the design.

Our grammar will be:

S -> xA
A -> yB
A -> zA
B -> lambda

I made it a bit more challenging by including non-deterministic rules.

So, how should we represent a rule? An idea is a hashmap. I’m thinking about something like this. All states are keywords. Also they are followed by a hashmap which includes the actions to be taken. lambda, i.e. end of string will be nil.

{:S {\x :A}}
{:A {\y :B}}
{:A {\z :A}}
{:B {nil true}}

I wonder if I want to create a transition table at all. The language is so flexible that I can do without it pretty fine I think. Let’s try it.

Tomorrow part 2

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.