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