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

Theory of Computation #5

Exercise 1.7.8: The string 527943001 is a listing of the digits that appear in the additional problem below as they would appear if we read down columns from right to left. Design a transition diagram for a finite automaton that accepts those and only those strings of digits that can be obtained from addition problems in this fashion.

 095
+042
____
 137

Intriguing. Let’s think about it. We have one special case which comes quite naturally, that is carryover.

I won’t design a diagram but rather write about the idea behind designing one.

Thanks to the nature to the problem we can start with just 3 digits.

0 -> 0 -> 0
0 -> 1 -> 1
0 -> 2 -> 2
....
5 -> 2 -> 7
5 -> 3 -> 8
5 -> 4 -> 9
5 -> 5 -> 10
...
9 -> 5 -> 14
9 -> 6 -> 15
...
9 -> 9 -> 18

You can see that two digits which are less than 10 are easy to solve. Just create states for each one. More interesting are the other cases. My idea is to create a state for results bigger than 10 which takes the next input but handles it like one which is one more. That is, the transition to 1 is equal to transition with input 0. And then we just have to read the string until we hit the end.

Excercise 1.7.15: Describe the language represented by each of the following regular expressions.

a) ((z U y)* o x)
d) ((x* o y* ) o  z*)

I just picked two of the 4 problems because they are similar.

Let’s start with a). z and y are in a union and form a set {z, y} which is than repeated none or more times. That is we now have a set like this {lambda, {z,y}, {zz,yy}, ...}. And finally, we concat x to each of the sets.

d) looks a bit different. The inner operations creates strings like this: lambda, x, xy, xxy, xxxy, …, y, xyy, xyyy, ….., xxy, xxyy, etc. Then we just concat z in a similar fashion on each of these sets.

Theory of Computation #4

Exercise 1.5.2: Show that the grammar below can be modified to be a regular grammar without changing the language it generates.

S -> xyX
X -> xxX
X -> yY
Y -> lambda (empty string)

Let’s think about the rules of regular grammars:

left side has to be a single nonterminal
the right side must be
a) a terminal followed by a nonterminal
b) a single terminal
c) the empty string (lambda)

The first rule is already fulfilled. Therefore, we only have to take care of the second one. The problems are the first and second line of our grammar which contains two terminals and a nonterminal. The last two lines aren’t affected by any changes we will do.

S -> xyX
X -> xxX

Start with the start state S. We can transform it like this:

S -> xA
A -> yX

And the second state X can be transformed like this:

X -> xB
B -> xX

Why can’t we just write X -> xX? The answer is that we have two rules for X. If we would just write xX the output could be x(yY) which isn’t equal to xxX.

So our new grammar is:

S -> xA
A -> yX
X -> xB
B -> xX
x -> yY
y -> lambda.

Exercise 1.5.3: Convert the regular grammar below to another regular grammar that contains no rewrite rules whose right sides consist of a single terminal, and yet generates the same language. Describe the language generated in your own words.

S -> xS
S -> y
S -> z

This is an interesting grammar. Let’s take a look at some derivations.

y
z
xy
xz
xxy
xxz
xxxy
xxxz
...

Now take a look back at the definition of a regular grammar. We need some way to end the string and we will use lambda. I hope I understand the definition correctly in this case that this isn’t considered a single terminal. Therefore we need some state like A -> lambda.

S -> xS
S -> yA
S -> zA
A -> lambda

And this should do the job.

Theory of Computation #3

Exercise 1.2.1: Describe the strings that are accepted by the deterministic finite automaton represented in the following transition diagram.

Let’s just follow the arrows. We start and we need a letter to get into the acceptance state. In this state we can have either a letter or a digit. Therefore the strings start with a letter and then are followed by a letters of digits. Examples: r2d2, Hello, Mr234S

Exercise 1.2.3: Identify another deterministic finite automaton in everyday life and draw its transition diagram.

The book listed the example of a vending machine and a telephone call. Both receive strings and jump between states. One other common example which I choose are traffic lights.

Let’s make it super easy, i.e. a traffic light which just switches between red, yellow, green for cars and red and green for pedestrians. Also there’s no option for the pedestrians to request green light.

The signal in our case is a timer. I also assume for simplicity that each transition has the same delay.

I represent the state as a tuple of (light cars, light pedestrians).

The starting state is (green, red).

(green,red) -> (yellow, red) -> (red, red) -> (red, green) -> (red, red) -> to the start

It’s a bit more boring then the other examples because it just cycles through its states but you can think about the diagram using a request button for pedestrians.