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