Starting from:
$26.99

$20.99

TDT4205 Problem Set 1 solution

Please  submit  your  answers  as an  archive  username.tar.gz containing  a PDF file with answers to theoretical questions,  and a code directory  like the provided one, containing  all files required  to build your solution.  Note that this dead- line   is  due to the formal registration deadline for  the course. It is highly recommended that you  complete this exercise within a  week, as  further problem sets will  be issued.

 

 

1    Regular Languages

 

Figure  1: DFA (Initial  state  1, accepting  state  3)

 

1.1

 

Consider  the  set of binary  strings  Σ∗  when Σ = {0, 1}.  Which  of these  strings are not accepted  by the DFA in Fig.  1?

(A  verbal  description suffices to  answer  this  question,  formal  notation is not required.)

 

1.2

 

Write  a regular  expression  for language  of complex numbers  in (finite)  decimal notation, e.g.  0, 127.5, 2.7182 − 3.1425i,  0 + 3i,  etc.   (Assume  that any  pure imaginary  number  will still be written with the real part,  i.e. with prefix 0+  or

0-, and use character classes, positive closure and zero-or-one-instance notation as in Dragon  3.3.5.)

 

1.3

Is the notation for regular expressions (Dragon  3.3.3) itself a regular langugage? Justify  your answer.

 

2    A  Simple Language for  Drawing Lines

 

These exercises will be concerned  with a minimal  toy language to create  simple line  drawings  on  a  page.    The  context   is that of an  imaginary   pencil  point initially  located  near  the  top  left  corner  of the  page.   It  is controlled  by  the three  commands  turn,  draw,  move, and end:

 

• Draw  draws  a line of fixed length  at  a given angle (initially,  straight to- wards the right),  leaving the pencil point at its end.

 

• Turn  alters  the angle of the next  step by 30 clockwise.

 

• Move shifts the point by one step without drawing  the line in between.

 

• End terminates the program.

 

The three  operations are already  implemented as the functions  turn(), draw() and move(); what remains to be implemented is an automaton which recognizes the corresponding  keywords from a text  stream,  and calls the appropriate func- tion.  The three keywords are to be case-insensitive  (i.e.  turn,  TuRn  and TURN are all correct).  Characters not part  of a command  are to be ignored, such that text,  whitespace  and commands  may be freely mixed in the input.

Note:  this specification  is somewhat open to interpretation - if you find some ambiguity,  select an interpretation and state  the reason  for your choice.

 

2.1

 

Draw a deterministic finite automaton which recognizes the three specified com- mands  and consumes/ignores other  input  until  a word has been recognized.

 

2.2

 

The provided archive pencil.tgz contains  code to translate the specified language into  a postscript graphics  file, except  that it is missing a scanner.   Implement your DFA from the previous  task  in scanner.c, to complete  the program.

More products