Fall 2000, CSE 468: Assignment 4
Distributed: Published on the web on Oct 19.
Due: Nov 1 (in class).
Total maximum score: 100 points.
The purpose of this assignment is to
to provide experience with context-free languages.
Please write your solutions as clearly and concisely as possible.
Exercise 1 (40 pts)
Consider the following context-free grammar, describing the language L of
formulae in propositional logic built on the elementary propositions
p, q, r, and on the connectives "and"
(logical conjunction),
"or" (logical disjunction), and "implies" (logical implication).
S -> p | q | r | S and S | S or S | S implies S | (S)
Note: The alphabet (set of terminal symbols) is Sigma =
{p, q, r, and, or, implies,
(, )}.
- Is it possible to represent L as a regular expression
(over Sigma)? Justify formally the answer.
- Prove that the above grammar is ambiguous
- Give a non-ambiguous grammar generating the same language L, and where:
- conjunction and disjunction are left associative,
- implication is right associative,
- conjunction has precedence over disjunction, and disjunction has precedence
over implication
Note: "conjunction is left associative" means that
A1 and A2 and A3
is considered structured as
(A1 and A2) and A3
"Implication is right associative"
means that
A1 implies A2 implies A3
is considered structured as
A1 implies (A2 implies A3).
"Conjunction has precedence over disjunction"
means that
A1 or A2 and A3
is considered structured as
A1 or (A2 and A3).
Exercise 2 (20 pts)
Consider the following grammar, generating the language of balanced parentheses:
S -> lambda | (S) | SS
- Prove that the above grammar is ambiguous
- Define a non-ambiguous grammar for the same language,
and prove the non-ambiguity of the new grammar.
Exercise 3 (40 pts)
For each of the following languages L, give a context free grammar G
generating the language, and prove that indeed L(G) = L.
- L = {anb2n | n > 0}
- L = {akbmcn | m = k + n }