Assignment 1
CMSPC 461: Programming Language Concepts
Prof. Suman Saha, Spring 2023
Due: 11:59 PM, - 1st Feb, 2023
Instructions:
You need to submit your homework to Gradescope. Do every problem on a separate page and mark
them before submitting. If the questions are not marked or are submitted with inco
ect page-to-question
mapping, the question will not be graded. Make sure your name and PSU ID is legible on the first page of
your assignment.
We highly recommend you follow the latex/doc template (which can be found on canvas) for the home-
work submissions, however, if you are writing and scanning make sure you maintain proper handwriting
and use stationary of high contrast.
**(Kindly refer syllabus for late submission and academic integration policies.)
Question 1 (7*3 = 21 pt)
Construct regular expressions for the below ’English’ statements. If you cannot construct one, explain why
that may be the case.
1. Given an alphabet Σ = {a, b}, a string where a is repeated even times and b odd times.
2. Given an alphabet Σ = {a, b}, a string which does not end with aa.
3. Given an alphabet Σ = {a, b}, a string which does not contain aa.
4. Given an alphabet Σ = {a, b, c}, a string that has a symbol in the middle that is neither its start nor its
end symbol, and its end and start symbols are different, for eg, a
c or bccccca.
5. Given an alphabet Σ = {a, b}, a string with a’s followed by b’s with both the number of a’s and b’s
eing equal.
6. A general email ID with between 13 to 18 characters before the @ symbol and 4 characters for a
domain name and ’edu’ for a top-level domain.
7. Given an alphabet with opening and closing parentheses only, express a string that contains the sub-
string ((().
1/4
Question 2 (6*3 = 18 points)
1. Read this interesting article on Java (https:
www.ibm.com/cloud
log/jvm-vs-jre-vs-jdk) and tell us
if you think Java is interpreted or compiled and if both, when it is interpreted and when it is compiled.
2. Build a DFA to accept hexadecimal numbers. If a DFA has all its a
ows inverted except the ’starting’
a
ow, would it still be a DFA?
3. Convert the above to an NFA
4. Generate a DFA for a set of strings with a’s followed by b’s with both the number of a’s and b’s being
equal for the alphabet Σ = {a, b}
5. Generate a DFA for a regular expression defined for the language over an alphabet Σ = {a, b} with
only one b.
6. Construct an FA for the regex a*b*a*a with only 3 states
Question 3: Grammar (3*5 = 15 pt)
1. Construct grammar for the below ’English’ statement. Given an alphabet Σ = {a, b}, generate a
grammar that represents strings that start with a when it ends with b and start with b when it ends with
a.
2. Construct grammar for the below ’English’ statement. Given an alphabet Σ = {a, b}, generate a
grammar that represents strings with an equal number of a’s and b’s
3. Is the following BNF grammar ambiguous? If so, design an unambiguous grammar that produces the
same binary-string language.
binary − string > − > 0 | 1 | < binary − string
binary − string
2/4
Question 4 (5*3 = 15 points)
Note that the questions below have a sequence, so working through them in increasing order helps you firm
up your concepts better.
G is a grammar of the form S− > D|S − S|S + S where D represents mathematical digits.
1. Derive XXXXXXXXXXusing leftmost derivation if it is possible.
2. Draw all possible parse trees for the above string.
3. Derive XXXXXXXXXXusing rightmost derivation if it is possible.
4. Derive XXXXXXXXXXusing a derivation that is not leftmost or rightmost (Note - we DO NOT want to
see parse trees)
5. How many left most and right most derivations do we have for the above string? Why?
Question 5 (5*3 = 15 points)
The following is based on Question 4
1. How many parse trees can we construct for the string in Q4.4?
2. Is the number of derivations for the string in Q4.4 the same as the number of parse trees? Why/ why
not?
3. Is this grammar ambiguous? Why/why not?
4. If the grammar is ambiguous (it need not be), try to design a new grammar to remove its ambiguity.
5. For the above question is it possible to do it in multiple ways, and if yes, in each such method, is there
some ’meaning’ to + and -, or their order?
3/4
Question 6 (4*4= 16 points)
These questions are slightly tougher and may require to think deeply. Please attend office hours- we are here
to help!
1. Consider the language consisting of strings that represent the list of numbers separated by commas.
For instance, the string ”10, 7” and ”1, 7, 5, 13” are in the language; also included in the language are
lists of a single number (e.g., ”12”). Write an unambiguous BNF grammar for the language. Briey
explain why your grammar is unambiguous.
2. S− > aS|aSb|b|ϵIs this grammar ambiguous? Why? Can we remove its ambiguity if it is ambiguous
(provide a replacement grammar)?
3. The following grammar for arithmetic expressions allows addition, subtraction, as well as a unary
operator ”∼” for negation; that is, ”∼ 8” is interpreted as the number negative eight.
e >→< d > | < e > + < e > | < e > − < e > | ∼< e
d >→ 0|1|2|3|4|5|6|7|8|9
The grammar is clearly ambiguous. Change the grammar so that ”+”and ”-” are left-associative and
the precedence of ”∼” is higher than ”+” and ”-”.
4. Do context-free grammars represent all regular languages? And do regular languages translate all
grammars? Are there any languages CFGs may not be able to represent? (Explain each answer in 10
words) (2*3 = 6 pt)
4/4