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 uR is a substring of v}. Remember, uR 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.