1. 1. [10 points] Let L be a language over the alphabet å= {a,b} that contains strings over {a,b} such that each string has at least one a and every a is immediately followed by 0 or 1 b. E.g. a, aa, ab, aab, aba, aabab… Give a regular expression that describes L.
2. [10 points] Draw an automaton that accepts the regular expression b(c+ b)*
3. [25 points] Question 5.8 (a) Draw the symbol table for the following C program at the three points (point 1, point 2, and point 3) using static scope. (b) What does the program print using static scope rule ? (c) What does the program print using dynamic scope rule ?
#include <stdio.h>
int a, b ;
int p(void) { int a, p ; /* point 1 */ a = 0 ; b = 1 ; p = 2 ; return p ;
}
void print(void) { print(%d\n%d\n , a,b) ;
}
void q(void)
{ int b ; /* point 2 */ a = 3 ; b = 4 ; print() ;
}
main()
{ /* point 3 */ a = p() ;
q() ;
}
4. [20 points] Question 5.26
5. [15 points] Question 8.9 Give the output of the following program using call-by-value, call-by-reference, and call-by-name.
6. [20 points] Let input.txt be a file containing a sequence of strings. The strings are separated using new lines. Write a Perl program match.pl which reads a file input.txt and print (1) strings that contain the text “or”, (2) strings that contain at least two vowel characters (i.e. a, e, i, o, u), (3) strings that do not start with “h”, (4) strings that have “e” as the second symbol, and end with the letter “y”, and (5) strings that contain both letters and digits. Assume that input.txt contains only letters a-z and digits 0-9.
E.g. input.txt:
today
lord
tomorrow helloy helloa
abc34
Output: today contains at least two vowel letters today does not start with h lord contains or lord does not start with h tomorrow contains or
tomorrow contains at least two vowel letters tomorrow does not start with h helloy contains at least two vowel letters helloy has e as the second symbol and ends with y helloa contains at least two vowel letters abc34 does not start with h abc34 contains both letters and digits
