Question

7. Let Σ = {a}, and consider the language L = {a n : n is a prime number} = {a 2 , a3 , a5 , a7 , a11 , . . .}.

Is L a regular language?

Why or why not? (Hint: L contains a 11 , a 17 , a 23 , a 29, but not a 77 since 77 is divisible by 11. . . )

8. Design a Turing machine that calculates the sum of two unary numbers. (You can assume the input consists of two unary numbers separated by a single blank space.)

Answer 1

7.

L is not a regular language.

The strings enumerated by the given language are { a^2, a^3, a^5, a^7, a^11, ......... }

A language on a unary alphabet can be accepted by a finite automata only where there is an arithmetic progression with respect to the unary alphabet. Here, the unary alphabet is a and there is no pattern of arithmetic progression among the strings a^2, a^3, a^5, a^7, a^11, ..........

So, the given language L is not a regular language.

8.

In order to build a turing machine to add 2 unary numbers with a blank symbol B in between the numbers, let's consider a string as an instance of the given language.

The string to be considered is represented in the tape as :

1

1

B

1

1

1

B

Here, the unary numbers to be added are 11 and 111 and this would give 11111 that is 2 + 3 = 5.

So, at first, let the initial state be q0.

State q0 on seeing input symbol 1 will remain in the same state, makes no changes to the symbol and moves the head towards the right.

The partial turing machine is :

1/1, R 90

The tape will remain as it is.

State q0 on seeing blank symbol B, will change B to symbol 1, change itself to state q1 and move the head towards the right.

The partial turing machine is :

1/1, R B/1, R 90 91

The tape will become :

1

1

1

1

1

1

B

State q1 on seeing 1 will remain in the same state, make no changes to the symbol and move the head towards the right.

The partial turing machine is :

1/1, R 1/1, R B/1, R 40 91

The tape will remain as it is.

State q1 on seeing blank input B will go to state q2, make no changes to the symbol and move the head towards the left.

The partial turing machine is :

1/1, R 1/1, R B/1, R B/BL 90 91 42

The tape will remain as it is.

State q2 on seeing the symbol 1 to the left of the blank symbol will change to the final state q3, change the symbol 1 to blank symbol B and move the head towards the right.

The partial turing machine is :

1/1, R 1/1, R B/1, R B/BL 1/BR 91

The tape will become :

1

1

1

1

1

B

B

The output 11111 is displayed on the tape which is the required value.

So, the final turing machine for the given language is :

1 / 1, R 1 / 1, R B/1, R B / B, L 1 / B, R q0 q། q2 q3