in Books, Doing Books, Theory of Computation

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.

Write a Comment

Comment

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