Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / The two automata below describe the possible behaviours of two parts of a machine that accepts £1 and 50p coins, and dispenses coffee or tea, depending on the amount of money in the machine (50p for tea, £1 for coffee)
The two automata below describe the possible behaviours of two parts of a machine that accepts
£1 and 50p coins, and dispenses coffee or tea, depending on the amount of money in the machine (50p for tea, £1 for coffee).
The first automaton M1 considers primarily the total cost of the product (total£1 or total50p) and the dispensing of tea or coffee. Because it does not count the number of coins received, it always allow £1 and 50p coins to be received in the initial state.
qa
qb
qc
£1
50p
total£1
total50p
coffee
tea
The second automaton M2 considers mainly the coins inserted (£1 or 50p) and the total amount
of money available (total£1 or total50p). Because it does not control the dispensing, it always
allows coffee and tea to be dispensed in the initial state.
Page 3 of 12 Continued.q0
q1
q2
coffee
tea
£1
50p
50p
total£1
total50p
The intersection of the behaviours of these automata describes all the possible behaviours of the
system as a whole. Using a systematic procedure for building the intersection of two automata,
draw the automaton of the complete system S [Hint: S = M1 \ M2].
The alphabet of both M1 and M2 is {coffee, tea, £1, 50p, total£1, total50p}.
2 (10 marks)
Using a systematic procedure, convert the following NDFA into an equivalent DFA, and draw the
resulting automaton. Show clearly all the steps involved.
q0 q1 q2 q3
l a a
a l
a b
a
b
Page 4 of 12Module Code
COM00014C
3 (10 marks)
By constructing a tree, identify the distinguishable states for the DFA below. Hence draw a DFA
which is equivalent to this one, but which has a minimal number of states. [Hint: Check if the
non-final states are distinguishable last.]
q0
q1
q2
q3
q4
q5
q6
b
a
a
b
a
b
a
b
a
b
a
b
ab
Page 5 of 12 Turn over.4 (5 marks)
Derive a regular expression for the language accepted by the following FSA, showing all your
working. [Hint: this FSA has two accepting states: you should deal with this issue first.]
q0 a q1 q2
a
b
b
a
5 (5 marks)
The company you are working for has a number of systems that exchange information in a
binary format where the strings always have an even number of symbols. The company wishes
to add a primitive error-detection scheme, where prior to communicating a binary string, a
system must insert either a 0 or a 1 after every two symbols of the original string according to the
following conditions:
• The value attached is 0 if the number of 0s in the original pair of symbols is greater than
the number of 1s.
• The value attached is 1 otherwise; that is if the number of 1s is greater than or equal to the
number of 0s.
For example, if the original string is 00110110, the communicated string should be
000111011101, where the bold digits are the error-detection bits.
Your manager has asked you to implement a DFA that checks whether a binary string received
by a system contains an error or not.
Your task here is either to produce such a DFA or to prove to your boss that a DFA cannot be
created to solve the task.
[Hint 1: If the language is regular, you may first construct an NDFA and then convert it into a
DFA.]
[Hint 2: Otherwise, you may use the pumping lemma to prove that the language is not regular,
and therefore no DFA can be created.]
Page 6 of 12Module Code
COM00014C
6 (5 marks)
One of your company systems produces descriptions of operations over binary strings. In
particular, it produces strings of the format: w1|w2=w3, where ‘0, ‘1’, ‘|’ and ‘=’ are symbols of
the language and w1, w2 and w3 are strings from {0, 1}?. This language contains strings of the
form:
• 00 | 11 = 11
• 11 | 11 = 11
• 10 | 000 = 100
• 101 | 10 = 101
The string 00 | 11 = 00, on the other hand, is not in the language.
The operator | evaluates the two operands w1 and w2 bit by bit from left to right and produces a
new value composed of the disjunction (bitwise or) of the bits of w1 and w2. If one string has
more bits than the other, the remaining bits are just appended to the result. For example:
• 0 | 0 is 0
• 0 | 1 is 1
• 1 | 0 is 1
• 1 | 1 is 1
• w1 | l is w1
• l | w2 is w2
• 01 | 1 is 11 (first 0 | 1 is calculated producing 1, and then the second value is
appended to the result)
Your manager asks you to implement a DFA that accepts a string if and only if it has the format
w1|w2=w3 and w3 is the correct result of w1|w2.
Your task here is either to build such a DFA or to prove to your manager that a DFA cannot be
created to solve the task.
[Hint 1: The operation | extends bitwise OR to work on binary string of different lengths.]
[Hint 2: If it is easier, you may first construct an NDFA and then convert it into a DFA.]
[Hint 3: You may use the pumping lemma to prove that the language is not regular, and therefore
no DFA can be created.]
Page 7 of 12 Continued.7 (5 marks)
Give a context-free grammar for the following language, over alphabet {a, b}:
L = {w : |w| # 5}
8 (5 marks)
Consider the following context-free grammar:
S ! aSaa | b | bb
Identify the language generated by this CFG.
Based on the grammar, draw an NPDA which accepts the same language, by empty stack,
explaining how you have derived all of the states and transitions of the NPDA.
9 (5 marks)
Consider the following FSA:
q0 q1 q2 q3
q4
a
b a
a
b
b
ab
Construct an equivalent CFG, using the structure of the FSA, and explain the process followed
for each component of the grammar.
Page 8 of 12Module Code
COM00014C
10 (5 marks)
Consider the following context-free grammar:
S ! AB | B
A ! aA | a
B ! Bbb | A
(a) [2 marks] Give a derivation for the string aabb.
(b) [3 marks] Show that the grammar is ambiguous.
11 (5 marks)
Consider the following NPDA (accepting by final state)
M = h{q0, q1, q2, q3}, {a, b, c}, {a, b, c, z}, d, q0, z, {q3}i
with the transition function d defined by
d(q0, a, z) = {(q0, az)} d(q1, b, z) = {(q1, bz)}
d(q0, a, a) = {(q0, aa)} d(q1, b, b) = {(q1, bb)}
d(q0, b, z) = {(q1, bz)} d(q1, b, b) = {(q2, l)}
d(q0, b, a) = {(q1, l)} d(q2, b, b) = {(q2, l)}
d(q0, b, a) = {(q1, l)} d(q2, l, z) = {(q3, z)}
(a) [3 marks] Use a sequence of IDs to determine whether or not the string ab3c3 is
accepted (by final state) by this NPDA
(b) [2 marks] What is the language accepted by the NPDA?
12 (10 marks)
(a) [5 marks] Draw an NPDA that accepts, by final state, the following language:
L = {akbmcn : k, m, n # 0, (k = m or k = n}
(b) [5 marks] Give a CFG for the language L from part (a), and draw a parse tree for the
string a2bc2.
Page 9 of 12 Turn over.13 (5 marks)
Suppose that you are using the CYK algorithm to determine whether a string de f gh can be
generated by a particular context-free grammar (written in Chomsky normal form). During this
process, you are completing the following table:
X15
X14 X25
X13 X24 X35
X12 X23 X34 X45
X11 X22 X33 X44 X55
d e f g h
(a) [1 mark] For the entry X35, which substring of de f gh is being considered?
(b) [2 marks] For that entry X35, which pairs of entries lower in the table are considered?
(c) [2 marks] Once the table is complete, how can you tell whether de f gh is generated by
the grammar?
14 (5 marks)
Consider the following context-sensitive grammar:
S ! xxXyyz | xxy
Xy ! yX
Xz ! Yzz
yY ! Yy
xY ! xxXy
xX ! xx
(a) [3 marks] What is the language generated by this grammar?
(b) [2 marks] Give a derivation to show how the string x4y3z2 can be derived in the
grammar.
Page 10 of 12Module Code
COM00014C
15 (10 marks)
Use the Pumping Lemma for context-free languages to show that the following language on
{a, b} is not context-free:
L = {bajb : j = p2 for some p # 0}
16 (5 marks)
Remember that the configuration of a Turing machine can be written xqy, where xy represents
the tape contents, q is the current state, and the position of the read-write head is over the first
symbol of y.
Consider the following Turing machine:
q0 q1 q2 q3
q4
q5 q6
y; y, R
a; x, R b; y, R
y; y, R
a; a, R
z; z, R
b; b, R
c; z, L
b; b, L
z; z, L
y; y, L
y; y, L
a; a, L
x; x, R
z; z, R
y; y, R
2; 2, R
(a) [3 marks] Give a sequence of configurations / IDs to show how this Turing machine
processes an input (ie initial tape contents) of abc.
(b) [2 marks] What is the language that is accepted by this Turing machine, and how is the
contents of the tape at the end of processing a string on the tape related to the original
contents of the string, for an accepted string? You may assume that the string is not empty,
and is made up from as, bs and cs.
