###
*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

A_{1} `and` A_{2} `and` A_{3}
is considered structured as
(A_{1} `and` A_{2}) `and` A_{3}

"Implication is right associative"
means that

A_{1} `implies` A_{2} `implies` A_{3}
is considered structured as
A_{1} `implies` (A_{2} `implies` A_{3}).

"Conjunction has precedence over disjunction"
means that

A_{1} `or` A_{2} `and` A_{3}
is considered structured as
A_{1} `or` (A_{2} `and` A_{3}).

## 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 = {a
^{n}b^{2n} | n > 0}
- L = {a
^{k}b^{m}c^{n} | m = k + n }