Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
College of Science
Computer Science
CS-275
Automata and Formal Language Theory
Release Time: (Time Zone: BST)
Deadline: (Time Zone: BST)
Exam Paper Information
• This is an open-book test.
• You may consult your notes, textbooks, and other resources as you see fit.
• You must submit before the deadline. Leave some time spare for technical issues.
• This exam is designed to take 2 hours (maybe a little longer to account for typing speed). The
deadline has been set to give you a longer window than necessary to allow you time to deal
with technical issues and to provide some flexibility of starting times.
• It is suggested that you may use Microsoft Word (or any other editor of your choice) to write
your answers, then save a pdf when you are ready to submit.
Special Instructions
Answer all questions.
Submission Instructions
Question 1: Regular Languages (20 marks)
(a) Give a right-linear grammar G for the language La = {ab, ba}∗ such that L(G) = La. (5 marks)
(b) Construct an equivalent DFA for the following NFA. Use the power-set construction. Your work-
ings must be visible by the naming scheme for states used in this construction. You may omit set
brackets in the state names. (10 marks)
b
b
q1
a
b
q3 q4
aq0
q2
a c
b
c
(c) Show that the language Lc = {aib2i | i ∈ N} is not regular. (5 marks)
CS-275: Page 2 of 4
Question 2: Context-Free Languages (20 marks)
In the following, |w|a denotes the number of occurrences of a in w.
(a) Consider the context-free grammar G = ({a, b, c}, {S,A,B,C}, S, P} with P consisting of
S → aAbBcC
A→ aA
A→ a
A→ !
B → bB
B → b
B → !
C → cC
C → c
C → !
Answer the following questions.
(i) What is L(G), the language generated by G? (3 marks)
(ii) Give a leftmost derivation of a word x ∈ L(G) with |x| = 6 and 0 < |x|a < |x|b < |x|c, and
give a matching derivation tree for x. (4 marks)
(iii) Is G ambiguous? Justify your answer. (3 marks)
(b) Consider the language L = {u#v | u, v ∈ {a, b}∗ and 2|u|a = |v|a}.
Give the diagram of a deterministic pushdown automaton P that accepts L by empty stack, i.e.,
N(P ) = L. (5 marks)
(c) Use the pumping lemma for context-free languages to show that the language
L = {anb2nc4n | n ∈ N}
is not context free. (5 marks)
Question 3: Computability and ω-Automata (10 marks)
(a) Give a detailed description (in words) of a Turing machine that accepts the language
L = {aibaibai | i ∈ N}. (5 marks)
(b) Show that f : N→ N with f(x) = 4x for x ∈ N is Turing computable. (3 marks)
(c) What is the language accepted by the Bu¨chi automaton B given by the following diagram with
F = {q1}. (2 marks)