Solution of midterm exam I

Exercise 1

A finite-state automaton accepting the language denoted by [a b c]*/[d | e] is:

                     
       d,e                      d,e                 d,e  
       ___                      ___                 ___  
      /   \                    /   \               /   \ 
     /    |                   /    |              /    | 
     \    |                   \    |              \    | 
      \  \|/      a            \  \|/     b        \  \|/
     ( fs0 ) ------------->   ( s1 ) ---------->  ( s2 ) ---|
         /|\                                                |
          |                                                 |
          |                                                 |
          |-------------------------------------------------|
                                  c

An alternative expression using only primitive operators is:

                     
[[d|e]* a [d|e]* b [d|e]* c]* | [d|e]*

Exercise 2

Note that there are many ways to solve the problem. A short and easy one is:

read regex [i e] -> [e i] || c _ ,,
           [e i] -> [i e] || [? - c] _ ;

Exercise 3

Again, there are many possible solutions. I prefer either:

clear stack ;
define base [{gdwl} | {yph} | {xbrwty} | {rk} | {adwm} | {q$h} | {ap$ry}] ;
define suffix [0 | {h} | {ym} | {wt}] ;
define form base @->  ... %+ suffix ;
define FinalH h -> 0 || _ %+ ? ;
define FinalY h -> t || y %+ _ ;
define RemovePlus %+ -> 0 ;
read regex form .o. FinalH .o. FinalY .o. RemovePlus;

or:

clear stack ;
define base [{gdwl} | {yph} | {xbrwty} | {rk} | {adwm} | {q$h} | {ap$ry}] ;
define suffix [0 | {h} | {ym} | {wt}] ;
define form [base %+ suffix];
define FinalH h -> 0 || _ %+ ? ;
define FinalY h -> t || y %+ _ ;
define RemovePlus %+ -> 0 ;
read regex form .o. FinalH .o. FinalY .o. RemovePlus;

Natural language processing, http://cs.haifa.ac.il/~shuly/teaching/01/nlp/
Updated by shuly@cs.haifa.ac.il on 28 April 2001