Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

## Problem 1

Write a grammar for the language of all palindromes over

*{a,b}*, and then give the 4-tuple defining it
using the formal definition of a grammar given in the
class notes.

## Problem 2

Write a grammar that generates the language

*L1 = { ucv ∈ {a,b,c}* | u,v ∈ {a,b}*
such that u*^{R} is a substring of
v}.
Remember, u

^{R} means the "reverse"
of string u.
This grammar takes some thinking, but all the ideas for it
are there in the in-class exercises.

## Problem 3

Consider the grammar:

*
G = ( {0,1,:}, {X,Y,Z}, {(X,Y:Z),(Y,00Y),(Y,λ),
(Z,11Z),(Z,1)}, X )
*

*G* is given in the formal 4-tuple notation
described at
the end of the class/notes.
Write down the complete derivation of the string

*00:111* in this grammar.