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, 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.