CS275 Automata and Formal Language Theory Coursework Part 2
CS-275 – Coursework Part 2
-
This is an individual assignment, and you must not collaborate with others or share solu- tions.
-
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 ac- cepting the same language as the following non-deterministic one. Do not include unreachable states or dead ends.
1a2 ab
b
b
a,b b
3 b 4 a,b b
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.
