Computer Science 350 Automata and Formal Languages Assignment 1: Automata
Computer Science 350 (2023)
Assignment 1: Automata
This assignment is worth 100 marks representing 10% of your total course grade.
Solutions must be typed. Respect the academic integrity obligations.
Questions Question A Consider the following NFA N :
a) What is the language accepted by the NFA N ? b) Construct an NFA N1 which accepts the language {an bwb | n ≥ 0, w ∈ {a, b}∗ }. c) Modify N1 such that the language accepted by the new NFA N2 is {an bw | n ≥ 0, w ∈ {a, b}∗ }. d) Construct a DFA M such that L(M ) = L(N2 ). [20 marks]
Question B Consider the sequence of languages Ln = {an bn }, n > 0. a) Fix n. Is the language Ln = {an bn } regular? S b) Let N > 0 be an integer. Is the language L = N n=1 Ln infinite? c) Is the language L regular? S∞ d) Is the language R = n=1 Ln infinite? e) Is the language R regular? Justify all answers. [50 marks]
Question C Consider the language L = {an bm | 0 < n < m or 0 < m < n}. a) Find an error in the following “Proof” that L is not regular: We have L = {an bm | n 6= m, n, m > 0} = {an bn | n > 0}. We know that the language {an bn | n > 0} is not regular, so since the class of regular languages is closed under complement, L can not be regular (since L regular would imply that {an bn | n > 0} is regular). b) Does the wrong proof given for a) imply that L is regular? c) Is L regular? Justify all answers. [30 marks]
