Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

## Problem 1

Prove that no finite automaton accepts the language

*L1 = { ucv ∈ {a,b,c}* | u,v ∈ {a,b}**
and

*u* is a substring of

*v }*.
Justify your proof - i.e. explain how you know that the string
produced by your proof/algorithm is either in

*L1*
but rejected by the input machine, or accepted by the
input machine but not in

*L1*.

**Example strings in ***L1*:
*bbcbabbbba*
and
*abbcabaabbab*
and
*cabaab*

## Problem 2

Prove that no finite automaton accepts the language

*L2 = { cucvc ∈ {a,b,c}* | u,v ∈ {a,b}**
and

*u* is a substring of

*v }*.
Justify your proof - i.e. explain how you know that the string
produced by your proof/algorithm is either in

*L2*
but rejected by the input machine, or accepted by the
input machine but not in

*L2*.

**Example strings in ***L2*:
*cbbcbabbbbac*
and
*cabbcabaabbabc*
and
*ccabaabc*

## Problem 3

**Challenge Problem:**
Prove that no finite automaton accepts the language

*L3 = { c*^{+}ucvc ∈ {a,b,c}* | u,v ∈ {a,b}*
and

*u* is a substring of

*v }*,
where the "+" is our usual "1 or more occurences", as with
Perl and egrep.
Justify your proof - i.e. explain how you know that the string
produced by your proof/algorithm is either in

*L3*
but rejected by the input machine, or accepted by the
input machine but not in

*L3*.

**Example strings in ***L3*:
*cccccbbcbabbbbac*
and
*cccabbcabaabbabc*
and
*ccabaabc*