本次澳洲代写是计算机理论基础的一个assignment
Overview
This assignment is intended both for introducing you to some basic concepts that we
will use in various ways later in the course, and to provide some early feedback on your
progress. The are six key concepts that we will return to again and again, which are formal
languages, regular expressions, grammars, nite state automata, pushdown automata and
Turing machines. A common thread in all of these is nondeterminism. This will come
up in various contexts, as you will see. Much of this assignment is concerned with these
concepts, to ensure that you are well-versed in these fundamentals. There is another part
which deals with the Platypus game.
Assessment details
A Note on Notation of Regular Expressions: Unfortunately there isn’t a uniformly
accepted standard notation for regular expressions. Given we are using JFLAP, our
notation should be as consistent as practicable with that, but that also means some
things get quite cumbersome. The two main issues are the speci cation of alternatives,
and how to abbreviate some obvious patterns like letters and numbers.
So in this assignment the following syntactic rules will be used.
‘+’ will be used to denote both alternatives (as in (1+2)
) and also to denote one or more applications of Kleene star. You must take its application within the context in which it is applied (so you will need to use your brains!).
Ranges such as all letters or all digits will be represented as [a z] meaning (a+b+
c+d+e+f +g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+w+x+y+z).
Hopefully the reason for using ranges is now obvious!
1. Regular Expression and languages. (20 marks)
The Ministry of Craziness uses email addresses of the form
[a z]([a z] + [A Z] + [0 9]) @(([a z])+) moc:com
and employee identi ers of the form
moc([0 9])+@moc:com
(a) Explain why there are email addresses which are also employee identi ers.
Give at least three examples. (3 marks)
(b) Explain why both of the strings gandalf@a4moc:com and Gandalf@magicmoc:com
are neither email addresses nor employee identi ers. (2 marks)
(c) In the company archives, the following regular expression has been found.
Explain what the language of this expression is in terms of email addresses
and employee identi ers. Is the empty string in this language? (3 marks)