CS-275讲解、辅导 Java程序设计

CS-275 – Coursework Part 2
Arno Pauly
• By submitting this work, you state that you fully understand and are complying with
the university’s policy on Academic Integrity and Academic Misconduct. The policy can
be found at https://www.swansea.ac.uk/academic-services/ academic-guide/assessmentissues/academic-integrity-academic-misconduct.
• This is an individual assignment, and you must not collaborate with others or share solutions.
• If you are using sources other than the lecture material, cite them.
• You submit your solutions by uploading a single pdf file on Canvas.
• Other than drawings, your answers need to be typed. Drawings can either be created by
hand, or by suitable software tools.
Part 1 of the coursework is done as a Canvas quiz worth 5 marks. Part 2 is
worth 15 marks.
Exercise 1 (3 marks). Use the powerset construction to find a deterministic automaton accepting the same language as the following non-deterministic one. Do not include unreachable
states or dead ends.

Exercise 2 (9 marks). We use the alphabet {a, b, c} and consider the language consisting of all
words meeting the following conditions:
1. Every a is immediately followed by the symbol b.
2. There are strictly more a’s than c’s.
Complete the following tasks:
a) List three words belonging to the language. (1 mark)
b) Prove that the language is not regular using the pumping lemma. (5 marks)
c) Give a context-free grammar for the language. (3 marks)
Exercise 3 (3 marks). Is the formal language comprised of all valid Java programs a regular
language? Justify your answer.

CS-275讲解 、辅导 Java程序设计

CS-275讲解、辅导 Java程序设计