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)

Math

Share With

---

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.