asdf

COMP2270 – Formal Languages and Automata
Assignment 1
Due on 15/04 (Fri), at 23:59


Question 1
Construct a deterministic finite state machine for each of the following languages:

a) Strings over the alphabet ={a,b} that have ‘abab’ as a substring
b) Strings over the alphabet ={a,b} that have not ‘aa’ nor ‘bb’ as substrings
c) L = {w {a,b,c}*; w= (a b)*abac(a b)*}

Question 2
For part c) above, is your machine minimal? Justify your answer. (Hint: use minDFSM on page
92 of Ref[1])

Question 3
Give nondeterministic finite automata M = (K, , , s, F) that accept the each of the following
languages.

a) The set of strings in (a b)* such that there are two a’s separated by a string whose
length is 4i, for some i.
b) L={ w {a,b}*; w= (ab aab aba)*}

Question 4
For each nondeterministic finite automaton M = (K, , , s, F) of Question 3, give a deterministic
finite automaton M’ = (K’, ’, ’, s’, F’) accepting the same language. Show your work using the
algorithm ndfmtodfsm on page 75 of Ref[1].

Question 5
For the following examples describe informally the languages represented by the FSM and write
down their regular expressions. In cases a) and b) you MUST use the algorithm fsmtoregex
shown in class (page 142 of Ref[1]) and show your work. In the other case you may or may not
use it.


a
a)



b

b
a

a,b



a,b


School of Electrical Engineering & Computer Science
The University of Newcastle

---

b)
a
b



a

b
a,b


a,b


a,b

c)

a



b
b

b
a


a


a,b


Question 6
A farmer has to take three items; a wolf, a sheep and a cabbage, across a river in a boat that just
fits 2 things: the man and something else. If left alone the wolf will eat the sheep and the sheep
will eat the cabbage. Draw a finite state machine to model this problem and solve the puzzle.

Question 7
Consider the following regular grammar G
S aT
T bT
T a
T aW
W
W aT

Use grammartofsm (page 157 of Ref[1]) to generate an FSM M that accepts L(G).

Question 8
Prove using the pumping lemma that the following languages are not regular:

a) L= {aibai | i 0}
b) L= {apq | p,q are primes}
c) L= {aibj |i is divisible by j}


School of Electrical Engineering & Computer Science
The University of Newcastle

---

Exercise 9
Are the following sets closed under the following operations? If not, what are their respective
closures?

a) The odd length strings over the alphabet {a, b} under Kleene star.
b) L = {w {a, b}*} under reverse.

Question 10
Given the following CFG G:
S aSb | SS |

a) List five strings that can be generated by G.
b) Give the derivations of the strings you listed (either as a series of one step
derivations or as a parse tree).
c) Give an English description of the language generated by G.
d) Give a formal description of the language generated by G.


REFERENCES
[1] Elaine Rich, Automata Computability and Complexity: Theory and Applications, Pearson,
Prentice Hall, 2008.

Marking guide

Question
Part
Marks

1
a
5

b
5
Submit using the digital
Total 15 marks
c
5
dropbox in Blackboard
2

10
3
a
5
ONLY.
Total 10 marks
b
5
Don’t forget to attach the
4
a
5
Total 10 marks
b
5
Assignment Cover Sheet
5
a
10

(ACS).
b
10
Total 25 marks
c
5
Carefully label your files
6

10
7

10
(eg. C3127171_A1.pdf).
8
a
10
Include your student

b
10
Total 30 marks
c
10
number and student name
9
a
5
in every page, as a header).
Total 10 marks
b
5
10
a
5

b
10
Total 20 marks
c
2
d
3

Total 150
School of Electrical Engineering & Computer Science
The University of Newcastle

---