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