This is not the document you are looking for? Use the search form below to find more!

Report

asdf

Document Description
asdf
File Details
Submitter
• Name: asdf
Embed Code:

Related Documents

asdf

by: austin, 9 pages

asdf asdf

asdf

by: asdasdf, 1 pages

asdf

asdf

by: asdf, 5 pages

asdf

asdf

by: asdf, 2 pages

asdf

asdf

by: asdf, 1 pages

asfafs asdf asdfasdf

by: asf, 4 pages

asdf

asdf

by: asdf, 200 pages

asdf

asdf

by: asdf, 2 pages

asdf

asdf

by: asdf, 76 pages

asdf

asdf

by: asdf, 2 pages

asdf

Content Preview
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
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
6

10
7

10
(eg. C3127171_A1.pdf).
8
a
10

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

asdf

Share asdf to:

example:

http://myblog.wordpress.com/
or
http://myblog.com/

Share asdf as:

From:

To:

Share asdf.

Enter two words as shown below. If you cannot read the words, click the refresh icon.

Share asdf as:

Copy html code above and paste to your web page.