## Description

## Question 1 (40pts)

a.

S0 S1

S2 S3

b, c

a

a

b

a, b

a

a

Figure 1. NFA N1

For the NFA given above (N1) fill the boxes in the following regular expression using Σ = {a, b, c} and

parentheses or symbols such as + or Kleene Star;

(a(□)

∗a + □ + □)□

Each box is worth 4 points.

b.

S0

S1 S4

S3

S5

S6

A

B

C

1

2

D

E

0

F

Figure 2. NFA N′

1

The NFA N′

1

represents the following regular expression;

((01∗

(0 + 1)1) + 2(2 + 10))(0 + 2)∗

What are the values of A to F? Each one is worth 4 points.

2

## Question 2 (35pts)

Definition. Finite state transducers are DFA-like machines which translate the input strings into output

strings. A Mealy Machine is a deterministic finite state transducer defined as such:

A Mealy Machine M = (Q, s, Σ, O, δ, λ) is a 6-tuple where

• Q is a finite set of states

• s is the starting state

• Σ is the input alphabet

• O is the output alphabet

• δ : Q × Σ → Q is the transition function which maps each (state, input symbol) pair to a state.

• λ : Q × Σ → O is the output function which maps each (state, input symbol) pair to an output

symbol.

In contrast to DFAs, Mealy Machines do not have final states; thus, they do not retain the concept

of accepting or rejecting a string. What they do is reading input from the input tape and writing the

output to the output tape. On the other hand they have output alphabets and output functions. The

output function at first sight resembles the transition function. It takes the same input as the transition

function but returns the output symbol to be emitted at the transition.

To illustrate, a simple Mealy Machine is given below:

M1 = (Q, s, Σ, O, δ, λ) where Σ = {a, b}, O = {A, B, C} and Q, s, δ, λ are as given at the graphical

representation at Figure3.

Remark. x/Y denotes the input symbol x is read and the output symbol Y is outputted.

q0 q2

q1

b/B

a/A

a/C

b/B

a/A

b/B

Figure 3. Mealy Machine M1

a. Notice that the set of output strings that can be produced by a Mealy Machine (i.e. output language

of a Mealy Machine) is a regular language. In fact, an algorithm to compute the output language of a

given Mealy Machine can easily be devised by slightly modifying one of the algorithms you have already

learned (in this course). State which algoritm is it.

Remark: Your answer may be in the form ”the algorithm which is used for this” or ”the algorithm which

does that” or the exact name of the algorithm.

3

b. State the modification(s) that must be made on the algorithm. Your answer does not have to be

very precise, but must somehow express the required modification(s). Also very briefly explain your

reasoning. Answers in the form ”Such a step must be added in order to …”, ”Instead of doing this on

that, doing this on that is required, since…”. will also be accepted. If multiple modifications/additions

are required, present each of them as different bullet points.

Remark: The original algorithm may include steps that are redundant in this context. If so, you do not

have to write anything about such steps. Just assume they do not exist and focus only on the step(s)

that must be modified.

Hint: Only a few modifications/additions are sufficient.

c. Applying the method you proposed at part-b, find the set of output strings of M1 which are ending

with ”C” and express it as a regular expression (M1 is the Mealy machine given at the Figure3.). Show

steps of your solution.

Hint: Do not attempt to find the output language and then to truncate it. Directly finding the requested

set is much easier. A slight simplification on the method you proposed at part-b may be required and

will be accepted (or may not be required, depending on the method you proposed).

## Question 3 (25pts)

Definition. Let us extend the definition of regular expression such that it does not only represent input

strings bu also represent output strings at the same time. That is possible by constituting regular expressions from input/output symbol pairs instead of only input alphabet symbols. To illustrate, (a/A)[(b/C)]∗

denotes a system producing the set of output strings AC∗ while recognizing the set input strings ab∗

;

[(a/A) ∪ (b/B)(a/C)]∗ denotes a system producing the set of output strings (A ∪ BC)

∗ while recognizing

the set of input strings (a∪ba)

∗

. I/O pairs are shown in parentheses so as to determine where the former

output ends and where the latter input starts.

Notably, that extended form of regular expressions enable us to represent the relation between input and

output; which cannot always be captured by providing two separate regular expressions for the sets of

input string and output strings.

You are given a system consisting of a black-box program P, a non-deterministic gate and two NFAs

N2 and N3. The program P takes the input from the outside world, processes it to produce an output,

and transmits the output to the non-deterministic gate. The gate selects one of the two NFAs nondeterministically and inputs the output of P to the selected NFA.

The NFAs N2 and N3 are as given at Figure5 and Figure6 respectively. Moreover, it is known that,

the input/output relation of the program P can be represented by a Mealy Machine; further, the I/O

behaviour of that Mealy Machine can be expressed as

[(a/A) ∪ (b/B)(a/A) ∪ (b/B)(b/B)(a/C)]∗ ∪ [(b/B)(b/B)]∗

4

Figure 4. Described System

q0 q1

q2

q3 q4

B

B

A

ϵ

A

B

A, B

B

Figure 5. N2

5

q0 q2

q1

q3

q4

B

A, B

B

A, B

A

ϵ

C

C

C

Figure 6. N3

Draw the DFA representing the whole system. Show and very briefly explain each step of your solution.

Hint1: Treat the non-deterministic gate as if it is a simple NFA (but you do not have to explicitly model

it as an NFA).

Hint2: The solution might be simpler than you think!

6