这是一篇来自澳洲的计算机代写

1 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, finite 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.

2 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 specification 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 (as in a+, meaning the language {an|n ≥ 1}).

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 expressions and languages  (17 marks)

The game of Buckitch has a history that goes back centuries, including being played at the legendary school Warthogs. Matches at Warthogs began shortly after the first recorded match in 1317, and have been held regularly since between the four Warthogs houses of Liongate, Crowfoot, Serpentine and Dragonbreath. Records of all Buckitch matches at Warthogs since 1317 have been kept in a handwritten archive. To save precious parchment and ink, the records of each match were kept as a string, using one character for each house (l, c, s, and d respectively) in the match, and including the date, winner and scores. Such strings were written as follows.

D1D2M1M2Y1Y2Y3Y4H1H2W S1S2S3S4S5S6 where

❼ D1D2 are two digits of the day of the date

❼ M1M2 are two digits of the month of the date

❼ Y1Y2Y3Y4 are four digits of the year of the date

❼ H1 and H2 are the characters representing the two houses involved

❼ W is the character for the winning house

❼ S1S2S3 is the three-digit winning house’s score

❼ S4S5S6 is the three-digit losing house’s score

Note that D1 can only be 0, 1, 2 or 3, M1 can only be 0 or 1 and Y1 can only be 1 or 2. Note also that the score is always a multiple of 10, and can be assumed to be no more than 990.

Buckitch matches are never drawn or incomplete. If no result is possible on the given day, the winner is determined by random choice. This means it is possible for the winning and losing score to be the same.

Scores were written one after the other on the parchment as one enormous string. In order to analyse the history of Buckitch, it is necessary to write regular expressions to identify specific matches of interest somewhere in this string.

(a) Give a regular expression for the following cases.

i.Any match in the year 1737 won by Dragonbreath. (1 mark)

ii.Any match on the 1st of April in which either score was 540. (1 mark)

iii. Any match involving Liongate after 1999. (2 marks)

1. Any sequence of wins for Crowfoot. (3 marks)
2. Any sequence of losses in August for Serpentine before 2000. (4 marks)

(b) Is it possible to give a regular expression for the following cases? Explain either why it is possible or why it is not.

i.Any match in which the scores are equal. (2 marks)

ii.The longest losing sequence for each house. (2 marks)

iii. Any match played on a date which is a palindrome. (2 marks)

2. Grammars

(18 marks)

(a) Consider the G1 grammar below.

S → aaSb | Ab

A → cAc | B

B → ddB | λ

i.Give a derivation of a string in L(G1) which contains at least 4 occurrences of b. (2 marks)

ii.Give a derivation of length at least 8 of a string in L(G1). (2 marks)

iii. Is λ ∈ L(G1)? Explain your answer. (1 marks)

1. Express L(G1) in set notation. (3 marks)
2. Let G2 be the grammar obtained from G1 by adding the rule S → AbS to G1. This makes G2 as below. What is L(G2)? How does it differ from L(G1)? (3 marks)

S → aaSb | Ab | AbS

A → cAc | B

B → ddB | λ

(b) Warthogs School provides its students with identifiers of the form N+I+H  where

❼ N is a 5-digit number over {1, 3, 5, 7, 9}

❼ I is a string over {a, b, e, f} of length at least four in which the number of a’s and f’s is the same

❼ H is a string of length at least two consisting solely of one of the characters{l, c, s, d}

For example, 13579+baaefef+llll and 53399+f af abbbe+ccc are valid identifiers, whereas 13579+baefef+llll and 53399+f af abbbe+csl are not.

i.Give a grammar whose language contains all valid identifiers, and only such identifiers. (2 marks)

ii.Give the derivation in your grammar for the two valid identifiers above.(2 marks)

iii. Warthogs School now decrees that N can be at least 5 digits long or more,but must contain at least one 7. Give a grammar for this new version of identifiers. (3 marks)