Description
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
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
Submission guideline
You need to hand in your assignment electronically using mycourses.binghamton.edu,
which contains:
– A readme, which contains the name and the email address of all group members
– assignment2.pdf, which contains the solution to problems 1-5.
– match.pl
Please place the above files under one directory with a unique name (such as p2-[userid]
for assignment 2, e.g. p2-pyang).
Tar the contents of this directory using the following command.
tar –cvf [directory_name].tar [directory_name]
E.g. tar -cvf p2-pyang.tar p2-pyang/
Use mycourses to upload the tared file you created above.
