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)